Algoritmo para convertir una base infinitamente larga de 2 ^ 32 números a base imprimible 10

Question

Estoy representando 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 en base 10 de uno de estos números, pero tengo dificultades para envolver mi cabeza alrededor de él. 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í hay 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 aritmética de 64 bits, es más fácil. Haría 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 () y reverse () a la izquierda para ser implementado. divideBy10 se divide por 10 y devuelve el resto.

Answer 2

Fundamentalmente, necesita la impresión decimal clásica utilizando la producción de dígitos al dividir su número por diez (en su base 2 ^ 32) repetidamente y usar el resto como dígitos. Es posible que no tenga una rutina de dividir por (cualquier cosa, y mucho 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 de paquete GNU Bignum . 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 multiprecisión usted mismo. Ya estás tomando prestada la terminología de Knuth; también suministra los algoritmos de multiprecisión en los algoritmos seminuméricos.

Answer 3

Si es .NET, eche un vistazo a esta implementación de una clase BigInteger .

Answer 4

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