Toom-Cook 乘法

无心人

9# 云梦

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

liangbch

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

liangbch

论文	作者	摘要	重要性	备注
ToomCook.pdf	Sai Krishna Yedugani	Toom-cook算法入门	中
WhatAboutToomCookMatricesOptimality.pdf	Marco Bodrato 和 Alberto  Zanoni	讲述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

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

liangbch

  在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 1000  mpn_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

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

使用楼上数据生成的图表

liangbch

可以看到，当乘数为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个，将矩阵转化为单位矩阵的步骤大大减小，大约只用常规方法的四分之一。故新的算法加速效应非常明显。

只是呼吸

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

liangbch

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