mersenneforum.org > Math low-value comments cleared out of FFT thread
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2011-11-07, 03:30   #1
Maximus

Nov 2011

22×3 Posts
low-value comments cleared out of FFT thread

Quote:
 Originally Posted by LaurV 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?
Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.

2011-11-07, 03:33   #2
Maximus

Nov 2011

22×3 Posts

Quote:
 Originally Posted by Christenson 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.
In the homework? No. :)

2011-11-07, 04:58   #3
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

231208 Posts

Quote:
 Originally Posted by Maximus 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.

2011-11-07, 05:17   #4
axn

Jun 2003

120758 Posts

Quote:
 Originally Posted by LaurV 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.
FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication)

Quote:
 Originally Posted by LaurV Maybe you found something like this, that could require a polynomial time, but it would require an exponential space.
If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time.

 2011-11-07, 06:08 #5 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2011-11-07, 12:20   #6
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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,
False.

Quote:
 if the coefficients are huge numbers (multi-precision).

False. 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 FFT multiplication is NOT polynomial. Its order is still (sub)exponential.
False. 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.

 2011-11-07, 13:15 #7 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24×613 Posts RDS rulz... Well, you are right... Mea culpa. I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P Last fiddled with by LaurV on 2011-11-07 at 13:21
2011-11-07, 13:29   #8
R.D. Silverman

Nov 2003

164448 Posts

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

The proof is trivial.

2011-11-07, 13:59   #9
axn

Jun 2003

3·11·157 Posts

Quote:
 Originally Posted by LaurV I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P
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.

Last fiddled with by axn on 2011-11-07 at 14:01 Reason: thing -> think

2011-11-07, 15:46   #10
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by axn 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.
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)

2011-11-07, 15:50   #11
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·613 Posts

Quote:
 Originally Posted by axn 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.
Well, the thread says "explanation for non math guys"....

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 46 2017-05-09 12:32 ET_ FermatSearch 5 2016-07-03 10:58 R.D. Silverman GMP-ECM 11 2013-06-29 20:34 jasong jasong 0 2012-08-19 20:02 opyrt Prime Sierpinski Project 7 2008-12-15 00:49

All times are UTC. The time now is 19:38.

Wed Dec 1 19:38:05 UTC 2021 up 131 days, 14:07, 1 user, load averages: 1.53, 1.57, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.