Mersenne Digest Wednesday, 3 March 1999 Volume 01 : Number 519
----------------------------------------------------------------------
From: Paul Derbyshire <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 10:47:01 -0500
Subject: Re: Mersenne: Some diagrams
At 02:45 PM 2/28/99 -0800, you wrote:
>> http://main.amu.edu.pl/~florek
>
>I gotta 'cannot reach server' error on this
>
>a traceroute dies after 12 hops (last response was from
>tni-sto3-rc01-fe00.telenordia.se, 195.163.70.34 )
There is a probability topping 90% that this is caused by the Polish
infrastructure biting the bag. :-)
- --
.*. "Clouds are not spheres, mountains are not cones, coastlines are not
- -() < circles, and bark is not smooth, nor does lightning travel in a
`*' straight line." -------------------------------------------------
-- B. Mandelbrot |http://surf.to/pgd.net
_____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED]
Programmer & Humanist|ICQ: 10423848|
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Paul Derbyshire <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 10:50:22 -0500
Subject: Re: Mersenne: Spike - demonstrating calculating prowess
At 04:38 PM 2/28/99 -0800, you wrote:
>Ah, but a list of the first 37 Mersennes demonstrates that we, as a
>species, are advanced and are to be treated with respect, even by
>more advanced exosocieties.
Fallacious reasoning: we, being sentient individuals who are for the most
part good, are for the most part to be treated with respect, period. (Of
course, some of *us* have yet to get that, e.g. whoever runs things in
Beijing, and Suharto, and...)
- --
.*. "Clouds are not spheres, mountains are not cones, coastlines are not
- -() < circles, and bark is not smooth, nor does lightning travel in a
`*' straight line." -------------------------------------------------
-- B. Mandelbrot |http://surf.to/pgd.net
_____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED]
Programmer & Humanist|ICQ: 10423848|
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Paul Derbyshire <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 10:51:27 -0500
Subject: Mersenne: Missends...
To everyone who got a missent message from me today (about 5 of you): On
behalf of the person who hasn't made the list server interface less
error-prone, I apoloize for the waste of bandwidth.
- --
.*. "Clouds are not spheres, mountains are not cones, coastlines are not
- -() < circles, and bark is not smooth, nor does lightning travel in a
`*' straight line." -------------------------------------------------
-- B. Mandelbrot |http://surf.to/pgd.net
_____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED]
Programmer & Humanist|ICQ: 10423848|
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Jud McCranie <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 11:24:45 -0500
Subject: Re: Mersenne: Re: Mersennes for Martians
At 12:03 PM 3/1/99 -0800, Todd Sauke wrote:
> When this discussion started, I think the point
>was how impressive Lucas Lehmer testing is compared to brute force
>factoring.
Someone asked if there could be a better method for testing Mersenne numbers
than the L-L test. I think that the L-L test is essentially as efficient as
possible. However, I think that there is room for improvement in the
algorithms for doing the arithmetic involved.
+-----------------------------------------------------------+
| Jud McCranie [EMAIL PROTECTED] |
| |
| "We should regard the digital computer system as an |
| instrument to assist the number theorist in investigating |
| the properties of his universe - the natural numbers." |
| -- D. H. Lehmer, 1974 (paraphrased) |
+-----------------------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: "George Strohschein" <[EMAIL PROTECTED]>
Date: Tue, 2 Mar 1999 11:46:41 -0500
Subject: Mersenne: RE: Mersenne Digest V1 #517, Mathematica
Hi,
I tried to get Mathematica 3.0 to calculate that 37th prime, but gave up on
my old 60 MHz P5 (Gateway) after about half a day. I then tried it on a 200
Mhz CPU, but gave up again after about 6 hours. Can someone send me the
number so I can also print it out in 2 point font and see how big it really
is?
thanks,
George
> From: Luke Welsh <[EMAIL PROTECTED]>
> Date: Mon, 01 Mar 1999 17:57:34 -0800
> Subject: Mersenne: Mathematica's Parallel Computing Toolkit
>
> Beta
>
> "...parallel programming over a network of heterogeneous machines..."
>
> http://www.wolfram.com/news/parallel.html
>
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: "Stephen A. Wood" <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 11:49:25 -0500
Subject: Mersenne: Re: Mersenne Digest V1 #518
Whether the "humble joe" feels like his contribution is important or
not, I don't know, but the fact is that his contribution is important.
About a year ago, I compared the CPU time recorded by the top 100
contributors to the total. It was about 50%. I repeated the excercise
a couple of months ago, comparing the total CPU hours per day estimate
for the top 100 primenet contributors to the total daily output of
primenet. That time it was 25% of the time comes from the top 100
participants. So the "individual" members contribute most of the time,
and the next Mersenne Prime is more likely than not to come from someone
past 100 in the rankings.
But I'll still be sad when I am no longer in first place!!
Gordon Spence wrote:
>What bothers me most I guess is that the ordinary humble joe in the street
>being realistic has no chance whatever of finding the next mersenne prime.
>Over-reacting? maybe, but when people like templeu have over 300 machines
>of PPRO200/PII300+ running think about it. They are generating about 14
>months of cpu per day.
>If we are going to continue to recruit new *individual* members or thos
>like me who can get time on a few computers as opposed to hundreds then
>shouldn't we be thinking about splitting the rankings based on the numbers
>of machines being used.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Paul Leyland <[EMAIL PROTECTED]>
Date: Tue, 2 Mar 1999 09:05:29 -0800
Subject: RE: Mersenne: Re: Mersennes for Martians
> Someone asked if there could be a better method for testing
> Mersenne numbers
> than the L-L test. I think that the L-L test is essentially
> as efficient as
> possible. However, I think that there is room for improvement in the
> algorithms for doing the arithmetic involved.
That is a remarkably bold claim. It's akin to saying that the only way of
finding primes is by brute force testing of all candidates.
To me, at least, it is conceivable that some advance in number theory will
prove that there is a finite number of Mersenne primes and that their values
are given by a relatively simple formula. Consider the history of FLT
(number of solutions of a^n+b^n=c^n) for an analogous case. Initially, each
exponent was tested in turn; then it was shown that an infinite class of
exponents could not be a solution; finally it was shown that only a finite
number of exponents could be a solution and, in particular, only the
exponents 0, 1 and 2 were valid. The final result used non-trivial
mathematics but did not require large amounts of numerical computation.
Paul
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Petri Holopainen <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 18:33:02 +0100
Subject: Re: Mersenne: Fabs & Pentium III
Ethan Hansen wrote:
>
> PIII (non-Xeon): +6-8%; +12-15% for 96K FFT length. Speed increase appears
> to be from increased L1 cache, which makes sense as accessing the L1 is 2-6x
> faster than accessing L2.
>
FYI, the PIII has exactly the same size 16Kb + 16Kb L1 cache as the
PII.
- -- Petri H.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Petri Holopainen <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 18:33:02 +0100
Subject: Re: Mersenne: Fabs & Pentium III
Ethan Hansen wrote:
>
> PIII (non-Xeon): +6-8%; +12-15% for 96K FFT length. Speed increase appears
> to be from increased L1 cache, which makes sense as accessing the L1 is 2-6x
> faster than accessing L2.
>
FYI, the PIII has exactly the same size 16Kb + 16Kb L1 cache as the
PII.
- -- Petri H.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Paul Leyland <[EMAIL PROTECTED]>
Date: Tue, 2 Mar 1999 10:49:39 -0800
Subject: RE: Mersenne: Re: Mersennes for Martians
> exponents could not be a solution; finally it was shown that
> only a finite
> number of exponents could be a solution and, in particular, only the
> exponents 0, 1 and 2 were valid. The final result used non-trivial
I really must proof-read more carefully before posting. 0 is *not* a valid
exponent. The other two are, though 1 is trivial and it's easy to give an
infinite set of solutions for n=2. The non-trivial bit is proving that
these are the only exponents.
I don't know what I was thinking of! Sorry.
Paul
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Johnson Kent D <[EMAIL PROTECTED]>
Date: Tue, 2 Mar 1999 12:48:23 -0600
Subject: RE: Mersenne: Category 1,2 or 3 ?
Perhaps we've found the ideal place for that additional prize money that
several on the list are desiring to offer. Give the additional prize money
to the category 3 GIMPSer that discovers the next Mersenne prime. I'm sure
there are some flaws with this approach, but it's worth discussion. One
potential problem is verifying that the person is category 3 since it would
be somewhat of an "honor" call.
Kent D. Johnson
[EMAIL PROTECTED]
Jesus is Alive...Elvis Isn't!
> >From: Spike Jones <[EMAIL PROTECTED]>
> >Date: Mon, 01 Mar 1999 21:57:59 -0800
> >Subject: Mersenne: who has the most wicked-fast home setup?
> >
> >Let category 1 GIMPSers be set that contains those GIMPSers that
> >use a number of commercially owned or institutional computers, such
> >as the champion TempleU.
> >
> >Let category 2 GIMPSers be set that contains those GIMPSers that
> >use a combination of commercial and home computers.
> >
> >Let category 3 GIMPSers be set that contains those GIMPSers that
> >use only computers located in the home of that GIMPSer and owned
> >by that GIMPSer.
> >
> >Are there any cat 3 GIMPSers in the top 100 producers? Top 200?
> >Who is the highest ranking cat 3 GIMPSer?
>
> I have been thinking about this for quite a while now. When I
> joined GIMPS
> back in thee mosts of pre-history (well, Fall 96 actually)
> there were only
> about 800 or so volunteers in the project.
>
> In thos days it was quite easy to actually make a mark in the rankings
> table, I seem to recall at one point just after finding
> M2976221 that I
> moved up to about number 78 in the rankings.
>
> The only machines I had were a P100 (home, 24 hours), PPRO200
> (work, 24
> hours) and about 6 hours a day on 3 or 4 P166's.
>
> Nowadays I still have the trusty P100 that found the prime,
> but I also have
> 8 other machines that I can get some access time on, my
> ranking has now
> disappeared into the depths.
>
> What bothers me most I guess is that the ordinary humble joe
> in the street
> being realistic has no chance whatever of finding the next
> mersenne prime.
> Over-reacting? maybe, but when people like templeu have over
> 300 machines
> of PPRO200/PII300+ running think about it. They are
> generating about 14
> months of cpu per day.
>
> If we are going to continue to recruit new *individual*
> members or thos
> like me who can get time on a few computers as opposed to
> hundreds then
> shouldn't we be thinking about splitting the rankings based
> on the numbers
> of machines being used.
>
> Of course, if I could get my employer signed up and use all
> the 25,000+
> pc's then I may well change my mind ;-))
>
> regards
>
> G
>
>
>
> Gordon Spence, Nokia IP Telephony
> Applications Engineer Grove House, Waltham Way,
> [EMAIL PROTECTED] White Waltham, Maidenhead,
> http://www.nokiaiptel.com/ Berkshire, SL6 3TN, UK.
>
> ________________________________________________________________
> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
>
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Jud McCranie <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 14:13:44 -0500
Subject: RE: Mersenne: Re: Mersennes for Martians
At 10:49 AM 3/2/99 -0800, Paul Leyland wrote:
>I really must proof-read more carefully before posting. 0 is *not* a valid
>exponent. The other two are, though 1 is trivial and it's easy to give an
>infinite set of solutions for n=2. The non-trivial bit is proving that
>these are the only exponents.
Actually n=2 is trivial too. You don't have to show that there are an infinite
number of solutions (in positive integers) for n=2, you only need to show one,
e.g. 3^2 + 4^2 = 5^2.
+-----------------------------------------------------------+
| Jud McCranie [EMAIL PROTECTED] |
| |
| "We should regard the digital computer system as an |
| instrument to assist the number theorist in investigating |
| the properties of his universe - the natural numbers." |
| -- D. H. Lehmer, 1974 (paraphrased) |
+-----------------------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Marc Getty <[EMAIL PROTECTED]>
Date: Tue, 02 Mar 1999 18:08:25 -0500
Subject: Mersenne: Categories 1,2 or 3?
> What bothers me most I guess is that the ordinary humble joe in the street
> being realistic has no chance whatever of finding the next mersenne prime.
> Over-reacting? maybe, but when people like templeu have over 300 machines
> of PPRO200/PII300+ running think about it. They are generating about 14
> months of cpu per day.
Actually closer to 22-23 months per day now, with 285 machines. I do
feel
guilty about making it difficult for an individual or group to make it
to
the top. I do NOT feel that I have much more of a chance then an average
individual does at finding the next Mersenne Prime though. The guy who
spends hundreds, even thousands of dollars on lottery tickets does not
have that much more of a chance at winning the lottery then the guy who
only buys one ticket. The odds of finding a Mersenne Prime are so small
that
I do not expect to ever find one, even though it would be nice! Over
time
the TempleU-CAS account will drop down from #1 and will be replaced by
some other Johnny-Come-Lately, our machines are aging and will be
obsolete
sooner then you think!
In order to categorize who belongs in what category, I propose that
IPS be expanded to allow an account to display a URL where the account
can post information about their account and their status. SUNY Albany
did this, as did team love fest, and did I.
See:
http://hawk.fab2.albany.edu/mersenne/mersenne.htm
http://etc.temple.edu/gimps/
http://myhouse.com/love/fest/team/index.html
Marc Getty - [EMAIL PROTECTED] - [EMAIL PROTECTED] - ICQ: 12916278
http://www.getty.net - http://www.vwthing.org Work: 215-204-3291
http://etc.temple.edu/ Home: 215-322-8363
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Tony Forbes <[EMAIL PROTECTED]>
Date: Tue, 2 Mar 1999 23:33:01 +0000
Subject: Re: Mersenne: Double-checking (was Chronons)
George Woltman <[EMAIL PROTECTED]> writes
>Finding an error in the first LL test is not rare. I've said about 1 in
>200 are incorrect. When the entire 1,400,000 - 2,000,000 range has
>been double-checked I'll perform some more rigorous analysis of the
>reliability of first-time LL results.
This is slightly worrying. The number of CPU cycles for performing the
LL-test for exponent n is approximately proportional to n^2*log(n).
Assuming, maybe rather naively, that the risk of computer error is
proportional to the number of CPU cycles, the LL-test for a typical
exponent of around 6000000 could be about 9.7 times less reliable than
for one in the vicinity of 2000000.
However, modern Pentium-IIs and memory chips are probably much more
reliable than the 486's and ordinary Pentiums that did the LL-tests in
the range 1400000 to 2000000. On the other hand, an error rate of 1/20
is just about acceptable. Do we have any statistics for the larger
exponents?
- --
Tony
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: [EMAIL PROTECTED]
Date: Tue, 2 Mar 1999 19:38:48 EST
Subject: Mersenne: Re: Mersenne Digest V1 #517
Not only would we be the first 50,000 to grok it, we'd also listen VERY, VERY
intently to what they say after 3021377. Hrm. :-D
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]>
Date: Wed, 3 Mar 1999 00:33:04 -0500 (EST)
Subject: Mersenne: CAMP
http://project.vobis.de/cgi-bin/mersenne.cgi
does not seem to work. What's up?
Is there a substitute (I am not on primenet).
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Ken Kriesel <[EMAIL PROTECTED]>
Date: Wed, 03 Mar 1999 00:24:51 -0600
Subject: Re: Mersenne: mersennes for exocivilizations
At 10:30 AM 1999/03/02 -0500, Paul Derbyshire <[EMAIL PROTECTED]> wrote:
>At 12:07 AM 3/1/99 -0800, you wrote:
>>At 11:17 PM 2/28/99 -0800, Spike Jones wrote:
>>>It would not surprise me at all if instead of a list of primes, they
>>>send us the series 2,3,5,7,13,19,31,61,89,107,127,521...
>>
>>or 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 perhaps?
>
>This one doesn't even ring a bell. The same Mersenne primes in it though,
>and also some Fermat primes. (3, 5, 17, 257).
The first list, p=2,3,5,7,13,19,31,61,89,107,127,521,...
is the list of exponents which generate Mersenne primes, as in Mp= 2^p - 1
The second list, p=2,3,5,7,13,17,19,31,67,127,257
is the list of exponents Marin Mersenne thought generated Mersenne primes.
He was mostly right, but both included exponents that generate composites,
and excluded exponents that generate primes.
Stating the exponents rather than the base10 representation seems to
me to be almost the ultimate in data compression. (2^521-1 has 157 digits;
the advantage increases along with the exponent, uh, exponentially.)
Ken
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Ken Kriesel <[EMAIL PROTECTED]>
Date: Wed, 03 Mar 1999 01:31:35 -0600
Subject: RE: MHZ (was re Mersenne: Fabs.)
At 07:36 AM 1999/03/02 -0800, Paul Leyland <[EMAIL PROTECTED]> wrote:
>> >When I was working with some of the first digital designs in the
>> >100-600 MHz range over 25 years ago...
I suspect the original comment above relates to working with the simpler
digital logic components of the day, not whole processors' clock rate.
As a reference point, a 1985 Fairchild F100K ECL Data book mentions
counters, registers, and flip-flops useful in the 400-500Mhz range.
Schottky TTL
of the same period was capable of about 100-125Mhz in flipflops.
Special purpose devices such as frequency counter prescalers were available
in the gigahertz range. (In July 1981 a 1250. Mhz prescaler chip could be had
for $35.00.) The 1972 Radio Amateur's Handbook mentions both analog IC's
(differential amplifiers) operating up to 100Mhz, and a prescaler operating
up to 320Mhz. (A prescaler is a circuit that divides a clock pulse train
down to a slower frequency by a fixed factor, such as by 10.)
>> Oops. I don't know if this is an extra-zeroes issue or a "M"
>> instead of a
>> "K" or what, but just 10 years ago 1 MHz was good and 7 MHz
>> was high end.
>> 25 years ago, I very much doubt they were bandying about
>> 600MHz anything,
>> since we're only just reaching the 600MHz level now at the
>> end of the 1990s!
>>
>> [Excessive quoted material snipped]
>
>[Excessive signature snipped 8-]
>
>Eh? My first job after finishing my DPhil was microcoding a AMD-2900 series
>bit slice machine which had a 25ns (40MHz) clock. That was in 1983 and it
>was far from rocket science then. Actually, I started (unpaid) work on it a
>couple of years earlier, so we're actually talking about 18 years ago.
>
>The good old 1970's Cray-1 had a 9ns (110MHz) clock if I remember correctly.
>
>*Twenty* years ago, a 4MHz Z80A was a commodity chip. I still have a 1979
>model 380Z from Research Machines with that very cpu. (Incidentally, RM is
>one of the few companies of that era still making PCs.)
>
>I can't remember when I bought my 25MHz 386, but it must be approaching 10
>years ago.
>
>
>Paul
1977: 1Mhz 6502 or 4Mhz Z80 (also the Vax 11/780; Mhz?)
1981: 4.77Mhz 8088 in the IBM PC
1984: 6Mhz 80286 in the IBM AT
1986: 16Mhz 80386 in a Compaq
1990: 33Mhz 80386 (mine just turned 9 & still runs, with its third hard drive;
the first drive cost about $10/MB)
Mhz alone is not a direct measure of performance, even with equal word size.
In 1983 I programmed a single-board PDP-11 clocked around 21Mhz in assembler,
and since it had no multiply or divide instruction, it took
about 480 microseconds to do a 16x16 unsigned integer multiply, which is
far longer than the 30 microseconds or so that a 4.77Mhz 8088 would take.
Ken
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Date: Wed, 3 Mar 1999 09:20:55 GMT
Subject: RE: Mersenne: Re: Mersennes for Martians
> > Someone asked if there could be a better method for testing
> > Mersenne numbers
> > than the L-L test. I think that the L-L test is essentially
> > as efficient as
> > possible. However, I think that there is room for improvement in the
> > algorithms for doing the arithmetic involved.
>
> That is a remarkably bold claim. It's akin to saying that the only way of
> finding primes is by brute force testing of all candidates.
How about a clever method of computing just the last few bits of
the residual - if we could work mod 2^64 instead of mod 2^p-1 then
that would give essentially a *huge* speed increase, even if the
algorithm was a great deal more complex.
Of course, there is still (approx) 1 chance in 1.8E19 (2^64) that the whole
residual is non-zero even though the low-order 64 bits are zero, so,
in the rare event we computed Res64 = 0, we'd still have to run a
full LL test.
Also, if you can find quicker arithmetic algorithms, then *please*
get in touch with Donald Knuth! There may be some (fairly small)
scope for improvement in the implementation - but, to get a major
advance, we're going to need dedicated hardware. I believe the
Chudnovskys (apologies if I've misspelled their name) had
dedicated hardware that could do a 2^20 bit by 2^20 bit
multiplication in less than a microsecond, about 15 years ago.
(Reference, "The Joy of Pi") That sort of raw power would be
*exceedingly* useful for LL testing, but is unlikely to find its way
into consumer products - unless someone can think of a "killer
application" that would make hardware implementation of this sort
of instruction essential!
> To me, at least, it is conceivable that some advance in number theory will
> prove that there is a finite number of Mersenne primes and that their values
> are given by a relatively simple formula.
I agree... except I'd replace "and" by "and/or".
In any event, I don't think the proof will fit in the margin of this
e-mail ;->
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #519
******************************
