Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication
Alberto Zanoni
zanoni at volterra.uniroma2.it
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
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
More information about the gmp-devel
mailing list