binary to decimal base shift

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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;
}