View Single Post
Old 2011-11-07, 04:58   #3
Romulan Interpreter
LaurV's Avatar
"name field"
Jun 2011

230738 Posts

Originally Posted by Maximus View Post
Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.
Ok. Now let's be a little more clear. Multiplying polynomials is always max quadratic in the number of terms. That is, if the polynomials have degree n, then you do maximum about n^2 multiplications. If one polynomial is degree n and one is degree m, then you do maximum (n+1)*(m+1) multiplications. Some algorithms as Karatsuba or else, will do less multiplications. So, multiplying polynomials requires a "polynomial" number of steps. But each step could be exponential inside, if the coefficients are huge numbers (multi-precision)... I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that FFT multiplication is NOT polynomial. Its order is still (sub)exponential.

Maybe you found something like this, that could require a polynomial time, but it would require an exponential space.

The best algorithm should be the one that make a good compromise between the time and the space.
LaurV is offline