Many thanks to Paul Landon for the very informative and enjoyable
trilogy about the history of computer testing of Mersenne numbers!
So Newman of Manchester was apparently the first - wait, I just got
an e-mail from someone with the handle [EMAIL PROTECTED] -
must work for some cryptography outfit. No, he goes on to explain that
"...Thanks to ze efforts of some enlightened mediums who are
knowledgeable about zis 'Internetz' of your modern era, selected
of us restless departed souls have been granted limited browsing
und e-mail privileges from ze great beyond. Zese mediums are
automatically transcribing ze voices zey hear, vich means zat
my missives vill probably sound like badly accented Tcherman,
even zo in reality mein written English ist sehr gut."
{Bunch of blah blah about his childhood and career snipped...
can we just cut to the chase here, fella?}
"...ze very first thing I typed into zis 'search maschine' was
ze phrase 'Mersenne prime', und I haff subsequently spent many
months vading sroo mostly tedious messages about 'Mein Komputer
ist so much faster zen yoors' und 'mein Hard drive ist very big',
but occasionally encountering an item of genuine interest, zo
ze accompanying mathematics ist usually ganz falsch. Ze recent
posting by Mr. P. Landon of Lucent Technologie vus very interesting,
but I must state for ze rekord zat I vas avare of zis at ze time.
After all, Newman vas really chust a persona I invented so I could
obtain verk in England. Ze phrase 'Neu Mann' translates into 'New
man' in English. Neumann/Newman - quite clever, nicht wahr?"
At this point this guy's delusions of grandeur just became too much, so
I added .crypt to my spam filter and got back to the truly grave business
of playing Quake.
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.
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.
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.
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.
Thanks again for the trilogy, Paul!
Cheers,
-Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
