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

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

5 голосов
/ 27 ноября 2009

Я представляю бесконечно точное целое число в виде массива беззнаковых целочисленных значений для обработки в графическом процессоре. В целях отладки я хотел бы вывести базовое 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);

Какие-либо предложения о том, как подойти к этой проблеме?

Редактировать: вот полная реализация благодаря 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);
}

Ответы [ 4 ]

4 голосов
/ 27 ноября 2009

Если у вас есть доступ к 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 () и reverse () осталось реализовать. divBy10 делит на 10 и возвращает остаток.

4 голосов
/ 27 ноября 2009

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

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

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

3 голосов
/ 27 ноября 2009

Если это .NET, взгляните на эту реализацию класса BigInteger .

0 голосов
/ 27 ноября 2009

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

...