大数除法

Question

除了学校方法之外，还有其他更快的大整数（1000位或更多）除法方法吗？

Answer 1

维基百科列出了多种除法算法。请参阅数学运算的计算复杂性，其中列出了教科书长除法 为 O(n^2) 和 牛顿法为M(n) 其中 M 是所使用乘法算法的复杂度，可能与 O(n log n 2^(log*n)) 渐近。

请注意一种乘法算法的讨论对于“小”输入，最好的渐近算法不一定是最快的：

在实践中，对于超过 2^(2^15) 到 2^(2^17)（10,000 到 40,000 个十进制数字）的数字，Schönhage–Strassen 算法开始优于旧方法，例如 Karatsuba 和 Toom–Cook 乘法。 GNU 多精度库将其用于至少 1728 到 7808 64 位字（111,000 到 500,000 个十进制数字）的值，具体取决于体系结构。 Schönhage–Strassen 有一个 Java 实现，它使用超过 74,000 位十进制数字。