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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

正在做关于大数乘法的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

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

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

http://en.wikipedia.org/wiki/Sch ... 3Strassen_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

账号		自动登录	找回密码
密码			欢迎注册

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分