将无限长基数 2^32 数字转换为可打印基数 10 的算法
我将无限精确的整数表示为无符号整数数组,以便在 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);
关于如何解决这个问题有什么建议吗?
编辑:这是一个完整的实现,感谢 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);
}
I'm representing an infinitely precise integer as an array of unsigned ints for processing on a GPU. For debugging purposes I'd like to print the base 10 representation of one of these numbers, but am having difficulty wrapping my head around it. Here's what I'd like to do:
//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);
Any suggestions on how to approach this problem?
Edit: Here's a complete implementation thanks to 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);
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
如果您可以访问 64 位算术,那就更容易了。我会做一些事情:
isEqual() 和reverse() 需要实现。 divideBy10 除以 10 并返回余数。
If you have access to 64 bit arithmetic, it is easier. I would do something along the line of:
isEqual() and reverse() left to be implemented. divideBy10 divides by 10 and returns the remainder.
从根本上讲,您需要使用数字生成进行经典的十进制打印,方法是将您的数字重复除以十(以您的基数 2^32 为单位)并将余数用作数字。您可能没有除以(任何东西,更不用说)10 的例程,这可能是问题的关键根源。
如果您使用 C 或 C++,您可以从 GNU Bignum 包 获得完整的无限精度算术包。大多数其他广泛使用的语言都有类似的可用包。
当然,如果你有太多的空闲时间,你总是可以自己实现多精度除法。你已经从 Knuth 那里借用了术语;他还在半数值算法中提供了多精度算法。
Fundamentally you need classic decimal printing using digit production by dividing your number by ten (in your base 2^32) repeatedly and using the remainder as digits. You may not have a divide by (anything, let alone) 10 routine, which is probably the key source of your problem.
If you are working in C or C++, you can get a complete infinite precision arithmetic package from GNU Bignum package. Most other widely used languages have similar packages available.
Of course, if you have too much free time, you can always implement multiprecision division yourself. You're already borrowing terminology from Knuth; he also supplies the multiprecision algorithms in Seminumerical Algorithms.
如果是 .NET,请查看 BigInteger 类的此实现。
If it is .NET, take a look at this implementation of a BigInteger class.
使用长双打怎么样?然后你在尾数中得到 80 位,但我猜使用浮点数时精度会丢失。
How about using long doubles? Then you get 80bits in the mantissa, but I guess that the accuracy is lost when using floating point numbers.