# 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

```