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

[Torbjorn Granlund]

"Huseyin HISIL" <huseyinhisil at iyte.edu.tr> writes:

  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.
  
The top row of partial products has a2*b2, a1*b1, a1*b1.  The latter
should be a0*b0.

It would be better to compute i.e., +(a2 + a1).(b2 + b1) as +(a2 -
a1).(b2 - b1) to avoid overflow.  (OK, obe needs to keep track of
signs, but that is not hard.

There is an hidden common expression in that you add the upper half of
a0*b0 to the lower half of a1*b1 twice.  Similarly for a2*b2 and
a1*b1.

-- 
Torbjörn