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

Torbjorn Granlund tege at
Fri Nov 24 11:57:22 CET 2006

"Huseyin HISIL" <huseyinhisil at> 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 
  You may want to check 
  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


More information about the gmp-devel mailing list