20070527, 17:35  #1 
Feb 2004
France
929 Posts 
Complexity of LLT
Hello,
I know this has already been said in this forum (Mr Silverman I think), but I cannot find it again. What is the overall complexity of the LLT as implemented by George, with the IBDWT method (the book of Crandall and Pomerance does not say a world about this). I'm lost with the 2 following information: Wikipedia : The most efficient known multiplication method, the SchönhageStrassen algorithm based on the Fast Fourier transform, requires O(p log p log log p) time to square a pbit number, reducing the complexity to O(p2 log p log log p) or Õ(p2). Mersenne Wiki : When used with the Fast Fourier transform, the test has the complexity of O(n2 log n), where n is the length of the number. Thanks, Tony 
20070528, 01:07  #2  
Jun 2005
2·191 Posts 
Quote:
Also, I don't believe the DWT represents an improvement in complexity over a typical FFT, it only reduces the proportionality constant. Drew Last fiddled with by drew on 20070528 at 01:29 

20070528, 14:10  #3 
Feb 2006
Denmark
2·5·23 Posts 
FFT multiplication of nbit numbers is O(n*log n*log log n).
The log log n term grows very slowly and realistic register and operand sizes make it disappear in practice in most implementations, so the time is often but inaccurately simplified to O(n*log n). A prp or fast proof test gets another factor n because it makes O(n) multiplications. Optimizations of special forms like with IBDWT give a constant factor in implementations, but the asymptotic time is unchanged. 
20070528, 16:12  #4  
Feb 2004
France
929 Posts 
Quote:
Let me add parenthesis to clarify. So, for a 2^n1 Mersenne number, executing the full LLT (n2 steps), is O( n * n* log(n) * log(log(n)) ) in theory, which simplifies in O( n^2 * log(n) ). Though the simple multiplication we learn at school would lead to O(n^3) for a whole LLT. Correct ? So it seems that Drew was correct and that our Mersenne Wiki is too vague by saying "the length of the number". Thanks, Tony 

20070528, 17:54  #5  
Jun 2005
17E_{16} Posts 
Quote:
Edit: I stand corrected, I just graphed the function, and it looks like the rate of growth of log(log(n)) decreases substantially as n grows. Last fiddled with by drew on 20070528 at 18:00 

20070529, 04:37  #6  
Feb 2006
Denmark
2×5×23 Posts 
Quote:


20070529, 09:55  #7  
Feb 2004
France
929 Posts 
Quote:
Thanks ! Tony 

20070529, 20:57  #8  
∂^{2}ω=0
Sep 2002
República de California
26752_{8} Posts 
Quote:
FFT gets you an asymptotic n > log n reduction, assuming you can implement it in manner that actually scales that way on modern cachebased microprcessors. DWT (a.k.a. "implicit mod") halves your runlength, i.e. gets you an asymptotic factor of ~2x. (At finite runlengths of practical interest, the speedup may be appreciably greater, approaching a factor of 3, due to the aforementioned cache effects.) Balanceddigit arithmetic gives a significant improvement in the slowness of the growth of roundoff error. I leave it as a homework exercise as to the (heuristic) asymptotic behavior here. Pureintegerbased transforms are not subject to roundoff error, but still have input wordsize restricted by the magnitude of convolution outputs. In fact, for a careful implementation of balanceddigit arithmetic, this convolutionoutputsize effect tends to dwarf the roundofferrorgrowth effect. In other words, as n gets larger, floatingpoint (counterintuitively) becomes relatively more attractive, not less. (This assumes that one starts with a floatingpoint precision sufficiently good to be competitive with pureinteger at modest n  that typically means double precision). Last fiddled with by ewmayer on 20070529 at 20:58 

20070529, 21:05  #9 
Feb 2004
France
929 Posts 
Since I plan to talk about that in a paper, what should I say about the complexity of LLT with basic multiplication compared to LLT with FFT/IBDWT ?
Is: "Thanks to FFT, we have about O(n^2*log n) instead of O(n^3) with scholar method" correct ? And what should I add (very short) about the impact of IBDWT ? Since I do not master that point, I need help to get the correct sentence. Thanks for helping ! Tony 
20070529, 21:15  #10  
∂^{2}ω=0
Sep 2002
República de California
2·3^{2}·653 Posts 
Hi, Tony:
Quote:
(What you might call the "Ecole normal inférieur" method, to make a pun on the French school naming system. ;) I further suggest replacing "about" with the more mathematically precise "asymptotically." Quote:
Cheers, Ernst 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Complexity of Chinese Remainder Theorem  carpetpool  Miscellaneous Math  4  20170209 19:26 
What is the time complexity of base conversion?  Mr. P1  Computer Science & Computational Number Theory  5  20130402 15:47 
Complexity analysis of 3 tests  kurtulmehtap  Math  10  20130320 14:15 
space complexity of common algorithms?  ixfd64  Math  4  20061127 20:52 
complexity of Pepin's test  ixfd64  Math  14  20051201 22:50 