GMP 正在使用的大数乘法算法论文分析

gxqcn · 发表于 2009-3-22 21:24:34

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

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

×

最近在网上查资料，偶然得到一些比较有价值的论文，与大家分享一下，并希望能交流讨论下。

附件一类似于一个ppt的演示文档：

kruppa-slides.pdf (324.09 KB, 下载次数: 51)

附件二估计是个draft版本（撰写于 2007-01-24）：

fft.pdf (278.86 KB, 下载次数: 22)

附件三应该是个发表的最终版（因排版需要，似乎不及附件二那么便于阅读）：

fft.final.pdf (253.01 KB, 下载次数: 15)

附件四是我从附件二中截取的一张图片：

test chart

从中可看出 GMP 4.2.1 与 4.1.4 之间算法有很大提升，
并将有新的提升（但不知是否已导入到当前 GMP 最新的版本中去了）。

gxqcn · 发表于 2009-3-22 21:32:37

顺着论文里的参考链接，点：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).

Bits GMP Magma Speedup
2^18 0.00338 0.00238 1.42
2^19 0.00984 0.00531 1.85
2^20 0.0225 0.0114 1.97
2^21 0.0539 0.0274 1.96
2^22 0.119 0.0592 2.01
2^23 0.286 0.132 2.17
2^24 0.630 0.300 2.10
2^25 1.51 0.640 2.36
2^26 3.19 1.56 2.04
2^27 6.96 3.30 2.11
2^28 15.27 8.54 1.79
2^29 33.04 17.67 1.87

Pentium 4 (2.66GHz, L2 512KB)

Bits GMP Magma Speedup
2^17 0.00530 0.00445 1.19
2^18 0.0126 0.00806 1.56
2^19 0.0316 0.0191 1.66
2^20 0.0804 0.0400 2.01
2^21 0.164 0.0890 1.84
2^22 0.408 0.205 1.99
2^23 0.965 0.425 2.27
2^24 1.90 1.17 1.62
2^25 3.78 2.47 1.53
2^26 7.98 5.78 1.38
2^27 18.14 12.15 1.49
2^28 38.54 30.88 1.25
2^29 98.54 65.51 1.50

Itanium 2 (1.5GHz)

Bits GMP Magma Speedup
2^18 0.01034 0.00572 1.81
2^19 0.0220 0.0126 1.75
2^20 0.0482 0.0270 1.79
2^21 0.110 0.0581 1.89
2^22 0.266 0.132 2.01
2^23 0.598 0.320 1.87
2^24 1.60 0.782 2.04
2^25 3.08 1.70 1.81
2^26 6.66 4.33 1.54
2^27 14.18 8.89 1.59
2^28 30.55 23.34 1.31
2^29 69.96 48.46 1.44

Ultrasparc (64-bit mode, 750MHz)

Bits GMP Magma Speedup
2^18 0.0359 0.0196 1.83
2^19 0.0814 0.0425 1.92
2^20 0.197 0.0946 2.08
2^21 0.415 0.203 2.04
2^22 1.07 0.498 2.15
2^23 2.34 1.06 2.22
2^24 4.98 2.87 1.74
2^25 10.24 6.08 1.68
2^26 23.03 15.85 1.45
2^27 51.43 32.80 1.57
2^28 112.90 85.04 1.33
2^29 254.18 175.03 1.45

这是该网站在 July 1, 2005 发布的测试结果。

gxqcn · 发表于 2009-3-22 21:51:48

正好在 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位平台下有些算法更容易实现及优化。

gxqcn · 发表于 2009-3-22 21:57:57

发这个帖子的目的不是为了讨论算法孰优孰劣，
而是想学习一下对方的算法究竟是如何的，
从而知己知彼。

我比较感兴趣的是它以“$sqrt(2)$ trick”（似乎无心人曾提到过），
但文中还有许多地方看得很朦胧，
希望明白人能指点一二，谢谢！

无心人 · 发表于 2009-3-23 08:28:37

你首先确定是FNT还是FFT

无心人 · 发表于 2009-3-23 08:53:58

下载了论文的粗略的翻了下
似乎是mod 2^N + 1的FFT算法

无心人 · 发表于 2009-3-23 08:57:55

我E文不行

谁给精简下
把其中的重点截取出来

gxqcn · 发表于 2009-3-23 09:52:04

原帖由 无心人 于 2009-3-23 08:53 发表
下载了论文的粗略的翻了下
似乎是mod 2^N + 1的FFT算法

好像还讨论了 mod 2^N-1 的算法。

另外，请问 无心人，去年初你编译的 GMP 版本号是多少？

无心人 · 发表于 2009-3-23 09:56:44

去年初？
记不得了

好像是4.2.2或者4.2.3
呵呵

gxqcn · 发表于 2009-3-23 10:20:12

该文写于2007-01-24，
现在不清楚论文里的“new GMP code”是否已导入到其新版本中去了，
也就是说我们当时对比测试的 GMP，
不知是属于那根蓝线还是那根紫红线？

（但可以肯定排除那根红线）

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

[讨论] GMP 正在使用的大数乘法算法 论文分析

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

[讨论] GMP 正在使用的大数乘法算法论文分析