2705101026 发表于 2013-4-29 19:33:10

关于大数乘法的Schönhage-Strassen算法，求指点

正在做关于大数乘法的Schönhage-Strassen算法，有谁做过吗或者是谁了解这个算法的，求指点。。。

liangbch 发表于 2013-4-29 20:38:12

我也想知道。
不过，这个只对乘数非常大时，才有效果，如果程序只有几千位10进制数字，Toom算法是最好的。

云梦 发表于 2013-4-30 16:39:35

当乘数相当大时，如亿位以上数量级，甚至10^100位以上，怎能用很短的时间内计算出来才是真正的突破。
我相信人类会找到更好的算法。

qianyb 发表于 2013-5-3 17:49:45

http://hi.baidu.com/ustc_likai/item/e37fedad57386215a8cfb7c2
Schönhage–Strassen算法

该算法的思想与Toom-cook算法有一点相似，它不划分A(x)与B(x)，如果可以直接找出2n-1个点pk以及计算出A(pk)和B(pk)，则同样得到了pk与C(pk)，再还原出系数即可。
取这2n-1个点为单位复根，把多项式从系数表示转化到点对表示以及由点对表示还原到系数表示采用了FFT。FFT的复杂度是O(nlogn)，中间的点乘是Θ(n)，所以总体复杂度为O(nlogn)

无心人 发表于 2013-5-4 14:37:01

当乘数相当大时，如亿位以上数量级，甚至10^100位以上，怎能用很短的时间内计算出来才是真正的突破。
我相信人类会找到更好的算法。
云梦 发表于 2013-4-30 16:39 http://bbs.emath.ac.cn/images/common/back.gif


超大的长度的乘法，现有宇宙是无法表示这么大数字的，也无法在宇宙灭亡前计算出来

无心人 发表于 2013-5-5 08:14:28

http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

感觉是基于NTT的算法，
这个有中文书可以找的

无心人 发表于 2013-5-5 08:19:14

http://www.numberworld.org/y-cruncher/algorithms.html

这个页面讨论了很多算法，
y-cruncher貌似是一个闭源数学工具

无心人 发表于 2013-5-5 08:45:08

据说这个Fürer's algorithm算法当整数超大时候比Schönhage-Strassen好

knate 发表于 2013-5-14 14:29:57

好奇问一句,
这个和快速数论变换有什么不同?

无心人 发表于 2013-5-20 08:10:34

有关系吧，是2^n + 1形式的NTT
页: [1] 2
查看完整版本: 关于大数乘法的Schönhage-Strassen算法，求指点