Toom-Cook 4x3 and 5x2 multiplication: Toom3.5
Paul.Zimmermann at loria.fr
Fri Nov 24 14:35:04 CET 2006
> From: "Huseyin HISIL" <huseyinhisil at iyte.edu.tr>
> Date: Fri, 24 Nov 2006 07:30:49 +0200
> Dear All,
> My apologies if I disturb your current concentration but
> has anyone ever considered Karatsuba 3-way multiplication
> in this fast multiplication context? Any idea? I guess
> there should be upper and lower thresholds where it is
> faster than both karatsuba and toomcook 3way. (More
> multiplications and less overhead). Any comment is
> You may want to check
> for a detailed explanation.
> Huseyin Hisil.
It performs a 3nx3n product with 6 products nxn, thus the theoretical
complexity is O(n^(log(6)/log(3))) where log(6)/log(3) ~ 1.63 is larger
than the Karatsuba exponent log(3)/log(2) ~ 1.58.
I believe it will never beat the current Karatsuba and Toom-Cook 3-way
codes, but maybe someone out there will prove I'm wrong...
More information about the gmp-devel