biginteger - 大数除法

Question

除学校方法外，除大整数(1000 位或更多)有没有更快的方法？

Answer 1

维基百科列出 multiple division algorithms .参见 Computational complexity of mathematical operations其中列出了 Schoolbook long division作为 O(n^2) 和 Newton's method as M(n) 其中 M 是所用乘法算法的复杂度，它可能与 O(n log n 2^( log* n)) 渐近。

来自 one of the multiplication algorithms 的讨论的注释对于“小”输入，最好的渐近算法不一定是最快的:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal digits). The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (111,000 to 500,000 decimal digits), depending on architecture. There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits.