Invariant multiplier in Karatsuba/Toom

Josh Liu zliu2 at
Sun Feb 29 18:37:01 CET 2004

I mentioned non-recursive variants of the Karatsuba-Ofman algorithm in 
two posts to this list. The code I put up, here at:


is slower than its recursive counterpart. This is because it is only a 
direct translation of the recursive version into an iterative algorithm 
with naive use of stacks.
I am currently working on an iterative Karatsuba algorithm that will 
involve the deconstruction of the basecase multiplications so that I 
can order them in such a way that they can be done in serial, with 
regards to spatial order. It involves the multiplication of factors 
that require no subtractions first, then factors that are differences 
with one subtraction next, then three subtractions, then seven 
subtractions, and so on. Some repeated subtractions will be eliminated. 
The important part is that this method can be implemented to take 
advantage of the dependencies of each level of the subtraction chain. 
The indices of the interpolation has a structure very  similar to that 
of the indices of the basecase multiplies and subtractions and can be 
done just as easily.

P.S. Please email me if you want any information regarding the 
iterative cache optimized Karatsuba-Ofman algorithm.

More information about the gmp-devel mailing list