Algoritmo per convertire un numero infinito di base 2 ^ 32 in base stampabile 10

Question

Sto rappresentando un intero infinitamente preciso come una matrice di interi senza segno per l'elaborazione su una GPU. Ai fini del debug, vorrei stampare la rappresentazione in base 10 di uno di questi numeri, ma ho difficoltà a avvolgerci la testa. 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?

Modifica: ecco un'implementazione completa 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 hai accesso all'aritmetica a 64 bit, è più facile. Farei qualcosa del genere:

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 () sono rimasti da implementare. divideBy10 divide per 10 e restituisce il resto.

Answer 2

Fondamentalmente hai bisogno della classica stampa decimale usando la produzione di cifre dividendo il tuo numero per dieci (nella tua base 2 ^ 32) ripetutamente e usando il resto come cifre. Potresti non avere una divisione per (niente, figuriamoci) con la routine 10, che è probabilmente la fonte chiave del tuo problema.

Se lavori in C o C ++, puoi ottenere un pacchetto aritmetico di precisione infinita completo da pacchetto GNU Bignum . La maggior parte delle altre lingue ampiamente utilizzate hanno pacchetti simili disponibili.

Naturalmente, se hai troppo tempo libero, puoi sempre implementare tu stesso la divisione multiprecisione. Stai già prendendo in prestito la terminologia da Knuth; fornisce anche algoritmi multiprecisione in algoritmi seminumerici.

Answer 3

Se è .NET, dai un'occhiata a questa implementazione di una classe BigInteger .

Answer 4

Che ne dici di usare i doppi lunghi? Quindi ottieni 80 bit nella mantissa, ma immagino che la precisione venga persa quando si usano numeri in virgola mobile.