20111107, 03:30  #1 
Nov 2011
2^{2}·3 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
2497_{16} 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
13^{2}×29 Posts 
Quote:
Quote:


20111107, 06:08  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 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
1110100100100_{2} 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
17×19×29 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
1110100100100_{2} Posts 

20111107, 13:59  #9 
Jun 2003
11445_{8} 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
17·19·29 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 