Choosing multiplication algorithm

Torbjorn Granlund tg at
Sat Sep 26 21:47:00 CEST 2009

I updated 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.)


More information about the gmp-devel mailing list