Toom-Cook 4x3 and 5x2 multiplication: Toom3.5

Paul Zimmermann Paul.Zimmermann at
Fri Nov 24 14:35:04 CET 2006

> From: "Huseyin HISIL" <huseyinhisil at>
> 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 
> appreciated.
> You may want to check 
> for a detailed explanation.
> Regards,
> 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...

Paul Zimmermann

More information about the gmp-devel mailing list