Karatsuba Speedup

Josh Liu zliu2 at student.gsu.edu
Tue Feb 10 20:31:03 CET 2004

It is advantageous to not repeat that addition that was mentioned in 
the manual. I have timed both mpn_kara_mul_n and my 5 half operand size 
addition method and it seems that the function call overhead is not 
much of a big deal when compared with the speedup possible by 
eliminating 1/6 of the additions at the tail end of the function. Also, 
it might be possible to combine two addition operations into a single 
function, at least for the Pentium 4. My combined mpn_add_add_n does 3 
cycles per limb versus mpn_add_n's 4 cycles per limb. It seems that my 
mpn_add_sub_n function only improves by 1/4 limbs per cycle, which is 
And on another note, where did the derivation come from in the Other 
Multiplications section of the manual where the Toom-Cook algorithm 
evaluated at points -r,...,0,...r requiring the divisors of algorithm T 
step 7 in Knuth be j^2 and the multipliers be (2 j t - j^2) for T-8?
P.S. E-mail me if you want to look at my 5 addition code.

More information about the gmp-devel mailing list