Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication
zanoni at volterra.uniroma2.it
Tue Dec 22 09:12:03 CET 2009
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