Toom-Cook 4x3 and 5x2 multiplication: Toom3.5
Torbjorn Granlund
tege at swox.com
Fri Nov 24 11:57:22 CET 2006
"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
More information about the gmp-devel
mailing list