mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Closed Thread
 
Thread Tools
Old 2011-11-07, 03:30   #1
Maximus
 
Nov 2011

148 Posts
Exclamation low-value comments cleared out of FFT thread

Quote:
Originally Posted by LaurV View Post
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.
Maximus is offline  
Old 2011-11-07, 03:33   #2
Maximus
 
Nov 2011

22×3 Posts
Default

Quote:
Originally Posted by Christenson View Post
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. :)
Maximus is offline  
Old 2011-11-07, 04:58   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100010110111002 Posts
Default

Quote:
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  
Old 2011-11-07, 05:17   #4
axn
 
axn's Avatar
 
Jun 2003

52×191 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
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.
axn is offline  
Old 2011-11-07, 06:08   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

"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
Dubslow is offline  
Old 2011-11-07, 12:20   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline  
Old 2011-11-07, 13:15   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×23×97 Posts
Default

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
LaurV is offline  
Old 2011-11-07, 13:29   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline  
Old 2011-11-07, 13:59   #9
axn
 
axn's Avatar
 
Jun 2003

477510 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
axn is offline  
Old 2011-11-07, 15:46   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by axn View Post
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)
R.D. Silverman is offline  
Old 2011-11-07, 15:50   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·23·97 Posts
Default

Quote:
Originally Posted by axn View Post
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"....
LaurV is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
Request for comments ET_ FermatSearch 5 2016-07-03 10:58
No Comments? R.D. Silverman GMP-ECM 11 2013-06-29 20:34
How do you look at previous comments on Youtube? jasong jasong 0 2012-08-19 20:02
Comments to the "getting started"-thread opyrt Prime Sierpinski Project 7 2008-12-15 00:49

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

Mon Nov 23 22:38:59 UTC 2020 up 74 days, 19:49, 4 users, load averages: 2.75, 2.47, 2.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.