找回密码
 欢迎注册
查看: 18472|回复: 10

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

[复制链接]
发表于 2013-4-29 19:33:10 | 显示全部楼层 |阅读模式

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

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

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

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-29 20:38:12 | 显示全部楼层
我也想知道。
不过,这个只对乘数非常大时,才有效果,如果程序只有几千位10进制数字,Toom算法是最好的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-30 16:39:35 | 显示全部楼层
当乘数相当大时,如亿位以上数量级,甚至10^100位以上,怎能用很短的时间内计算出来才是真正的突破。
我相信人类会找到更好的算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-14 14:29:57 | 显示全部楼层
好奇问一句,
这个和快速数论变换有什么不同?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-20 08:10:34 | 显示全部楼层
有关系吧,是2^n + 1形式的NTT
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 19:19 , Processed in 0.045716 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表