Algoritmo para convertir la base infinitamente larga 2^32 número en base imprimible 10

Question

Represento un entero infinitamente preciso como una matriz de entradas sin signo para procesar en una GPU. Para fines de depuración, me gustaría imprimir la representación de base 10 de uno de estos números, pero estoy teniendo dificultades para entenderlo. Esto es lo que me gustaría hacer:

//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); 

¿Alguna sugerencia sobre cómo abordar este problema?

Editar: Aquí está una implementación completa gracias a 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

Si tiene acceso a la aritmética de 64 bits, es más fácil. Me gustaría hacer algo en la línea de:

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() e inverso() a ser implementado. divideBy10 se divide por 10 y devuelve el resto.

Answer 2

Si se trata de .NET, echar un vistazo a this implementation of a BigInteger class.

Answer 3

Fundamentalmente necesita una impresión decimal clásica con producción de dígitos dividiendo su número por diez (en su base 2^32) repetidamente y usando el resto como dígitos. Puede que no tenga una rutina dividida por (cualquier cosa, menos) 10, que probablemente sea la fuente clave de su problema.

Si está trabajando en C o C++, puede obtener un paquete aritmético de precisión infinita completo desde GNU Bignum package. La mayoría de los otros idiomas ampliamente utilizados tienen paquetes similares disponibles.

Por supuesto, si tiene demasiado tiempo libre, siempre puede implementar la división de multiplicidad usted mismo. Ya está pidiendo prestado la terminología de Knuth; él también suministra los algoritmos de multiprecision en Seminumerical Algorithms.

Answer 4

¿Qué le parece usar dobles largos? Luego obtienes 80bits en la mantisa, pero supongo que la precisión se pierde cuando se usan números de coma flotante.