代码之家 › 专栏 › 技术社区 › Rich

将无限长基数2^32数字转换为可打印基数10的算法

largenumber decimal c

Rich · 技术社区 · 16 年前

我将一个无限精确的整数表示为在GPU上处理的无符号整数数组。出于调试的目的,我想打印其中一个数字的以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);

#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 回复 | 直到 14 年前

Gunther Piez 16 年前

如果您可以使用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()有待实现。divideBy10除以10并返回余数。

Ira Baxter 16 年前

基本上,您需要使用数字生成进行经典的十进制打印,方法是重复将数字除以10(基数为2^32),并将余数用作数字。你可能没有一个除以(任何东西,更不用说)10的例行程序,这可能是你的问题的关键来源。

如果你在C或C++中工作,你可以从中得到一个完整的无穷精度算术包。 GNU Bignum package . 大多数其他广泛使用的语言都有类似的软件包。

当然,如果您有太多的空闲时间,您可以自己实现多精度除法。你已经借用了克努斯的术语;他还提供了半数值算法中的多精度算法。

Konamiman 16 年前

如果是.NET,请查看 this implementation of a BigInteger class .

Fred 16 年前

用长双打怎么样?然后尾数中有80位,但我猜当使用浮点数时,精度会降低。