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