Fabrizio Caruso wrote:
>Hi!
>
>Thanks!
>Yes, expand was the problem.
>
>fasttimes performs roughly the same as "*"
>with fairly big dense univariate
>polynomials (degree>2500)
>which means fasttimes must be probably
>using something different then standard Karatsuba.
>I wonder it fasttimes does...\
>
You can look at the code for fasttimes. Unless someone changed
it since I wrote it, it is using a Karatsuba-style multiplier.
>
>Karatsuba as described in textbooks
>splits univariate dense polynomials
>into its higher degree part and
>lower degree part and by doing so
>it avoids one multiplication (3 instead of 4)
>at each recursive step.
>My C++ implementation of Karatsuba overtakes
>on the computers I tested it
>the school multiplication algorithm
>as soon as the degree is about 100.
>
That sounds reasonable. The degree of answer or the input?
50X50 --> 100 is a possible winner in my recent tests. Trying it on
10X90 --> 100 you might get a different winner.
Also consider that the Karatsuba iteration for say 2500X2500 degree
should be cut off at whatever you see as the break-even, and switch
to the "school multiplication".
On the other hand, for 2500X2500 univariate you can consider
FFT multiplication if you really have modest-size coefficients and
only one variable.
If you are studying this problem seriously, look at what is
done by NTL. I also have some programs for splitting in 3 rather
than 2 (Cook-Toom) and FFT.
RJF