Invariant multiplier in Karatsuba/Toom
zliu2 at student.gsu.edu
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