什么是用于大整数除法的最快算法？

Question

我需要将以字节数组表示的数字以非标准数量的字节进行划分。它可能是5个字节，也可能是1GB或更多。划分应该使用以字节数组表示的数字进行，而不需要将其转换为数字。

- Kosmo零

---

类似于Java的BigInteger（http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html）的东西？ - Bernhard Barker

巴雷特约简计算的是模数，而不是商数。 - Tyler Durden

对于这样的通用问题，您应该使用维基百科，在阅读维基百科并尝试了解后再来这里。 - Tyler Durden

维基百科上没有回答最快的问题。我不需要运行数天的部门。 - Kosmo零

@Tyler：...它通过首先计算商，然后减去除数的适当倍数来获得余数。 - user1084944

Answer 1

分治方法在处理大整数时要比传统的学校算法快得多。

GMP 是一款先进的大整数库，它为几乎所有的操作提供了针对特定操作数大小的不同算法实现。

这里 是GMP关于“除法算法”的文档。虽然算法描述略显简洁，但至少可以让你搜索更多信息。

Brent和Zimmermann的《现代计算机算术》 是一本关于大整数算术理论和实现的好书。如果你想知道已知的内容，那么阅读这本书可能是值得的。

- tmyklebu

---

是的，但是......就像我说的那样，这些算法比D算法复杂得多。采用分治策略的主要原因是可以使用Karatsuba算法，而且让我告诉你，编写所有这些加上Karatsuba实现将需要大量的工作，我的意思是非常非常多的工作。我不知道OP是一个好程序员吗，但即使是非常好的程序员也可能花费数月时间编写正确的分治实现。 - Tyler Durden

@TylerDurden：嗯，他问到了“疯狂大的数字”。Karatsuba本身并不差，因为你不会遇到2的幂问题。当你开始想要实现Toom-Cook和各种基于FFT的方法时，它就开始变得很麻烦了，然后需要找出交叉点。这就是为什么你要使用GMP :) - tmyklebu

@TylerDurden：一旦你有了快速乘法黑盒，分治法并不太难。取分子和分母的高半部分，递归地进行除法，然后稍作清理即可。再次强调，调整和找到传统算法与分治法之间的交叉点需要相当多的工作。 - tmyklebu

Answer 2

标准长除法算法类似于小学长除法，被称为D算法，在Knuth 4.3.1中进行了描述。Knuth在他的书的这一部分对除法进行了广泛的讨论。结果是，确实有比D算法更快的方法，但它们的速度提升不是很大，而且它们比D算法复杂得多。

如果你决定要获得最快的算法，可以使用所谓的SRT算法。

另外，维基百科的除法算法页面上也包含了以上内容以及更多其他信息。

- Tyler Durden

---

在维基百科链接中列出的算法中，您可能会发现长除法最有用。但要注意符号。**D(0)表示数字中最低有效值，而左移则表明数字以大端方式存储（这意味着LSD应该在D(n-1)**）。 - Python Cheese