Toom-Cook methods and even long integers

Alberto Zanoni zanoni at
Mon Mar 2 12:25:06 CET 2009

Dear Developers,

I've recently tried to see what can be done in Toom-Cook method for long
integers multiplication when one factor is even, looking for some
possible improvement by slightly modifying evaluation and
interpolation phases.

Actually, for Toom-3 it seems that possible optimizations are not very
effective, particularly when specific basic operations (A -= B/2) are
not available. Toom-3.5, for unbalanced operands, seems instead to be
a bit more promising, even if more investigation (mpn level
implementation) is needed.

For your interest, some details are discussed in

I'm at disposal for whatever clarification: thank you very much for
your attention.
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