GMP 正在使用的大数乘法算法 论文分析
最近在网上查资料，偶然得到一些比较有价值的论文，与大家分享一下，并希望能交流讨论下。附件一类似于一个ppt的演示文档：
附件二估计是个draft版本（撰写于 2007-01-24）：
附件三应该是个发表的最终版（因排版需要，似乎不及附件二那么便于阅读）：
附件四是我从附件二中截取的一张图片：
从中可看出 GMP 4.2.1 与 4.1.4 之间算法有很大提升，
并将有新的提升（但不知是否已导入到当前 GMP 最新的版本中去了）。 顺着论文里的参考链接，点：Magma V2.12-1 is up to 2.3 times faster than GMP for large integer multiplication
Opteron 150 (2.4GHz, L2 1MB)
NB: Both the GMP and the Magma timings here use the AMD64 assembly code of Pierrick Gaudry for the base operations (which is is vastly superior to the official GMP 4.1.4 running on AMD64 processors).
BitsGMPMagmaSpeedup2^180.003380.002381.422^190.009840.005311.852^200.02250.01141.972^210.05390.02741.962^220.1190.05922.012^230.2860.1322.172^240.6300.3002.102^251.510.6402.362^263.191.562.042^276.963.302.112^2815.278.541.792^2933.0417.671.87
Pentium 4 (2.66GHz, L2 512KB)
BitsGMPMagmaSpeedup2^170.005300.004451.192^180.01260.008061.562^190.03160.01911.662^200.08040.04002.012^210.1640.08901.842^220.4080.2051.992^230.9650.4252.272^241.901.171.622^253.782.471.532^267.985.781.382^2718.1412.151.492^2838.5430.881.252^2998.5465.511.50
Itanium 2 (1.5GHz)
BitsGMPMagmaSpeedup2^180.010340.005721.812^190.02200.01261.752^200.04820.02701.792^210.1100.05811.892^220.2660.1322.012^230.5980.3201.872^241.600.7822.042^253.081.701.812^266.664.331.542^2714.188.891.592^2830.5523.341.312^2969.9648.461.44
Ultrasparc (64-bit mode, 750MHz)
BitsGMPMagmaSpeedup2^180.03590.01961.832^190.08140.04251.922^200.1970.09462.082^210.4150.2032.042^221.070.4982.152^232.341.062.222^244.982.871.742^2510.246.081.682^2623.0315.851.452^2751.4332.801.572^28112.9085.041.332^29254.18175.031.45
这是该网站在 July 1, 2005 发布的测试结果。 正好在 2007-12-08 HugeCalc V8.0.0.0 版正式发布后，
也曾邀请大家将 HugeCalc 与 GMP 进行对比测试，
测试结果见：HugeCalc vs. GMP
当时打包的日期是 2008-02-28，当时 GMP 的版本应该为 GMP 4.2.2（2007-12-10 released）或更高。
从测试数据表明，
在规模比较大的大数乘法中，HugeCalc 逐渐超越 GMP，
单核超出不太明显，但多核超出很多，由风云剑提交的4核测试结果，HugeCalc 可提速 4.427 倍。
从我现有评估的64位版本 HugeCalc，将比32位版本的效率高更多，
因为将在64位平台下有些算法更容易实现及优化。 发这个帖子的目的不是为了讨论算法孰优孰劣，
而是想学习一下对方的算法究竟是如何的，
从而知己知彼。
我比较感兴趣的是它以“$sqrt(2)$ trick”（似乎 无心人 曾提到过），
但文中还有许多地方看得很朦胧，
希望明白人能指点一二，谢谢！ 你首先确定是FNT还是FFT 下载了论文的粗略的翻了下
似乎是mod 2^N + 1的FFT算法 我E文不行
谁给精简下
把其中的重点截取出来
:lol 原帖由 无心人 于 2009-3-23 08:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
下载了论文的粗略的翻了下
似乎是mod 2^N + 1的FFT算法
好像还讨论了 mod 2^N-1 的算法。
另外，请问 无心人，去年初你编译的 GMP 版本号是多少？ 去年初？
记不得了
好像是4.2.2或者4.2.3
呵呵 该文写于2007-01-24，
现在不清楚论文里的“new GMP code”是否已导入到其新版本中去了，
也就是说我们当时对比测试的 GMP，
不知是属于那根蓝线还是那根紫红线？:Q:
（但可以肯定排除那根红线）
页:
[1]
2