维基百科列出了多种划分算法.见计算数学运算的复杂性,其中列出教科书长除法是O(n^2)和牛顿法作为M(n)其中M是用乘法算法,这可能是一样好复杂渐近.O(n log n 2^(log*n))
从一个乘法算法的讨论中注意到,渐近最佳算法不一定是"小"输入的最快算法:
在实践中,Schönhage-Strassen算法开始优于旧方法,例如Karatsuba和Toom-Cook乘法,数字超过2 ^(2 ^ 15)到2 ^(2 ^ 17)(10,000到40,000十进制数字).GNU多精度库使用它作为至少1728到7808个64位字(111,000到500,000十进制数字)的值,具体取决于体系结构.Schönhage-Strassen有一个Java实现,它使用了超过74,000个十进制数字.
| 归档时间： |
|
| 查看次数： |
5655 次 |
| 最近记录： |