Hiya Ernst, it wasn't me who wrote "exactly the same method", I was quoting Alan Hodges, and I found the phrase entertaining too. [EMAIL PROTECTED] wrote: [snip New Men, replied separately] > Seriously, Paul, there's just one quote in your compilation I take issue > with, in the section from Alan Hodges (about the Mersenne primes M521, > M607, M1279, M2203 and M2231 found by Robinson on the SWAC): > > > The largest known prime now is again a Mersenne prime, and found > > by exactly the same method, only on a somewhat larger and faster > > computer). > > "Exactly the same method" is misleading. Yes, the modern programs all > use the Lucas-Lehmer test in some form. But the algorithmic implementation > thereof has undergone radical changes since the days of Robinson's work. I agree with you completely! I did try to hint at this when I wrote:- > (That has O(n^3), more than George's great implementation of the LL > test. The Lucas-Lehmer algorithm was created in 1930, but they must have > used Grammar School multiplication as the Karatsuba method or Fourier > Transforms had not been invented yet). > The simplistic story of mine does leave space for more needed detail, and you are better than I at describing it. > Most notably, the use of FFT-based multiply schemes have reduced the number > of operations needed to test an n-bit Mersenne number from the > approximately O(n^3) (the n^2 term becomes negligible as n gets large) > cited by Robinson to just O(n^2*log2(n)). The Crandall/Fagin discrete > weighted transform method further eliminates the need for zero-padding > the vectors to be FFTed and more than doubles the speed of a typical > FFT-based implementation. As a result, the constant of proportionality > implied by the O(...) notation is typically around 5, where I've > factored in the fact that each computer input digit in a modern scheme > is around 16 bits or more. If one uses a simple grammar-school multiply > method on a 36-bit architecture like the SWAC, one can have input digits > of similar size (18 bits max.), and needs roughly 2*(n/18)^2 operations > per squaring, and n such squarings means O(n^3) machine operations, with > a constant of proportionality of around 1/100 (call it 1/2^7.) > > That means that for a Mersenne of around 8-9 million (call it 2^23) bits > (ropughly the size of current GIMPS first-time tests), these genuine > algorithmic improvements have reduced the labor from around (2^23)^3/2^7 > = 2^62 machine operations to test primality (which would need over 100 > years even running at 1 Giga-op per second) to around 5*n^2*log2(n) > ~= 2^49, a reduction of around a factor of ten thousand. Exactly! I do have a high respect for people who create new algorithms. This speed up is for free and forever, rather than building a computer 10,000 times faster. > Luke Welsh informs me that the SWAC had a cycle time of 8 microseconds > (not bad at all for its era!), so the hardware has speeded up since > then by a similar factor of about ten thousand. Thus, algorithmic > and hardware improvements have contributed about equally to increasing > the speed of testing, and thus the phrase "...and found by exactly > the same method, only on a somewhat larger and faster computer" is > (from an algorist's perspective) grossly inaccurate. I agree. It wasn't me who wrote it! > > So, Paul, perhaps you could add a Chapter 4 to your trilogy, describing > some of the algorithmic and computer advances (and the people who took > adavantage of them to find new Mersenne primes) since the 1950s, as > well as the era of distributed supercomputing which the Internet has > made possible. Or Chapter 2 Version 0.1.2? Yes, there is also a 25,000 times speed up from cooperation and distribution. > > > Thanks again for the trilogy, Paul! > > Cheers, > -Ernst Even funnier, is the following quote from Paul Hoffman's "The Man Who Loved Only Numbers", a biography of Erdös, page 35. "The technique that the GIMPS project uses isn't much more sophisticated than the 2000 year old method called "the sieve of Eratosthenes," invented by Eratosthenes of Alexandria, whose nickname was Beta" That would be the Beta release of Prime95 then? ;-) Cheers, Paul Landon _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
