大数除法 [英] Division of Large numbers

问题描述

除了学习方法以外，还有没有更快的方法来对大整数(具有1000位或更多)进行除法?

Is there any faster method for division of large integers(having 1000 digits or more) other than the school method?

推荐答案

维基百科列出了多重划分算法.请参阅数学运算的计算复杂度，其中列出了

Wikipedia lists multiple division algorithms. See Computational complexity of mathematical operations which lists Schoolbook long division as O(n^2) and Newton's method as M(n) where M is the complexity of the multiplication algorithm used, which could be as good as O(n log n 2^(log*n)) asymptotically.

有关其中一种乘法算法的讨论的注释对于小"输入，渐近最佳算法不一定是最快算法:

Note from the discussion of one of the multiplication algorithms that the best algorithm asymptotically is not necessarily the fastest for "small" inputs:

实际上，对于超出2 ^(2 ^ 15)到2 ^(2 ^ 17)(10,000到40,000个十进制数字)的数字，Schönhage–Strassen算法开始优于旧方法(例如Karatsuba和Toom–Cook乘法). GNU Multi-Precision库将它用于至少1728至7808个64位字(111,000至500,000个十进制数字)的值，具体取决于体系结构.有一个Schönhage–Strassen的Java实现，它在74,000个十进制数字以上使用它.

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.

这篇关于大数除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！