New algorithm for cube (third power) computation
zanoni at volterra.uniroma2.it
Mon Mar 15 17:06:43 CET 2010
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
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.
Centro Interdipartimentale "Vito Volterra"
Universita' degli Studi di Roma "Tor Vergata"
Via Columbia 2
00133 Roma, Italia
More information about the gmp-devel