low-value comments cleared out of FFT thread
 

[QUOTE=LaurV;277395]I am confused here. Did you find an algorithm to multiply polynomials (in whatever complexity time) or did you find an algorithm to multiply integers in polynomial time?[/QUOTE]

Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.

[QUOTE=Christenson;277396]Let's have it, with a small example. Be mathematically precise in the sense you mean it...and post in the homework thread, since your post (and my reply) is off-topic, and it will draw fewest flames there.[/QUOTE]

In the homework? No. :)

[QUOTE=Maximus;277399]Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.[/QUOTE]

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 [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential.

Maybe you found something like [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Linear_time_multiplication"]this[/URL], 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.

[QUOTE=LaurV;277405]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 [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential. [/quote]
:huh: FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication)

[QUOTE=LaurV;277405]Maybe you found something like [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Linear_time_multiplication"]this[/URL], that could require a polynomial time, but it would require an exponential space.
[/QUOTE]

:huh: :huh: If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time.

"requires that any memory location can be accessed in constant time"

Now admittedly, that also requires a multiplication look up table of significant size, which, when counted with the actual multiplication, would create an exponential algorithm

[QUOTE=LaurV;277405]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,
[/QUOTE]

[b]False.[/b]

[QUOTE]
if the coefficients are huge numbers (multi-precision).
[/QUOTE]


[b]False.[/b] Integer multiplication also takes just polynomial time.

[QUOTE]
.. 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 [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential.
[/QUOTE]

[b]False.[/b] FFT multiplication is definitely polynomial.

Three strikes and you are out!

Go back and do some reading. For example,

Go read my joint paper with Peter: An FFT Extension to the P-1 Factoring
Algorithm.

Integer multiplication takes polynomial time. The 'paper/pencil'
method is quadratic in the size of the inputs. Integer multiplication via
FFT's takes O(n log n loglogn) where n is the size of the numbers.

The only essential difference between integer and polynomial multiplication is
that for the latter one does not need to handle CARRIES.

RDS rulz... Well, you are right... Mea culpa. :smile:
I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P

[QUOTE=LaurV;277422]RDS rulz... Well, you are right... Mea culpa. :smile:
I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P[/QUOTE]

PROVABLY IMPOSSIBLE.

The proof is trivial.

[QUOTE=LaurV;277422]I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P[/QUOTE]

I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied.

[QUOTE=axn;277426]I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied.[/QUOTE]

The input to a complexity function is the SIZE of the problem........
We measure time/space complexity as a function of the size of the inputs.....

The size of a number is its length (in whatever radix you choose)

(as axn knows)

[QUOTE=axn;277426]I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied.[/QUOTE]

Well, the thread says "explanation for non math guys"....