Algorithm to convert infinitely long base 2^32 number to printable base 10.

Question

I'm representing an infinitely precise integer as an array of unsigned ints for processing on a GPU. For debugging purposes I'd like to print the base 10 representation of one of these numbers, but am having difficulty wrapping my head around it. Here's what I'd like to do:

//the number 4*(2^32)^2+5*(2^32)^1+6*(2^32)^0
unsigned int aNumber[3] = {4,5,6};
char base10TextRepresentation[50];
convertBase2To32ToBase10Text(aNumber,base10TextRepresentation);

Any suggestions on how to approach this problem?

Edit: Here's a complete implementation thanks to drhirsch

#include <string.h>
#include <stdio.h>
#include <stdint.h>

#define SIZE 4

uint32_t divideBy10(uint32_t * number) {
  uint32_t r = 0;
  uint32_t d;
  for (int i=0; i<SIZE; ++i) {
    d = (number[i] + r*0x100000000) / 10;
    r = (number[i] + r*0x100000000) % 10;
    number[i] = d;
  }
  return r;
}

int zero(uint32_t* number) {
  for (int i=0; i<SIZE; ++i) {
    if (number[i] != 0) {
      return 0;
    }
  }
  return 1;
}

void swap(char *a, char *b) {
  char tmp = *a;
  *a = *b;
  *b = tmp;
}

void reverse(char *str) {
  int x = strlen(str);
  for (int y = 0; y < x/2; y++) {
    swap(&str[y],&str[x-y-1]);
  }
}

void convertTo10Text(uint32_t* number, char* buf) {
  int n = 0;
  do {
    int digit = divideBy10(number);
    buf[n++] = digit + '0';
  } while(!zero(number));
  buf[n] = '\0';
  reverse(buf);
}

int main(int argc, char** argv) {
  uint32_t aNumber[SIZE] = {0,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
  uint32_t bNumber[4] = {1,0,0,0};

  char base10TextRepresentation[50];

  convertTo10Text(aNumber, base10TextRepresentation);
  printf("%s\n",base10TextRepresentation);
  convertTo10Text(bNumber, base10TextRepresentation);
  printf("%s\n",base10TextRepresentation);
}

Answer 1

If it is .NET, take a look at this implementation of a BigInteger class.

Answer 2

If you have access to 64 bit arithmetic, it is easier. I would do something along the line of:

int32_t divideBy10(int32_t* number) {
    uint32_t r = 0;
    uint32_t d;
    for (int i=0; i<SIZE; ++i) {
        d = (number[i] + r*0x100000000) / 10;
        r = (number[i] + r*0x100000000) % 10;
        number[i] = d;
        number[i] = r;
}

void convertTo10Text(int32_t* number, char* buf) {
    do {
        digit = divideBy10(number);
        *buf++ = digit + '0';
    } while (!isEqual(number, zero));
    reverse(buf);
}

isEqual() and reverse() left to be implemented. divideBy10 divides by 10 and returns the remainder.

Answer 3

Fundamentally you need classic decimal printing using digit production by dividing your number by ten (in your base 2^32) repeatedly and using the remainder as digits. You may not have a divide by (anything, let alone) 10 routine, which is probably the key source of your problem.

If you are working in C or C++, you can get a complete infinite precision arithmetic package from GNU Bignum package. Most other widely used languages have similar packages available.

Of course, if you have too much free time, you can always implement multiprecision division yourself. You're already borrowing terminology from Knuth; he also supplies the multiprecision algorithms in Seminumerical Algorithms.

Answer 4

How about using long doubles? Then you get 80bits in the mantissa, but I guess that the accuracy is lost when using floating point numbers.