3

我想知道什么是大数字，以及用于处理它们的一些常用算法是什么。我在 Coders at Work 中听到过这个词，在一次采访中，有人要求我创建一个库来处理大数字。

4

3 回答 3

5

大数通常是全精度整数或小数，而不是浮点数（它也可以存储非常大的数字，但精度非常有限）。它们主要用于密码学。以 RSA 密钥为例：它们是 1024 或 2048 位的整数（大约 300 或 600 个十进制数字）。它们需要很长才能使使用蛮力计算破解加密变得不可行。

库需要提供的是支持存储这些数字并对其执行计算（例如加法、乘法、整数除法和余数）

于 2010-01-15T13:03:27.287 回答
2

有像 gmp 这样的 bignum 库 - 有些提供任意精度（......尽可能多的内存可以处理），有些有简单的可笑限制 - 256 字节基数的浮点变量，256 字节尾数。

这些方法与 FPU 的普通软件仿真非常相似，只是为每次计算迭代更多字节的数据，操作类似于您在纸上计算的方式。如果您有 256 字节整数，则可以将其视为普通的 256 base256 数字...

简单的 256 字节整数加法（完全未优化...数字应保持长度等）

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;
}
于 2010-01-15T13:20:24.303 回答
1

这些是具有可变位长度的数字，与具有预定义大小的数字（例如 4 位整数类型）不同。

NTL是处理大数的快速 C++ 库的一个示例，它也特别用于数论和密码学应用程序。另一个著名的工具是 unix bc计算器，它默认以无限精度工作。像 Haskell 这样的一些函数式语言也使用这种类型的数字。

用于处理大量算术的方法示例是用于乘法的Karatsuba 算法。如果您有兴趣，可以在 NTL 的文档中找到更多信息；）

于 2010-01-15T13:07:47.577 回答