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

[Alberto Zanoni]

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

http://bodrato.it/papers/zanoni.html#CIVV2009c

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

-DONLY_B_EVEN

to obtain version (1), and with

-DA_AND_B_EVEN

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.

Alberto