New algorithm for cube (third power) computation

Alberto Zanoni zanoni at
Mon Mar 15 17:06:43 CET 2010

Hi all,
       as anticipated in

a new algorithm for the computation of the cube of a long integer has
recently been discovered, based on a splitting in two a' la Karatsuba
and on an ad hoc unbalanced Toom-3 method. The description and some details 
are contained in a preprint you can find in

The file:

and (improvable) GMP code.

It seems that in some cases the new algorithm can be effective (see
the graphics in the preprint), but still some work must be done
and see what happens if the new cube algorithm is "mixed" with binary
algorithm for generic power exponentiation.

Whatever comment, observation, suggestion is welcome.
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