biginteger – 大数分部
除了学校方法之外,还有更快的方法来划分大整数(1000位或更多)吗?
解决方法
维基百科列出
multiple division algorithms.见
Computational complexity of mathematical operations,其中
Schoolbook long division为O(n ^ 2),Newton’s method为M(n),其中M是所用乘法算法的复杂度,可以与O一样好(n log n 2 ^(
log* n)渐渐地.
从one of the multiplication algorithms的讨论中注意到,渐近的最佳算法不一定是“小”输入的最快算法:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |