Алгоритм преобразования бесконечно длинной базы 2^32 числа для печати базы 10

Question

Я представляю бесконечно точное целое число в виде массива беззнаковых целых чисел для обработки на графическом процессоре. Для целей отладки я хотел бы напечатать базовое представление 10 одного из этих чисел, но у меня трудности с обволакиванием вокруг него. Вот что я хотел бы сделать:

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

Любые предложения по решению этой проблемы?

Edit: Вот полная реализация благодаря 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

Если у вас есть доступ к 64-разрядной арифметике, это проще. Я хотел бы сделать что-то вдоль линии:

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() и обратный() слева будет реализован. divideBy10 делит на 10 и возвращает остаток.

Answer 2

Если .NET, посмотрите на this implementation of a BigInteger class.

Answer 3

В основном вам нужна классическая десятичная печать с использованием производства цифр, деля число на десять (в вашей базе 2^32) несколько раз и используя остаток в виде цифр. У вас может не быть деления на (всего, не говоря уже) 10 рутинных, что, вероятно, является ключевым источником вашей проблемы.

Если вы работаете на C или C++, вы можете получить полный арифметический пакет с бесконечной точностью от GNU Bignum package. Большинство других широко используемых языков имеют похожие пакеты.

Конечно, если у вас слишком много свободного времени, вы всегда можете реализовать раздельное разделение. Вы уже заимствуете терминологию у Кнута; он также поставляет алгоритмы многоточия в семинумерных алгоритмах.

Answer 4

Как насчет использования длинных парных? Тогда вы получаете 80 бит в мантиссе, но я думаю, что точность теряется при использовании чисел с плавающей запятой.