如何实现(快速)大整数除法？

Question

我正在制作自己的BigInt类，通过将数字按7位数分割（即在基数10,000,000中）。

我已经实现了加法、减法和乘法，现在正在实现除法和模运算。我编写了一段代码，通过长除法（通过除以最高位数字估计数字）执行除法，并且它可以工作。

然而，它太慢了。当我测试一个108位数字和一个67位数字的操作时，计算除法需要1.9毫秒，比其他操作慢得多（计算加法/减法需要0.007~0.008毫秒，计算乘法需要0.1毫秒）。

像Karatsuba和FFT算法用于快速乘法一样，有哪些算法可用于计算除法？Wikipedia演示了一些除法算法（计算除数的乘法逆元并将其与被除数相乘），但我认为这对我实现除法没有什么帮助。我也阅读了“大整数方法”部分，但那对我也没有帮助... :(

- JiminP

---

不错的问题，但你可以考虑访问 http://programmers.stackexchange.com 而不是 stackoverflow。 - Ben Lee

简单的谷歌搜索就可以展示出关于这个问题的大量文章，我认为这不是一项容易的工作，但主要思路是使用快速乘法，所有的算法都围绕着这个思路。例如，您可以查看《大整数的快速除法》（http://www.treskal.com/kalle/exjobb/original-report.pdf）。 - Saeed Amiri

你能开源这个吗？目前JS没有一个好的bigint库。 - Nico Burns

Answer 1

大整数算法的标准参考书是 Donald Knuth 的《计算机程序设计艺术》第2卷第4.3节。他的除法算法基本上是小学算法，但有一些小的改进。

顺便说一下，实现大整数算法的大多数人都使用的是一个二次方而不是十次方作为其数字系统的基数。

- user448810

Answer 2

我建议您查看GMP库的源代码，并将所需的功能移植到JavaScript中，或者了解它是如何完成的。如果有一个好的算法存在，这个库很可能已经包含了它；同时它还在LGPL下分发。

- copy

---

你也可以使用LLVM -> JavaScript (emscripten)编译器自动移植整个库。 - Raynos

@Raynos 我不会打赌使用 emscripten 的输出结果能够在 JS 中被调用而不会出现重大问题，特别是在不同版本的 emscripten 之间。 - user395760

我阅读了一些代码（divexact.c和divegcd.c），似乎包含了位运算，但由于我使用的是10^7进制表示数字，因此无法实现。 - JiminP

Answer 3

如果你需要一个相对快速的除法算法，可以看一下http://myweb.lmu.edu/dmsmith/MComp1996.pdf。

虽然它的时间复杂度仍为O(n^2)，但对于中等长度的数值非常高效。特别是当你使用的基数小于字长时，它表现得尤为出色。多年前，我在Python中实现了它。代码被埋藏在http://home.comcast.net/~casevh/decint_041.tar.gz中。寻找函数smithdiv()和remainder_norm()即可。

- casevh