论坛 › 算法交流 › Toom-Cook 乘法

无心人 发表于 2013-5-8 16:59:29

9# 云梦

有，就是并行算法。。。。

liangbch 发表于 2017-1-4 16:42:11

最近学习了下Toom-Cook算法，贴出一些相关的论文。

liangbch 发表于 2017-1-4 16:52:23

论文
作者
摘要
重要性
备注

ToomCook.pdf
Sai Krishna Yedugani
Toom-cook算法入门
中


WhatAboutToomCookMatricesOptimality.pdf
Marco Bodrato 和 AlbertoZanoni
讲述Toom算法优化的
高
最有用的矩阵变换序列,可以利用这些数据写出自己的Toom2.5,toom3,toom3.5,toom4,toom4.5,toom5算法

iterativeToomCookForVeryUnbalancedMultiplication.pdf
Alberto Zanoni
讲述非平衡Toom算法的
低


Toom-Cook_8-way_for_Long_Integers_Multiplication.pdf
Alberto Zanoni
给出一个Toom8路乘法的实现
低
是一个非最优化的实现,效率不Marco Bodrato的Toom8h

Integer_and_polynomial_multiplication_towards_optimal_toom-cook_matrices.pdf
Marco Bodrato和Alberto Zanoni
给出查找在Toom算法中interpolation阶段用到的最优矩阵变换序列的方法。
高.
内容相对艰深。

High_degree_Toom_n_half_for_balanced_and_unbalanced_multiplication.pdf
Marco Bodrato
作者提出一种效率很高的高阶Toom6.5, Toom8.5的实现方法。此算法已经在GMP 5.0中实现。
高
有较大的适用价值，欲看懂GMP中Toom6h和TOOM8h算法，必看此文。

Bodrato2007-OptimalToomCookMultiplicationForBinaryFieldAndIntegers.pdf
Marco Bodrato
讲述GF(2)上的多项式乘法的Toom算法
低


Madrid2007-Toom-Cook-inGF2x.pdf
Marco Bodrato
主要涉及Toom3算法
低
应用于GF(2)上多项式乘法.内容较少,像一个PPT而不像正规论文

SmallCharacteristicLowDegreeToom.pdf
Marco Bodrato
讲优化低阶Toom算法在有限域上的多项式乘法
低

gxqcn 发表于 2017-1-4 17:00:42

感谢贴出它们的评价，抽空将仔细阅读一下

liangbch 发表于 2017-1-4 17:26:40

在gmp源码树tune目录下运行make,可以build出2个应用程序，其中speed可用来测试一些GMP函数的性能。我特地测试并分析了GMP乘法函数的性能。

说明：
1.硬件 Intel I7-4700HQ @2.40GHz, 8G RAM
2.操作系统，windows7,64bit
3.用MinGW32编译GMP的最新源代码6.1.2,以32位方式编译。
4.我使用命令行 speed -C -E -s size 函数名 来测试GMP函数的运行速度，例
speed -C -E -s 128 mpn_toom22_mul
参数说明，-C指定时间的单位为 每个操作步的周期数，-E 指定时间周期的计算方式为总时间/(size*size). 上面的命令表示调用GMP函数mpn_toom22_mul计算2个128个limb的整数的乘法，时间为总始终周期除以(128*128)，这里1个limb表示32比特。
5. 测试方法为，同一命令运行3次，取3次中的最小值。

用单位时间而不用总时间的好处是可以直观的评价各个函数的性能或者加速比。我首先测试了mpn_mul_basecase函数的性能（见下）s从1000到10000，测试结果显示，平均每步的计算时间稳定在1.51到1.64个时钟周期. 我们取平均值1.55.

speed -C -E -s 1000mpn_mul_basecase
1000         1.5151
2000         1.5154
3000         1.5093
4000         1.5212
5000         1.5406
6000         1.5437
7000         1.5774
8000         1.5608
9000         1.6486
10000          1.5613

然后我分别测试当size为 6000-12000之间时，mpn_mul_n和mpn_toom8h_mul性能数据，发现，当size为12000以上时，mpn_mul_n明显更快，这说明，当size为12000以上时，进入FFT算法的势力范围，toom算法的效率明显低于FFT算法，故我只测试size为128到16384之间（size为等比数列，公比为2的8分之1）各个toom函数的性能，各个toom算法的性能指标。

liangbch 发表于 2017-1-4 17:31:37

len        basecase        toom22        toom33        toom44        toom6h        toom8h        toom22        toom33        toom44        toom6h        toom8h
128        1.55        1.0726        1.0748        1.1168        1.3522        1.5908        1.445086705        1.442128768        1.387893983        1.146280136        0.974352527
140        1.55        1.0324        0.9877        1.0396        1.247        1.4689        1.501356064        1.56930242        1.490958061        1.24298316        1.055211383
153        1.55        0.9954        0.9513        1.0017        1.062        1.3515        1.55716295        1.629349311        1.547369472        1.459510358        1.146873844
166        1.55        0.9695        0.9054        0.9261        1.0478        1.1872        1.598762249        1.711950519        1.673685347        1.479289941        1.305592992
182        1.55        0.927        0.8554        0.9068        0.947        1.0571        1.67206041        1.812017769        1.709307455        1.636747624        1.46627566
198        1.55        0.8952        0.8456        0.86        0.8885        1.0031        1.731456658        1.833017975        1.802325581        1.744513225        1.545209849
216        1.55        0.8637        0.7785        0.8161        0.8144        0.9161        1.794604608        1.991008349        1.899277049        1.90324165        1.691955027
235        1.55        0.8331        0.7565        0.7663        0.8237        0.8842        1.860520946        2.048909451        2.022706512        1.881753065        1.752997059
256        1.55        0.7801        0.7568        0.7279        0.7584        0.8001        1.986924753        2.048097252        2.129413381        2.043776371        1.937257843
280        1.55        0.7597        0.7011        0.697        0.7119        0.7402        2.040279058        2.210811582        2.223816356        2.177272089        2.094028641
305        1.55        0.7099        0.6973        0.6716        0.6556        0.7185        2.183406114        2.222859601        2.307921382        2.364246492        2.157272095
332        1.55        0.7171        0.6604        0.6406        0.6483        0.6718        2.161483754        2.347062386        2.419606619        2.390868425        2.307234296
363        1.55        0.6909        0.6179        0.6133        0.5931        0.6303        2.243450572        2.50849652        2.527311267        2.613387287        2.459146438
395        1.55        0.6706        0.6121        0.5938        0.5711        0.5969        2.311362959        2.53226597        2.610306501        2.714060585        2.596749874
431        1.55        0.6458        0.584        0.5438        0.5376        0.5554        2.400123877        2.654109589        2.850312615        2.883184524        2.790781419
470        1.55        0.6348        0.5544        0.5375        0.517        0.5178        2.441713926        2.795815296        2.88372093        2.998065764        2.993433758
512        1.55        0.5713        0.5324        0.4921        0.5007        0.4786        2.71311045        2.911344853        3.149766308        3.095666068        3.23861262
559        1.55        0.5703        0.5282        0.4851        0.4627        0.4627        2.717867789        2.93449451        3.195217481        3.349902745        3.349902745
609        1.55        0.5504        0.5108        0.4558        0.4478        0.4454        2.816133721        3.034455756        3.400614305        3.461366682        3.480017961
664        1.55        0.5395        0.491        0.4302        0.4254        0.4136        2.873030584        3.156822811        3.60297536        3.643629525        3.747582205
725        1.55        0.522        0.4555        0.4091        0.401        0.3964        2.969348659        3.402854007        3.788804693        3.865336658        3.910191726
790        1.55        0.49        0.4382        0.3906        0.3832        0.3776        3.163265306        3.537197627        3.968253968        4.044885177        4.104872881
862        1.55        0.4733        0.4322        0.385        0.3653        0.3543        3.274878513        3.586302638        4.025974026        4.243087873        4.374823596
940        1.55        0.4687        0.425        0.3679        0.348        0.329        3.307019415        3.647058824        4.213101386        4.454022989        4.711246201
1024        1.55        0.4423        0.4085        0.356        0.3339        0.3176        3.504408772        3.794369645        4.353932584        4.642108416        4.880352645
1117        1.55        0.4174        0.3939        0.3411        0.3156        0.3031        3.713464303        3.935008886        4.544121958        4.911280101        5.113823821
1218        1.55        0.4148        0.3808        0.3178        0.2999        0.292        3.736740598        4.070378151        4.877281309        5.168389463        5.308219178
1328        1.55        0.4066        0.368        0.3112        0.2857        0.2795        3.812100344        4.211956522        4.980719794        5.425271264        5.545617174
1449        1.55        0.3937        0.3389        0.299        0.2711        0.2646        3.937007874        4.573620537        5.183946488        5.717447436        5.857898715
1580        1.55        0.381        0.324        0.2857        0.2543        0.2513        4.06824147        4.783950617        5.425271264        6.095163193        6.167926781
1723        1.55        0.3681        0.3097        0.2714        0.2497        0.2364        4.210812279        5.004843397        5.711127487        6.207448939        6.556683587
1879        1.55        0.3545        0.3052        0.2653        0.2341        0.22        4.37235543        5.078636959        5.842442518        6.621102093        7.045454545
2048        1.55        0.3339        0.305        0.2549        0.223        0.2103        4.642108416        5.081967213        6.080816006        6.950672646        7.370423205
2234        1.55        0.3249        0.2943        0.245        0.2055        0.1953        4.770698677        5.266734625        6.326530612        7.542579075        7.936507937
2436        1.55        0.3136        0.2847        0.2384        0.1939        0.1897        4.942602041        5.444327362        6.501677852        7.993811243        8.170795994
2656        1.55        0.3062        0.2731        0.2271        0.1847        0.1805        5.062050947        5.675576712        6.825187142        8.391987006        8.587257618
2897        1.55        0.2931        0.2624        0.2168        0.1752        0.1687        5.288297509        5.907012195        7.149446494        8.847031963        9.187907528
3159        1.55        0.2829        0.2514        0.2071        0.1661        0.1586        5.478967833        6.165473349        7.484307098        9.331727875        9.773013871
3445        1.55        0.2782        0.2406        0.1978        0.1575        0.1488        5.571531272        6.442227764        7.83619818        9.841269841        10.41666667
3757        1.55        0.2656        0.236        0.1935        0.1492        0.1415        5.835843373        6.56779661        8.010335917        10.38873995        10.9540636
4096        1.55        0.2519        0.2294        0.1864        0.1416        0.1363        6.153235411        6.756756757        8.315450644        10.94632768        11.37197359
4467        1.55        0.2453        0.2184        0.179        0.1337        0.1246        6.318793314        7.097069597        8.659217877        11.59311892        12.43980738
4871        1.55        0.2335        0.2133        0.1728        0.1277        0.1188        6.638115632        7.266760431        8.969907407        12.13782302        13.04713805
5312        1.55        0.2299        0.2049        0.1658        0.1204        0.1162        6.742061766        7.564665691        9.348612786        12.87375415        13.33907057
5793        1.55        0.2243        0.1965        0.1579        0.1161        0.1066        6.910387873        7.888040712        9.816339455        13.35055986        14.54033771
6317        1.55        0.2165        0.1883        0.1515        0.1089        0.1015        7.159353349        8.231545406        10.2310231        14.23324151        15.27093596
6889        1.55        0.2105        0.1802        0.1444        0.1041        0.0941        7.363420428        8.601553829        10.73407202        14.8895293        16.47183847
7513        1.55        0.2026        0.1777        0.1423        0.0981        0.0902        7.650542942        8.722566123        10.89248067        15.80020387        17.18403548
8192        1.55        0.1895        0.1718        0.138        0.0936        0.0858        8.179419525        9.022118743        11.23188406        16.55982906        18.06526807
8934        1.55        0.186        0.165        0.1335        0.087        0.0794        8.333333333        9.393939394        11.61048689        17.81609195        19.52141058
9742        1.55        0.178        0.1601        0.1282        0.0851        0.0765        8.707865169        9.681449094        12.09048362        18.21386604        20.26143791
10624        1.55        0.1737        0.1549        0.1227        0.08        0.0727        8.923431203        10.00645578        12.63243684        19.375        21.32049519
11586        1.55        0.1708        0.1499        0.1183        0.0745        0.0694        9.074941452        10.34022682        13.10228233        20.80536913        22.33429395
12634        1.55        0.1635        0.1424        0.112        0.0697        0.0661        9.480122324        10.88483146        13.83928571        22.23816356        23.44931921
13778        1.55        0.1582        0.1357        0.1081        0.066        0.0615        9.797724399        11.42225497        14.33857539        23.48484848        25.20325203
15025        1.55        0.153        0.1351        0.1089        0.0621        0.0567        10.13071895        11.47298298        14.23324151        24.95974235        27.33686067
16384        1.55        0.1439        0.1342        0.1044        0.0594        0.0551        10.77136901        11.54992548        14.8467433        26.09427609        28.13067151
上表第2列到第7列（basecase        toom22        toom33        toom44        toom6h        toom8h）为 平均单位时间，时间单位为始终周期，第8列以后为各个Tomm算法相对于basecase乘法的速度，即加速比。

liangbch 发表于 2017-1-4 17:37:42

使用楼上数据生成的图表

liangbch 发表于 2017-1-4 17:51:44

可以看到，当乘数为16384个limb时，toom8h算法的加速比超过28. 另外，相对于toom22，toom33，toom44，toom6h的加速效果明显高出一大截。这是因为toom6h和toom8h使用新的算法，在系数矩阵转化为单位矩阵时，新的算法所需的步骤更好。下面我简单的分析一下。
一般的，toom-kk算法使用2k-1个插值点。如当k=5是，使用9个插值点，故系数矩阵式一个9X9的方阵，第一行使用插值点0，最后一行使用插值点正无穷，这两行的点已经符合单位矩阵的要求，无需归零化。其它的点共计(2k-3)*（2k-1）个，若每步矩阵变换可将1个点归零（对角线上的元素需要转为1），则大约需要4k*k个步骤，而新的toom6h和toom8h，总是使用成对地使用符号相反的插值点，按照论文High_degree_Toom_n_half_for_balanced_and_unbalanced_multiplication.pdf中的方法，矩阵中相邻的4个点变为1个，将矩阵转化为单位矩阵的步骤大大减小，大约只用常规方法的四分之一。故新的算法加速效应非常明显。

只是呼吸 发表于 2017-1-4 21:24:05

论文下了一个来看，全是英文，这个恼火，真无法。

liangbch 发表于 2017-1-5 09:05:03

不但都是英文，而且几乎全是Marco Bodrato写的。意大利人Marco Bodrato是这个算法具体实现的最大贡献者，他研究Toom-Cook算法十年如一日，值得尊敬。GMP5.0以后的Toom-Cook算法的代码也是他写的。

查看完整版本: Toom-Cook 乘法