Choosing multiplication algorithm
Torbjorn Granlund
tg at gmplib.org
Sat Sep 26 21:47:00 CEST 2009
I updated http://gmplib.org/devel/ with some curious diagrams for
multiplication algorithm selection.
We currently (in the development sources) have 9 Karatsuba/Toom
variants, then also schoolbook multiplication and large-ring Schönhage
FFT multiplication, all-in-all 11 algorithms.
But the diagrams have 15 colours, since we also show 4 nested
strategies, used for the most unbalanced operands.
Now we just need to figure out how to best decide which algorithm to use
in GMP. :-)
(Thanks goes to Marco Bodrato for the idea to compare like this.)
--
Torbjörn
More information about the gmp-devel
mailing list