[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-devel
Subject: Toom-Cook non-congruent multiplication
From: zliu2 () student ! gsu ! edu (Josh Liu)
Date: 2004-02-26 20:39:34
Message-ID: 9BCB3482-688F-11D8-8FC7-000393A76A50 () student ! gsu ! edu
[Download RAW message or body]
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
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic