Algorithme pour convertir un nombre infiniment long en base 2 ^ 32 en base imprimable 10

Question

Je représente un entier infiniment précis sous la forme d'un tableau d'ints non signés à traiter sur un GPU. Pour des raisons de débogage, j'aimerais imprimer la représentation en base 10 de l’un de ces chiffres, mais j’ai du mal à comprendre. Voici ce que j'aimerais faire:

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

Des suggestions sur la façon d'aborder ce problème?

Modifier: voici une implémentation complète grâce à 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 vous avez accès à l'arithmétique 64 bits, c'est plus simple. Je voudrais faire quelque chose le long de la ligne 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 () et reverse () doivent être implémentés. divideBy10 divise par 10 et renvoie le reste.

Answer 2

Fondamentalement, vous avez besoin d’une impression décimale classique utilisant la production de chiffres en divisant votre nombre par dix (dans votre base 2 ^ 32) à plusieurs reprises et en utilisant le reste sous forme de chiffres. Vous ne pouvez pas avoir de routine de division par (n'importe quoi, encore moins) 10, ce qui est probablement la source principale de votre problème.

Si vous travaillez en C ou C ++, vous pouvez obtenir un paquet arithmétique à précision infinie complet à partir du paquet GNU Bignum . . Des packages similaires sont disponibles dans la plupart des autres langues largement utilisées.

Bien sûr, si vous avez trop de temps libre, vous pouvez toujours implémenter vous-même la division multi-précision. Vous avez déjà emprunté la terminologie à Knuth; il fournit également les algorithmes multi-précision dans les algorithmes séminumériques.

Answer 3

S'il s'agit de .NET, consultez cette implémentation d'une classe BigInteger .

Answer 4

Pourquoi ne pas utiliser de longs doubles? Ensuite, vous obtenez 80 bits dans la mantisse, mais je suppose que la précision est perdue lors de l’utilisation de nombres à virgule flottante.