大数，常见算法？

Question

我想知道什么是大数，并且有哪些常见算法用于处理它们。在《程序员面试金典》一书中，我听说有人被要求在面试中创建一个用于处理大数的库。

- cam

---

相关链接：https://dev59.com/DErSa4cB1Zd3GeqPTREk无需转换即可输入非常长的数字的编程语言是什么？ - jldupont

Answer 1

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

库需要提供支持来存储这些数字并对它们执行计算（例如加法、乘法、带余数的整数除法）。

- Thilo

---

啊，谢谢。完全精度和浮点数之间有什么区别？ - cam

浮点数也有预定义的存储大小，例如4或8个字节，它们保存了有效数字，完全精度意味着真正无限的大小。 - Tomas Vana

基本上，一个完全精度的有理数R是由两个大数字N和M的比值N/M得到的。这仍然不允许您表示像e、pi和sqrt(2)这样的无理数，但您可以无限接近它们。 - Vatine

Answer 2

有一些大整数库，例如gmp - 有些提供任意精度（...只要你的内存能处理），有些则具有荒谬的限制 - 基于256字节底数和256字节尾数的浮点变量。

这些方法与FPU的正常软件模拟非常相似，只是对每个计算迭代了更多的数据字节，操作类似于您在纸上计算的方式。如果你有一个256字节的整数，它可以被视为一个普通的256进制数字...

简单的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;
}

- SF.

Answer 3

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

一个快速处理大数值的C++库的例子是NTL，特别适用于数论和密码应用。另一个众所周知的工具是unix的bc计算器，默认情况下可以处理无限精度。一些函数式语言如Haskell也使用此类数字。

用于处理大数算术的方法之一是Karatsuba算法用于乘法。如果您感兴趣，在NTL的文档中可以找到更多信息 ;)

- Tomas Vana