Algoritmo per convertire il numero infinitamente lungo della base 2^32 alla base stampabile 10

Question

Rappresento un numero infinitamente preciso come una matrice di input non firmati per l'elaborazione su una GPU. Per motivi di debug mi piacerebbe stampare la rappresentazione di base 10 di uno di questi numeri, ma ho difficoltà a girarmi intorno. Ecco cosa mi piacerebbe fare:

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

Qualche suggerimento su come affrontare questo problema?

Edit: Ecco una completa implementazione grazie 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

Se si ha accesso all'aritmetica a 64 bit, è più semplice. Vorrei fare qualcosa lungo la linea del:

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 reverse() a sinistra per essere attuato. divideBy10 divide per 10 e restituisce il resto.

Answer 2

Se è NET, dare un'occhiata a this implementation of a BigInteger class.

Answer 3

Fondamentalmente è necessaria la stampa decimale classica utilizzando la produzione di cifre dividendo il numero per dieci (nella base 2^32) ripetutamente e usando il resto come cifre. Non puoi avere una divisione per (nulla, per non parlare) 10 routine, che è probabilmente la fonte chiave del tuo problema.

Se si lavora in C o C++, è possibile ottenere un pacchetto aritmetico di precisione infinito completo da GNU Bignum package. La maggior parte delle altre lingue ampiamente utilizzate ha pacchetti simili disponibili.

Ovviamente, se hai troppo tempo libero, puoi sempre implementare la divisione multiprecisione da solo. Stai già prendendo in prestito la terminologia da Knuth; inoltre fornisce gli algoritmi di multiprecisione in Algoritmi Seminumerici.

Answer 4

Che ne dici di usare i doppi lunghi? Quindi si ottengono 80 bit nella mantissa, ma suppongo che l'accuratezza si perda quando si usano numeri in virgola mobile.