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

[Paul Zimmermann]

> 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 
> appreciated.
> 
> You may want to check 
> http://arf.iyte.edu.tr/~hhisil/index/main/research/karatsuba_3way.txt 
> 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