Toom-Cook non-congruent multiplication
Josh Liu
zliu2 at student.gsu.edu
Thu Feb 26 14:11:41 CET 2004
One can multiply $n$ point by $m$ point numbers with $n+m-1$ point
multiplications of congruent numbers by applying the Toom-Cook
multiplication algorithm. The degree of an $n-1$ degree polynomial
multiplied by an $m-1$ degree polynomial will yield an $n+m-1$ degree
polynomial. This means that only $n+m-1$ point multiplications are
necessary to obtain the coefficients of the product with the Toom-Cook
multiplication. I am going to implement this method. It will be faster
than the original splitting code by a sizable margin. For instance,
multiplying 3x2 uses 5 multiplications with the Karatsuba-Ofman
algorithm and 6 with basecase whereas with the Toom-Cook requires only
4 multiplications. Multiplying 5x2 requires 10 basecases, 8 with the
Karatsuba-Ofman, but only 6 with the Toom-Cook. The factors the
multiplications can be padded with a few extra limbs to make the
corresponding ratio simpler and thus decrease overhead.
PS. Would someone please look at this iterative Karatsuba-Ofman code
and see if there are any ways to further optimize it? It is not the
cache-optimized code I mentioned earlier but it would still be
interesting to investigate.
http://sourcepost.sytes.net/sourceview.aspx?source_id=11251
More information about the gmp-devel
mailing list