Toom-Cook non-congruent multiplication

[Josh Liu]

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