我想知道什么是大数,并且有哪些常见算法用于处理它们。在《程序员面试金典》一书中,我听说有人被要求在面试中创建一个用于处理大数的库。
我想知道什么是大数,并且有哪些常见算法用于处理它们。在《程序员面试金典》一书中,我听说有人被要求在面试中创建一个用于处理大数的库。
unsigned char x[256];
unsigned char y[256];
unsigned char sum[256];
int overflow=0,tmp;
for(unsigned char i=0;i<256;i++)
{
tmp = x[i] + y[i] + ovr;
sum[i] = tmp % 256;
overflow = tmp / 256;
}
这些是具有可变位长度的数字,不同于具有预定义大小的数字(例如4位整数类型)。
一个快速处理大数值的C++库的例子是NTL,特别适用于数论和密码应用。另一个众所周知的工具是unix的bc计算器,默认情况下可以处理无限精度。一些函数式语言如Haskell也使用此类数字。
用于处理大数算术的方法之一是Karatsuba算法用于乘法。如果您感兴趣,在NTL的文档中可以找到更多信息 ;)