javascript - 如何实现(快速)bigint 划分？

Question

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

我实现了加法、减法和乘法，现在我正在实现除法和模。我编写了一个代码，通过长除法执行除法(通过除以最高有效数字来估计数字)，并且它有效。

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

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

Answer 1

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

顺便说一下，most people实现大整数运算的那些使用 2 的幂而不是 10 的幂作为其数字系统的基数。