CODEWITHSUNDEEP
algorithmmathbignumarbitrary-precision
iolo
iolo

Reputation: 1090

binary to decimal base shift

I need an algorithm that converts an arbitrarily sized unsigned integer (which is stored in binary format) to a decimal one. i.e. to make it human-readable ;)
I currently use the maybe (or obviously) somewhat naive way of continuously calculating the modulus and remainder through division through ten.
Unfortunately the speed is somewhat... lame.

e.g. I calculate 2000^4000 (with my bignum library) which takes roughly 1.5 seconds (no flaming please xD). The print including the necessary base conversion however takes about 15 minutes which is quite annoying.

I have tested bc which does both in a lot less than one second.
How does it do that? (Not the multiplication stuff with ffts and whatever only the base conversion)

Upvotes: 1

Views: 13410

Answers (3)

kaharas
kaharas

Reputation: 607

There's no need to use exponentiation:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int main(){
    char a[] = "10011";
    unsigned long int res= 0;
    int i;

    for(i = 0; i < strlen(a); i++){
        res = (res<<1) + (a[i]-'0');
    }

    printf("%d",res);
    return 0;
}

FIRST UPDATE

Now length shouldn't be a problem...

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *doubles(char *);
char *sum(char *,int);

int main(){
    char a[] = "10011";
    char *res = calloc(2,sizeof(char));
    int i;

    res[0] = '0';
    for(i = 0; i < strlen(a); i++){
        res = sum(doubles(res),(a[i]-'0'));
    }

    printf("%s",res);
    return 0;
}

char *doubles(char *s){
    int i,len = strlen(s),t = 0;
    char *d;
    d = calloc(len+1,sizeof(char));
    for(i = 0; i < len; i++){
        t = ((s[len-i-1]-'0')<<1) + t;

        d[len-i] = ('0' + (t%10));
        t = t/10;
    }

    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}

char *sum(char *s,int n){
    int i, len = strlen(s),t = n;
    char *d = calloc(len+1,sizeof(char));

    for(i = 0; i < len ; i++){
        t = (s[len-i-1]-'0') + t;
        d[len-i] = ('0' + (t%10));
        t = t/10;
    }
    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}

Upvotes: 0

6502
6502

Reputation: 114481

I think that bc is using 10^n as base instead of 2. So every internal "digit" is just n decimal digits and at least for decimal input/output the problem becomes trivial.

Upvotes: 1

Nikita Rybak
Nikita Rybak

Reputation: 68006

I currently use the maybe (or obviously) somewhat naive way of continuously calculating the modulus and remainder through division through ten.
Then you should have O(n^2) complexity, which should fare much better than 15 minutes.

Although, it's worth looking how exactly you do division by 10.

  1. Make sure you apply not generic division of long by long, but simpler algorithm of division long number by standard one.
  2. Make sure that you reuse memory. Allocating 10Kb blocks 10000 times would surely hinder your performance.

edit
How to divide long binary number by 10 in one pass and get both result and reminder. With no additional memory.
Simple pseudo-code (a[0] is the highest order digit)

int r = 0;
for (int i = 0; i < n; ++i) {
    r = r * 2 + a[i];
    a[i] = r / 10;
    r = r % 10;
}

Let's take an example, number 100111011 = 315.

Step 0: r = 1, a[0] = 0
Step 1: r = 2, a[1] = 0
Step 2: r = 4, a[2] = 0
Step 3: r = 9, a[3] = 0
Step 4: r = 9, a[4] = 1
Step 5: r = 9, a[5] = 1
Step 6: r = 8, a[6] = 1
Step 7: r = 7, a[7] = 1
Step 8: r = 5, a[8] = 1

So, reminder is 5 and the result is 000011111 = 31.

Upvotes: 2

Related Questions