20111107, 03:30  #1 
Nov 2011
14_{8} Posts 
lowvalue comments cleared out of FFT thread

20111107, 03:33  #2 
Nov 2011
2^{2}·3 Posts 

20111107, 04:58  #3  
Romulan Interpreter
Jun 2011
Thailand
9751_{10} Posts 
Quote:
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. 

20111107, 05:17  #4  
Jun 2003
47×109 Posts 
Quote:
Quote:


20111107, 06:08  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
"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 
20111107, 12:20  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Quote:
False. Integer multiplication also takes just polynomial time. Quote:
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 P1 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. 

20111107, 13:15  #7 
Romulan Interpreter
Jun 2011
Thailand
7^{2}·199 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 20111107 at 13:21 
20111107, 13:29  #8 
Nov 2003
2^{2}·5·373 Posts 

20111107, 13:59  #9 
Jun 2003
47·109 Posts 
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 20111107 at 14:01 Reason: thing > think 
20111107, 15:46  #10  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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) 

20111107, 15:50  #11 
Romulan Interpreter
Jun 2011
Thailand
7^{2}·199 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
Request for comments  ET_  FermatSearch  5  20160703 10:58 
No Comments?  R.D. Silverman  GMPECM  11  20130629 20:34 
How do you look at previous comments on Youtube?  jasong  jasong  0  20120819 20:02 
Comments to the "getting started"thread  opyrt  Prime Sierpinski Project  7  20081215 00:49 