Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication

Alberto Zanoni zanoni at
Tue Dec 22 09:12:03 CET 2009

Dear developers,

                I've recently worked on the use of "iterative"
Toom-Cook methods for the multiplication of very unbalanced operands
(say a and b).  In particular, considering the smallest unbalanced
version, Toom-2.5 (a.k.a. toom32), I wrote GMP code implementing the
two following main ideas:

1) Single evaluation of the shortest factor b (in the considered
   particular case, in points 1 and -1) - this was already pointed out
   some time ago, and Niels let me know that he also worked about that
   for a clever "double" use of Karatsuba method in the past.

2) Divide-by-2 techinque, moving shifts from interpolation phase to
   evaluation phase, when possible. For Toom-2.5 this means that if
   evaluation of b in 1 (and therefore in -1, too) is even, it is
   possible to do one single shift in b evaluation phase, and no
   shifts at all in all interpolation phases during iteration.
Details are contained in a soon-to-appear preprint of mine (it's just
a matter of a couple of weeks, I guess, but "unfortunately" Christmas
holydays are one step away...). I can send the dvi/pdf file to whom is
interested, just tell me.

You can find the code in

The code contains two version of the functions. The first one (1)
considers only parity of b evaluation, the second (2) of b and of a's
sections. In my experiments, (1) seems to be a bit faster than (2) on
my architecture, but I report both versions. Maybe testing on other
architectures could give different results. Compile with


to obtain version (1), and with


to obtain version (2)

I made some tests comparing the code with gmp-4.3.1, the development
version (December 2nd) and with a small modification suggested by
Marco. The maximum obtained gains lie in my case between 26 and 33 %.
I hope the code can someway be useful. Obviously corrections,
comments, changes, optimizations and whatever else are all welcome. Thank you 
very much in advance.


More information about the gmp-devel mailing list