如何实现(快速)bigint部门？

Question

我正在创建自己的BigInt类,通过将数字分成7位数.(即基数10,000,000)

我实现了加法,减法和乘法,现在我正在实现除法和mod.我编写了一个代码,通过长除法进行除法(通过除以最高有效数字来估算数字),并且它有效.

但是,它太慢了.当我测试108位数和67位数的运算时,计算除法需要1.9ms,比其他运算慢得多(计算加法/减法0.007~0.008ms,计算乘法0.1ms).

与用于快速乘法的Karatsuba和FFT算法一样,存在用于计算除法的算法？维基百科演示了一些除法算法(计算除数的乘法逆,并将其乘以除数),但我认为这对我实施除法没有多大帮助.我也阅读了"大整数方法"部分,但这对我也没有帮助...... :(

Answer 1

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

如果有一个好的算法，这个库很可能就有它；它是在 LGPL 下分发的。