如何实现（快速）bigint 除法？
我目前正在制作自己的 BigInt 类，通过将数字分割为 7 位数字。 （即以 10,000,000 为基数）
我实现了加法、减法和乘法，现在我正在实现除法和取模。我编写了一个执行长除法除法的代码（通过除以最高有效位来估计数字），并且它有效。
然而，它太慢了。当我测试108位数字和67位数字的运算时，计算除法需要1.9ms，比其他运算慢得多（计算加减法0.007~0.008ms，计算乘法0.1ms）。
与用于快速乘法的 Karasuba 和 FFT 算法一样，存在哪些计算除法的算法？ Wikipedia 演示了一些除法算法（计算除数的乘法逆元并将其与被除数相乘） ），但我认为这对我实施划分没有多大帮助。我也读了“大整数方法”部分，但这对我也没有帮助......:(
I'm currently making my own BigInt class, by splitting numbers by 7 digits. (i.e. in base 10,000,000)
I implemented addition, subtraction, and multiplication, and now I'm implementing division and mod. I wrote a code that performs division by long division (estimating numbers by dividing most-significant digits), and it works.
However, it is too slow. When I test operations on a 108-digit number and a 67-digit number, it takes 1.9ms to calculate division, much slower than other operations (0.007~0.008ms to calculate addition/subtraction, 0.1ms to calculate multiplication).
Like Karatsuba and FFT algorithm for fast multiplication, what algorithms exist for calculating division? Wikipedia demonstrates some division algorithm (which calculates multiplicative inverse of divisor and multiplies it with dividend), but I think that doesn't help me much implementing division. I read the 'Large Integer Methods' sections too but that doesn't help me neither... :(
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
大整数算术的标准参考是 Donald Knuth 的书计算机编程艺术，第 2 卷，第 4.3 节。他的除法算法基本上是小学算法，有一些小的改进。
顺便说一句，大多数人都实现了大整数算术使用二的幂而不是十的幂作为其数字系统的基数。
The standard reference for big-integer arithmetic is Donald Knuth's book Art of Computer Programming, Volume 2, Section 4.3. His division algorithm is basically the grade-school algorithm, with some small improvements.
By the way, most people that implement big-integer arithmetic use a power of two rather than a power of ten as the radix of their number system.
我建议您查看 GMP 库 的源代码，并将您需要的功能移植到 JavaScript，或者了解它是如何完成的。
如果有好的算法，这个库很可能就有；它是在 LGPL 下分发的。
I'd suggest you have a look at the source code of the GMP library and port the functionality you need to JavaScript, or get an idea of how it's done.
If there is a good algorithm out there, this library will most likely have it; and it is distributed under the LGPL.