Slug #882
Impl faster multiplication for DUP (dense univariate polys)
Description
Christof wanted faster multiplication for DUPs.
He suggested implementing karatsuba's method.
History
#1 Updated by John Abbott almost 8 years ago
I made a very ad hoc impl of karatsuba when I was in Osnabrueck as I wanted to get an idea of when cross-over might occur (for polys in ZZ[x]
). My experiments found that karatsuba became potentially faster for two polys of degree about 30 (with fairly small integer coeffs).
#2 Updated by John Abbott almost 8 years ago
I also tried implementing a method which uses fast integer multiplication in GMP.
Evaluate both polys at 1000000 (say); multiply the integers, then extract the coeffs of product by converting the result to base 1000000. My prototype was about 5 times faster than the karatsuba prototype, so this method is probably worth implementing.
Note that this method would work best if all coeffs are about the same size. It may be rather inefficient if a few coeffs are much bigger than all the others. There should not be any problem in checking the "uniformity" of the sizes of the coeffs at run time.