New algorithm for cube (third power) computation
Alberto Zanoni
zanoni at volterra.uniroma2.it
Mon Jan 18 16:04:25 CET 2010
Hi all,
I've recently (last week) found a completely new algorithm to
compute the cube of a long integer A, quite (and curious, so to say, and)
different from the obvious
1) compute A1 = A^2
2) multiply A1*A
I've already written some GMP code for it. It is far from being stable and
optimal, but it works and I could compute some timings, see below.
I hope I'll soon have something more definitive and worth to be presented.
Could it perhaps be interesting for GMP ? Do you know any other function that
could benefit from it ?
Thanks,
Alberto
an GMP cube Alberto cube Gain %
---------------------------------------------------------------
20 5800.00 8736.00 -50.62
21 6284.00 9604.00 -52.83
22 6812.00 9672.00 -41.98
23 7392.00 10744.00 -45.35
24 8076.00 10720.00 -32.74
25 8552.00 11612.00 -35.78
26 9288.00 11716.00 -26.14
27 9840.00 13368.00 -35.85
28 10660.00 13636.00 -27.92
29 11296.00 14896.00 -31.87
30 15420.00 15588.00 -1.09
31 15996.00 15896.00 0.63
32 16968.00 16472.00 2.92
33 17676.00 17224.00 2.56
34 18408.00 17520.00 4.82
35 18684.00 18392.00 1.56
36 19064.00 18708.00 1.87
37 20328.00 20272.00 0.28
38 20576.00 19508.00 5.19
39 21444.00 21132.00 1.45
40 22732.00 21516.00 5.35
41 23188.00 22828.00 1.55
42 23932.00 22844.00 4.55
43 24344.00 24696.00 -1.45
44 25064.00 24652.00 1.64
45 26740.00 26020.00 2.69
46 27004.00 26900.00 0.39
47 29224.00 27752.00 5.04
48 29732.00 28488.00 4.18
49 30684.00 29744.00 3.06
50 31332.00 29980.00 4.32
51 32392.00 31420.00 3.00
52 34188.00 32652.00 4.49
53 34372.00 33276.00 3.19
54 34764.00 33464.00 3.74
55 36804.00 35472.00 3.62
56 38788.00 35980.00 7.24
57 40056.00 37924.00 5.32
58 40012.00 38556.00 3.64
59 43016.00 41116.00 4.42
60 43032.00 42304.00 1.69
61 45320.00 44736.00 1.29
62 45364.00 44892.00 1.04
63 48016.00 48708.00 -1.44
64 48672.00 47676.00 2.05
65 51452.00 48672.00 5.40
66 52096.00 49964.00 4.09
67 52436.00 51760.00 1.29
68 53396.00 51220.00 4.08
69 55352.00 51504.00 6.95
70 56084.00 51916.00 7.43
71 55872.00 52944.00 5.24
72 57192.00 53444.00 6.55
73 57252.00 54172.00 5.38
74 57352.00 54180.00 5.53
75 58648.00 56484.00 3.69
76 59232.00 56984.00 3.80
77 61220.00 58252.00 4.85
78 62100.00 58976.00 5.03
79 63964.00 60884.00 4.82
80 64288.00 61340.00 4.59
81 65440.00 62784.00 4.06
82 67360.00 63548.00 5.66
83 68796.00 65536.00 4.74
84 69092.00 66084.00 4.35
85 71120.00 67352.00 5.30
86 72116.00 67908.00 5.84
87 74568.00 70716.00 5.17
88 74736.00 70488.00 5.68
89 76468.00 72736.00 4.88
90 77388.00 73396.00 5.16
91 79888.00 75900.00 4.99
92 81100.00 76132.00 6.13
93 82656.00 78040.00 5.58
94 83504.00 79168.00 5.19
95 85872.00 81508.00 5.08
96 86024.00 81576.00 5.17
97 88724.00 83500.00 5.89
98 88736.00 84184.00 5.13
99 91340.00 86796.00 4.97
100 91624.00 87460.00 4.54
101 94320.00 88880.00 5.77
102 94544.00 89168.00 5.69
103 97432.00 92200.00 5.37
104 97728.00 92056.00 5.80
105 100220.00 94736.00 5.47
106 101616.00 95492.00 6.03
107 103528.00 98132.00 5.21
108 103744.00 98036.00 5.50
109 107284.00 101236.00 5.64
110 108184.00 101748.00 5.95
111 110456.00 105584.00 4.41
112 110632.00 105316.00 4.81
113 113664.00 107252.00 5.64
114 113972.00 108564.00 4.75
115 118780.00 114004.00 4.02
116 118096.00 114492.00 3.05
117 125572.00 118508.00 5.63
118 125696.00 120676.00 3.99
119 129516.00 123312.00 4.79
120 129168.00 125264.00 3.02
121 131796.00 126984.00 3.65
122 132212.00 126156.00 4.58
123 134772.00 130544.00 3.14
124 135556.00 131324.00 3.12
125 145488.00 134520.00 7.54
126 145000.00 136636.00 5.77
127 146464.00 140964.00 3.76
128 146688.00 140724.00 4.07
129 149628.00 141628.00 5.35
130 148016.00 142008.00 4.06
131 149176.00 142976.00 4.16
132 148340.00 144220.00 2.78
133 150820.00 143564.00 4.81
134 152672.00 146052.00 4.34
135 156616.00 149520.00 4.53
136 157476.00 145708.00 7.47
137 160636.00 152404.00 5.12
138 160736.00 155108.00 3.50
139 162708.00 150868.00 7.28
140 161816.00 153124.00 5.37
141 170084.00 153844.00 9.55
142 169352.00 153400.00 9.42
143 169296.00 157632.00 6.89
144 167868.00 157232.00 6.34
145 169656.00 158896.00 6.34
146 171116.00 158604.00 7.31
147 172612.00 160700.00 6.90
148 169136.00 159720.00 5.57
149 174224.00 161296.00 7.42
150 174104.00 161356.00 7.32
151 175196.00 166348.00 5.05
152 175728.00 165780.00 5.66
153 180440.00 169972.00 5.80
154 182136.00 170408.00 6.44
155 184824.00 173572.00 6.09
156 184812.00 173544.00 6.10
157 187920.00 174912.00 6.92
158 189396.00 175264.00 7.46
159 192232.00 178948.00 6.91
160 191020.00 178492.00 6.56
161 194328.00 182012.00 6.34
162 196284.00 183468.00 6.53
163 197888.00 186940.00 5.53
164 198328.00 187348.00 5.54
165 204128.00 190220.00 6.81
166 203784.00 188968.00 7.27
167 206272.00 194156.00 5.87
168 207260.00 194380.00 6.21
169 212520.00 197064.00 7.27
170 213348.00 198656.00 6.89
171 216248.00 201792.00 6.68
172 217820.00 202204.00 7.17
173 221480.00 203852.00 7.96
174 221556.00 203992.00 7.93
175 223008.00 207984.00 6.74
176 224056.00 208696.00 6.86
177 227296.00 211856.00 6.79
178 232028.00 212992.00 8.20
179 231652.00 216824.00 6.40
180 233088.00 216504.00 7.11
181 235376.00 219116.00 6.91
182 237224.00 220540.00 7.03
183 239084.00 225216.00 5.80
184 239700.00 224492.00 6.34
185 245248.00 228504.00 6.83
186 245672.00 229260.00 6.68
187 249612.00 232808.00 6.73
188 251432.00 233180.00 7.26
189 251744.00 236200.00 6.17
190 255708.00 236780.00 7.40
191 259168.00 241536.00 6.80
192 256372.00 240532.00 6.18
193 261504.00 245048.00 6.29
194 263968.00 246120.00 6.76
195 267976.00 249744.00 6.80
196 268468.00 249476.00 7.07
197 271932.00 253068.00 6.94
198 271404.00 252968.00 6.79
199 278656.00 258168.00 7.35
200 277752.00 258148.00 7.06
201 282160.00 262336.00 7.03
202 282396.00 262640.00 7.00
203 283880.00 266512.00 6.12
204 285728.00 268372.00 6.07
205 290892.00 270428.00 7.03
206 290132.00 270652.00 6.71
207 292488.00 275396.00 5.84
208 291552.00 273900.00 6.05
209 303800.00 278316.00 8.39
210 301556.00 278684.00 7.58
211 305144.00 283124.00 7.22
212 305660.00 283116.00 7.38
213 305112.00 286932.00 5.96
214 310628.00 285668.00 8.04
215 310840.00 292428.00 5.92
216 311456.00 290916.00 6.59
217 316188.00 296404.00 6.26
218 315696.00 296540.00 6.07
219 317492.00 301384.00 5.07
220 322020.00 301872.00 6.26
221 324388.00 305748.00 5.75
222 321052.00 306464.00 4.54
223 323712.00 311464.00 3.78
224 324604.00 311240.00 4.12
225 325708.00 317252.00 2.60
226 335908.00 317036.00 5.62
227 332688.00 322324.00 3.12
228 332508.00 322920.00 2.88
229 342972.00 325640.00 5.05
230 345268.00 325552.00 5.71
231 341600.00 336232.00 1.57
232 345600.00 336980.00 2.49
233 348292.00 345164.00 0.90
234 353660.00 345816.00 2.22
235 355460.00 353956.00 0.42
236 349700.00 357416.00 -2.21
237 351212.00 351084.00 0.04
238 368472.00 350436.00 4.89
239 367592.00 352948.00 3.98
240 365152.00 348676.00 4.51
241 368624.00 355608.00 3.53
242 365532.00 350592.00 4.09
243 368032.00 355224.00 3.48
244 373732.00 354864.00 5.05
245 375392.00 361124.00 3.80
246 373388.00 360896.00 3.35
247 378876.00 366108.00 3.37
248 378696.00 365812.00 3.40
249 378200.00 368900.00 2.46
250 387520.00 369796.00 4.57
251 388248.00 373616.00 3.77
252 385748.00 373940.00 3.06
253 394872.00 376260.00 4.71
254 394552.00 376000.00 4.70
255 395724.00 379488.00 4.10
256 400240.00 378872.00 5.34
257 400844.00 385768.00 3.76
258 401988.00 385824.00 4.02
259 405728.00 389700.00 3.95
260 406680.00 390476.00 3.98
261 405340.00 391356.00 3.45
262 416152.00 392304.00 5.73
263 414348.00 397272.00 4.12
264 412628.00 396268.00 3.96
265 421988.00 401404.00 4.88
266 420832.00 401660.00 4.56
267 420768.00 405516.00 3.62
268 427868.00 405084.00 5.33
269 430072.00 413976.00 3.74
270 428284.00 413172.00 3.53
271 435108.00 417664.00 4.01
272 435208.00 417648.00 4.03
273 433264.00 419488.00 3.18
274 446048.00 420196.00 5.80
275 447972.00 426276.00 4.84
276 443472.00 427576.00 3.58
277 452964.00 427828.00 5.55
278 453652.00 428660.00 5.51
279 457476.00 433836.00 5.17
280 462700.00 432144.00 6.60
281 462192.00 442260.00 4.31
282 461752.00 442360.00 4.20
283 465160.00 446276.00 4.06
284 467300.00 446728.00 4.40
285 467808.00 450212.00 3.76
286 477440.00 451540.00 5.42
287 478916.00 457568.00 4.46
288 476572.00 456408.00 4.23
289 484980.00 460560.00 5.04
290 486880.00 460448.00 5.43
291 485936.00 465332.00 4.24
292 493120.00 463636.00 5.98
293 493640.00 472824.00 4.22
294 493344.00 472736.00 4.18
295 498312.00 478596.00 3.96
296 496692.00 478260.00 3.71
297 497484.00 482968.00 2.92
298 509900.00 484748.00 4.93
299 510052.00 490936.00 3.75
300 508992.00 491088.00 3.52
301 520376.00 494740.00 4.93
302 519456.00 493252.00 5.04
303 523884.00 497328.00 5.07
304 529180.00 497796.00 5.93
305 530140.00 504524.00 4.83
306 526060.00 504368.00 4.12
307 530224.00 509004.00 4.00
308 530484.00 510188.00 3.83
309 535376.00 513776.00 4.03
310 543320.00 514616.00 5.28
311 541792.00 519620.00 4.09
312 541028.00 519908.00 3.90
313 549700.00 522036.00 5.03
314 548520.00 523452.00 4.57
315 549296.00 525520.00 4.33
316 555276.00 526124.00 5.25
317 556456.00 534908.00 3.87
318 556836.00 535840.00 3.77
319 560116.00 539976.00 3.60
320 561364.00 538396.00 4.09
321 558892.00 544460.00 2.58
322 573500.00 542340.00 5.43
323 575484.00 554020.00 3.73
324 572352.00 551916.00 3.57
325 582336.00 554436.00 4.79
326 583740.00 553476.00 5.18
327 582628.00 558996.00 4.06
328 589148.00 558888.00 5.14
329 592892.00 568864.00 4.05
330 591156.00 570400.00 3.51
331 593148.00 574172.00 3.20
332 597128.00 575144.00 3.68
333 596312.00 580572.00 2.64
334 609752.00 580996.00 4.72
335 610104.00 589936.00 3.31
336 608704.00 589236.00 3.20
337 618332.00 590236.00 4.54
338 619504.00 591432.00 4.53
339 619556.00 600436.00 3.09
340 628156.00 599560.00 4.55
341 631852.00 616708.00 2.40
342 628908.00 615908.00 2.07
343 631888.00 623812.00 1.28
344 632772.00 628560.00 0.67
345 632272.00 631596.00 0.11
346 655392.00 629992.00 3.88
347 658792.00 644240.00 2.21
348 654372.00 645328.00 1.38
349 670824.00 653504.00 2.58
350 669460.00 654608.00 2.22
--
Alberto Zanoni
Centro Interdipartimentale "Vito Volterra"
Universita' degli Studi di Roma "Tor Vergata"
Via Columbia 2
00133 Roma, Italia
More information about the gmp-devel
mailing list