20

我目前正在制作自己的 BigInt 类，将数字分成 7 位数字。（即以 10,000,000 为基数）

我实现了加法、减法和乘法，现在我正在实现除法和取模。我编写了一个执行长除法除法的代码（通过除以最高有效数字来估计数字），它可以工作。

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

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

4

3 回答 3

3

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

顺便说一句，大多数实现大整数算术的人使用 2 的幂而不是 10 的幂作为他们数字系统的基数。

于 2012-01-16T20:37:11.197 回答
2

我建议您查看GMP 库的源代码并将您需要的功能移植到 JavaScript，或者了解它是如何完成的。

如果那里有一个好的算法，这个库很可能会有它；它是根据 LGPL 分发的。

于 2012-01-16T17:34:19.840 回答
1

对于相当快的除法算法，请查看http://myweb.lmu.edu/dmsmith/MComp1996.pdf

它仍然是 O(n^2) 但对于中等长度是有效的。当您使用小于字长的碱基时，它特别适合。几年前，我用 Python 实现了它。代码隐藏在http://home.comcast.net/~casevh/decint_041.tar.gz中。寻找函数smithdiv() 和remainder_norm()。

于 2012-01-17T16:46:42.140 回答