Mersenne Digest Monday, November 5 2001 Volume 01 : Number 901 ---------------------------------------------------------------------- Date: Sun, 4 Nov 2001 23:41:58 +0100 From: =?utf-8?Q?Torben_Schl=C3=BCntz?= Subject: SV: SV: Mersenne: Strange factor arrived though not calculating it Yes I did check all prime.log and all results.txt. I would never have missed it if it had been mentioned in any of these files. You probably also did not notice that I have all results I have produced going to a special file called: Results.all (how creative I am :-) ), and this process is done automagicly by a script? br tsc OK. Did you look through the contents of prime.log on whichever system once had exponent 16871993? If the exponent was dropped because PrimeNet informed the system the job was already done, the evidence will be in there. If the system really did run that exponent, found the factor & informed PrimeNet, the evidence will also be in there. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 4 Nov 2001 14:50:50 -0800 From: "Aaron Blosser" Subject: RE: Mersenne: SMT I kind of like the practice that many dual processor folks have seem to adopted (and one which I'll be switching my group of computers too)... Namely, on dual CPU systems, have one Prime process doing LL tests, and have the other one doing trial factoring. Even on Compaq servers that have GREAT cache/memory management, running 2 LL tests on each CPU will slow down both processes. Running one LL and one factor reduces the hit on the memory subsystem since the factoring can generally remain in the CPU cache of it's respective processor, leaving the LL process to better use the memory for itself. So perhaps this same approach could be adopted for SMT? And just a reminder... trial factoring is still a great use of slower machines... I have an AMD K6-III 400 that can trial factor the current 17M exponents in just about 2 days. Yeah, P4's can do it a lot faster, or 1.2GHz Athlons, but I'd rather have those machines concentrate on the LL tests. Aaron > -----Original Message----- > From: mersenne-invalid-reply-address@base.com [mailto:mersenne-invalid- > reply-address@base.com] On Behalf Of bjb@bbhvig.uklinux.net > Sent: Sunday, November 04, 2001 1:36 PM > To: Kel Utendorf > Cc: mersenne@base.com > Subject: Re: Mersenne: SMT > > On 3 Nov 2001, at 21:40, Kel Utendorf wrote: > > > At 21:01 11/03/2001 -0500, George Woltman wrote: > > >Can prime95 take advantage of SMT? I'm skeptical. If the FFT is > > broken >up to run in two threads, I'm afraid L2 cache pollution will > > negate any >advantage of SMT. Of course, I'm just guessing - to test > > this theory out we >should compare our throughput running 1 vs. 2 > > copies of prime95 on an >SMT machine. > > I'm not sure I fully understand the way in which a SMT processor > would utilise cache. But I can't see how the problem could be > worse than running two copies of a program on a SMP system. > This seems to work fairly well in both Windows and linux regimes > (attatching a thread to a processor and therefore its associated > cache, rigidly in the case of Windows, loosely but intelligently in > the case of linux). > > If an SMT processor has a unified cache, cache pollution should > surely be not too much of a problem? Running one copy & thereby > getting benefit of the full cache size would run that one copy faster, > (just as happens with SMP systems where memory bandwidth can > be crucial) but the total throughput with two copies running would > surely be greater. Especially on a busy system, where two threads > get twice as many timeslices as one! > > If there is some way in which the FFT could be broken down into > roughly equal sized chunks, it _might_ be worth synchronizing two > streams so that e.g. transform in on one thread was always in > parallel with transform out on the other, and vice versa. Obviously > you'd need to be running on two different exponents but using the > same FFT length to gain from this technique. Whether this would > be any better than running unsynchronized would probably require > experimentation. > > > > Could things be setup so that factoring and LL-testing went on > > "simultaneously?" This would speed up the overall amount of work > > being done. > > Because trial factoring, or P-1/ECM on _small_ exponents, have a > very low memory bus loading, running a LL test and factoring in > parallel on a dual-processor SMP system makes a lot of sense. I > suspect the same situation would apply in an SMT environment. > > The "problem" of mass deployment (almost everyone in this > position, instead of only a few of us) is that there is a great deal of > LL testing effort required in comparison to trial factoring, so running > two LL tests in parallel but inefficiently would bring us to > "milestones" faster than the efficient LL/trial factoring split. > > > Regards > Brian Beesley > ________________________________________________________________________ _ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 00:02:30 +0100 From: =?utf-8?Q?Torben_Schl=C3=BCntz?= Subject: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? What will we do when anyone finds a number of 10 million+ digits which is prime? Will everybody just leave the project because there is no prize to gain any longer? After the introduction of "search for 10 million digits number" this could leave the project with quite a big hole, say from M14.xxx.xxx and up till the exponent found. It will be kind of difficult to find new volunteers that will use time and electricity to fill the hole if nothing more than glory is won. Will there be an other prize? Will there be a new goal? We have the 4 or 5 biggest primes, are anyone stressing us by using another algorithm like the LL, have access to more CPU, working on a bulletproof method of generating new primes? br tsc _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 4 Nov 2001 15:19:56 -0800 From: "John R Pierce" Subject: Re: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? > What will we do when anyone finds a number of 10 million+ digits which > is prime? that would be a number up aruond 2^32000000, a place we are very very far from. - -jrp _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 00:24:55 +0100 From: "Steinar H. Gunderson" Subject: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? On Mon, Nov 05, 2001 at 12:02:30AM +0100, Torben Schlüntz wrote: >What will we do when anyone finds a number of 10 million+ digits which >is prime? Spread the prize according to the rules on the website, and continue searching? ;-) >Will everybody just leave the project because there is no prize to gain >any longer? Considering that the project worked very well for years (actually, a whole lot longer than we've had a prize) before EFF announced its prize, I doubt so. :-) >After the introduction of "search for 10 million digits number" this >could leave the project with quite a big hole, say from M14.xxx.xxx and >up till the exponent found. Well, then we'll do our best to fill such a hole, won't we? :-) >It will be kind of difficult to find new volunteers that will use time >and electricity to fill the hole if nothing more than glory is won. Doubtful (see my comments above). >Will there be an other prize? >Will there be a new goal? EFF has a prize for a 100+ million digit prime, and a 1000+ million digit prime. The first prize (which has already been awarded) also went out to a GIMPS member, discovering the first 1+ million digit prime. :-) /* Steinar */ - -- Homepage: http://www.sesse.net/ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 18:24:07 -0500 From: Jud McCranie Subject: Re: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? At 12:02 AM 11/5/2001 +0100, =?utf-8?Q?Torben_Schl=C3=BCntz?= wrote: >It will be kind of difficult to find new volunteers that will use time >and electricity to fill the hole if nothing more than glory is won. I'm not in it for the prize, and a lot of others aren't either. I've been it over 4 years (maybe over 5 years?), well before there were any prizes. I just replaced a computer that I have been using over 4 years, and I think I was in GIMPS before I had that one. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 4 Nov 2001 15:43:13 -0800 From: "Aaron Blosser" Subject: RE: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? Well, there's still plenty of people who'll stick to it. There's a lot of hardcore GIMPSers who are more than willing to keep crunching numbers alive (some even willing to risk getting the FBI on their case) :) Besides the "big ticket" things like finding the megadigit prime and a ten megadigit prime, there's still all the other work of testing all the exponents in between, confirming that Mersenne Prime XX is really the XXth prime (and we didn't just miss any in-between). There's the double-checking work, and I still think it's cool when I find a really big factor (anything over 80 bits is fun to find) of a Mersenne number. I'm sure a lot of folks would just give up, but personally, I'd contribute to some fund for a "prize" for the other Prime numbers we find along the way. Just my 2 cents worth. > -----Original Message----- > From: mersenne-invalid-reply-address@base.com [mailto:mersenne-invalid- > reply-address@base.com] On Behalf Of Torben Schlüntz > Sent: Sunday, November 04, 2001 3:03 PM > To: mersenne@base.com > Subject: Mersenne: What will we do when anyone finds a number of 10 > million+ digits which is prime? > > What will we do when anyone finds a number of 10 million+ digits which > is prime? > > Will everybody just leave the project because there is no prize to gain > any longer? > > After the introduction of "search for 10 million digits number" this > could leave the project with quite a big hole, say from M14.xxx.xxx and > up till the exponent found. > > It will be kind of difficult to find new volunteers that will use time > and electricity to fill the hole if nothing more than glory is won. > > Will there be an other prize? > Will there be a new goal? > > We have the 4 or 5 biggest primes, are anyone stressing us by using > another algorithm like the LL, have access to more CPU, working on a > bulletproof method of generating new primes? > > br > tsc > > ________________________________________________________________________ _ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 19:21:18 -0500 From: George Woltman Subject: Re: Mersenne: SMT At 09:35 PM 11/4/2001 +0000, bjb@bbhvig.uklinux.net wrote: >I'm not sure I fully understand the way in which a SMT processor >would utilise cache. This is a prime95 problem, not a SMT problem. Prime95 is designed to run efficiently in 128KB of L2 cache. If I split the current FFT into 2 threads, then either each thread is going to want 128KB of L2 cache space (more cache contention) or I must recode the "passes" of prime95 to run efficiently in just 64KB of cache (this might be a bad idea as using less L2 cache may require adding another "pass" over the FFT data - at least for some FFT sizes). That is why I fear that SMT may not be helpful to prime95. Another way of saying this is prime95 may be more constrained by L2 cache sizes than it constrained by micro-op scheduling. However, I had not considered the idea of factoring and LL testing. Even better, if we make the factoring code use mostly integer instructions then the LL test thread would keep the FPU units busy and the factoring thread would keep the integer units busy! Then the only question becomes "Does the user want to slow down his LL tests in order to increase his total (LL + factoring) throughput". - -- George _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 01:20:03 +0100 From: Lars Lindley Subject: Re: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? > I'm sure a lot of folks would just give up, but personally, I'd > contribute to some fund for a "prize" for the other Prime numbers > we find along the way. > > Just my 2 cents worth. If we put 2 cents for every computer in GIMPS we would get $600 total :) I would be thrilled to get $600 for finding a prime... /Lars _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 19:27:35 -0500 From: George Woltman Subject: Re: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? Hi, At 12:02 AM 11/5/2001 +0100, =?utf-8?Q?Torben_Schl=C3=BCntz?= wrote: >What will we do when anyone finds a number of 10 million+ digits which >is prime? > >Will everybody just leave the project because there is no prize to gain >any longer? Careful reading of the prize rules show that $20,000 would go to GIMPS primarily to fund future awards. My goal would be $5000 per prime. That should keep us funded for a decade. Of course this is all very wishful thinking. It would take about 20,000 top-of-the-line P4 systems a year to have a 50% chance of finding a 10M prime. We will find it one day, but it is more likely to be when 5 and 10 GHz P4s are commonplace. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 01:43:17 +0100 From: "Steinar H. Gunderson" Subject: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? On Sun, Nov 04, 2001 at 07:27:35PM -0500, George Woltman wrote: >Of course this is all very wishful thinking. It would take about 20,000 >top-of-the-line P4 systems a year to have a 50% chance of finding a >10M prime. We will find it one day, but it is more likely to be when >5 and 10 GHz P4s are commonplace. Speaking of which -- shouldn't we be (statistically) really close to finding a new prime soon? /* Steinar */ - -- Homepage: http://www.sesse.net/ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 20:09:20 -0500 From: Jud McCranie Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? At 01:43 AM 11/5/2001 +0100, Steinar H. Gunderson wrote: >Speaking of which -- shouldn't we be (statistically) really close to finding >a new prime soon? Yes, statistically. You'd "expect" the next one to be before 14,000,000 and I've got assignments in the 13,000,000 range. However, all exponents have been checked once only to a little past 8,000,000. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 20:19:35 -0500 From: Michael Vang Subject: Re: Mersenne: SMT George Woltman wrote: > This is a prime95 problem, not a SMT problem. Prime95 is designed to > run efficiently in 128KB of L2 cache. George- Are there any gains to be had if you code it to fit a 256KB L2? If so, maybe we should have 2 versions? :) Also, how do you think the new .13 micron Tualatin CPUs will do for Prime95? I read someting about a new pre-fetch mechanism (?) but I didn't quite grasp what it meant... The newer PIIIs (1.13 & 1.26GHZ, IIRC...) have an option for 512KB... Thanks! Xyzzy [81/117.943/94/9.801/801.750] http://www.teamprimerib.com/ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 20:48:36 -0500 From: Nathan Russell Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? On Sun, 04 Nov 2001 20:09:20 -0500, Jud McCranie wrote: > >At 01:43 AM 11/5/2001 +0100, Steinar H. Gunderson wrote: > >>Speaking of which -- shouldn't we be (statistically) really close to finding >>a new prime soon? > >Yes, statistically. You'd "expect" the next one to be before 14,000,000 >and I've got assignments in the 13,000,000 range. However, all exponents >have been checked once only to a little past 8,000,000. Of course, this whole argument makes (as far as I can see) heavy use of the gamblers' fallacy, aka the fallacy of maturation of probabilities ("Hey, I lost the last 50 games - what are the odds against me losing 51 5-man games in a row? I'm certain to win!") Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 4 Nov 2001 18:31:05 -0800 From: "Aaron Blosser" Subject: RE: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? Hmm... in games of chance, each game's outcome is independent of the results of past games, so that is a valid point. In Mersenne Prime hunting though, I think it's safe to say that statistically there should be some prime numbers in the range we're checking, so the more we *don't* find, the higher the odds of the remaining ones being prime. :) In other words, there is a certain sort of dependence on previous outcomes. In gambling terms, that's like saying that perhaps you could guarantee winning one game out of every 50 hands of poker (alright, so he's a lousy player). If you lost 49 times, and you know you would win 1 out of 50 times, then yes, there's a 100% chance you'll win the next hand. :) What's a bigger issue here is whether or not the statistical model for how many primes we expect to find in a given range is accurate or not. Since the probabilities are based purely on the spread of previous primes, the sample data is pretty small, and there's already a jagged curve to the whole thing, so any probabilities are likely to be off by a good amount in practice. I know we did lots of analyses prior to finding the last one, and I'm curious how well that # fit any of the odds people had formulated. Aaron > -----Original Message----- > From: mersenne-invalid-reply-address@base.com [mailto:mersenne-invalid- > reply-address@base.com] On Behalf Of Nathan Russell > Sent: Sunday, November 04, 2001 5:49 PM > To: mersenne@base.com > Subject: Re: Mersenne: Re: What will we do when anyone finds a number of > 10 million+ digits which is prime? > > On Sun, 04 Nov 2001 20:09:20 -0500, Jud McCranie > wrote: > > > > >At 01:43 AM 11/5/2001 +0100, Steinar H. Gunderson wrote: > > > >>Speaking of which -- shouldn't we be (statistically) really close to > finding > >>a new prime soon? > > > >Yes, statistically. You'd "expect" the next one to be before 14,000,000 > >and I've got assignments in the 13,000,000 range. However, all exponents > >have been checked once only to a little past 8,000,000. > > Of course, this whole argument makes (as far as I can see) heavy use > of the gamblers' fallacy, aka the fallacy of maturation of > probabilities ("Hey, I lost the last 50 games - what are the odds > against me losing 51 5-man games in a row? I'm certain to win!") > > Nathan > ________________________________________________________________________ _ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 21:46:58 -0500 From: Jud McCranie Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? At 08:48 PM 11/4/2001 -0500, Nathan Russell wrote: >Of course, this whole argument makes (as far as I can see) heavy use >of the gamblers' fallacy, aka the fallacy of maturation of >probabilities ("Hey, I lost the last 50 games - what are the odds >against me losing 51 5-man games in a row? I'm certain to win!") Statistically, each exponent resulting in a prime is about twice the previous one. There is a heuristic argument that supports that being the case. The last one was 6.9 million something, we're now testing close to twice that. I think there are only three cases where one exponent is more than twice as large as the previous one. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 04 Nov 2001 23:59:18 -0500 From: Nathan Russell Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? On Sun, 04 Nov 2001 21:46:58 -0500, Jud McCranie wrote: >At 08:48 PM 11/4/2001 -0500, Nathan Russell wrote: > >>Of course, this whole argument makes (as far as I can see) heavy use >>of the gamblers' fallacy, aka the fallacy of maturation of >>probabilities ("Hey, I lost the last 50 games - what are the odds >>against me losing 51 5-man games in a row? I'm certain to win!") > >Statistically, each exponent resulting in a prime is about twice the >previous one. There is a heuristic argument that supports that being the >case. The last one was 6.9 million something, we're now testing close to >twice that. I think there are only three cases where one exponent is more >than twice as large as the previous one. P1 P2 ratio 127 521 4.102362205 607 1279 2.10708402 4423 9689 2.190594619 216091 756839 3.502408707 1398269 2976221 2.128503886 and, almost certainly, 3021377 6972593 2.307753385 It looks like there's some clumpiness around ratios of 2.1, but I suspect that's an artifact of the cutoff point you gave. I wouldn't know how to check statistically, and the sample size is probably too small anyhow. I don't know whether the second-largest gap is an outlier, but the largest definately is. It might be noted that there are only 98-31-1=66 primes between 127 and 521 (exclusive); I don't know offhand whether this is significant. The gaps with ratio < 1.1 follow, for those who are curious. 4423 4253 1.039971785 9941 9689 1.026008876 21701 19937 1.088478708 23209 21701 1.069489885 3021377 2976221 1.01517226 I don't see any outliers here. I might note that gaps of this size aren't even possible until after 29 (31/29=1.077, and 19/17=1.118, thus excluding gaps beginning with the first seven Mersennes before the primes above them are even calculated) Any comments from the list? Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 01:45:02 -0600 From: "Steve Harris" Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? Nathan, I'll tell you what jumped out at me from your list of "large" (>2) gaps: there are exactly zero instances of _consecutive_ gaps larger than a factor of 2. Also, the larger gaps tend to be adjacent to the smaller gaps, and vice-versa, although that is not always the case. Now granted we are still working with a small sample, but if the next mersenne prime turns out to be greater than M13945xxx then it would be the first instance of consecutive gaps greater than 2. Although this is far from proof, it is a good reason to expect the next one to be smaller than that. I personally expected the next one to be around M10million; that still hasn't been ruled out as there are many exponents below 11million which have not yet been tested. I agree that the "gambler's fallacy" does not apply as these are not unrelated outcomes, but then again we don't actually know for sure if there even ARE any more Mersenne primes. Regards, Steve Harris - -----Original Message----- From: Nathan Russell To: Jud McCranie Cc: mersenne@base.com Date: Monday, November 05, 2001 12:03 AM Subject: Re: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? >On Sun, 04 Nov 2001 21:46:58 -0500, Jud McCranie > wrote: > >>At 08:48 PM 11/4/2001 -0500, Nathan Russell wrote: >> >>>Of course, this whole argument makes (as far as I can see) heavy use >>>of the gamblers' fallacy, aka the fallacy of maturation of >>>probabilities ("Hey, I lost the last 50 games - what are the odds >>>against me losing 51 5-man games in a row? I'm certain to win!") >> >>Statistically, each exponent resulting in a prime is about twice the >>previous one. There is a heuristic argument that supports that being the >>case. The last one was 6.9 million something, we're now testing close to >>twice that. I think there are only three cases where one exponent is more >>than twice as large as the previous one. > >P1 P2 ratio >127 521 4.102362205 >607 1279 2.10708402 >4423 9689 2.190594619 >216091 756839 3.502408707 >1398269 2976221 2.128503886 > >and, almost certainly, > >3021377 6972593 2.307753385 > >It looks like there's some clumpiness around ratios of 2.1, but I >suspect that's an artifact of the cutoff point you gave. I wouldn't >know how to check statistically, and the sample size is probably too >small anyhow. > >I don't know whether the second-largest gap is an outlier, but the >largest definately is. It might be noted that there are only >98-31-1=66 primes between 127 and 521 (exclusive); I don't know >offhand whether this is significant. > >The gaps with ratio < 1.1 follow, for those who are curious. > >4423 4253 1.039971785 >9941 9689 1.026008876 >21701 19937 1.088478708 >23209 21701 1.069489885 >3021377 2976221 1.01517226 > >I don't see any outliers here. I might note that gaps of this size >aren't even possible until after 29 (31/29=1.077, and 19/17=1.118, >thus excluding gaps beginning with the first seven Mersennes before >the primes above them are even calculated) > >Any comments from the list? > >Nathan >_________________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm >Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 05 Nov 2001 09:18:14 +0100 From: Henk Stokhorst Subject: Re: Mersenne: What will we do when anyone finds a number of 10 million+ digits which is prime? - --------------030702020909040906000004 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Lars Lindley wrote: > If we put 2 cents for every computer in GIMPS we would get $600 total > [:)] > > I would be thrilled to get $600 for finding a prime... > Eeehhhh, I think the winner should award all the participants 2 cents. (Costs a lot less if you count only the computers checking in results) YotN, Henk Stokhorst. - --------------030702020909040906000004-- _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 18:44:06 -0000 From: bjb@bbhvig.uklinux.net Subject: RE: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? On 4 Nov 2001, at 18:31, Aaron Blosser wrote: > Hmm... in games of chance, each game's outcome is independent of the > results of past games, so that is a valid point. Precisely. > > In Mersenne Prime hunting though, I think it's safe to say that > statistically there should be some prime numbers in the range we're > checking, so the more we *don't* find, the higher the odds of the > remaining ones being prime. :) In other words, there is a certain > sort of dependence on previous outcomes. WRONG! "Statistically" you would expect there would be 3 or 4 Mersenne primes with exponents between 127 & 521, "surely" at least one? Nah! A truly random distribution will have both unexpectedly dense clumps and unexpectedly long gaps. > > What's a bigger issue here is whether or not the statistical model for > how many primes we expect to find in a given range is accurate or not. > Since the probabilities are based purely on the spread of previous > primes, the sample data is pretty small, and there's already a jagged > curve to the whole thing, so any probabilities are likely to be off by > a good amount in practice. I thought there was a purely theoretical argument involving Euler's Constant which resulted in the "average" ratio of consecutive Mersenne primes being approximately 1.45. > > I know we did lots of analyses prior to finding the last one, and I'm > curious how well that # fit any of the odds people had formulated. As STL pointed out, we appear to be "missing" one somewhere round 4 million. And possibly another somewhere round 10 million? Conversely, we might discover _two_ tomorrow! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 5 Nov 2001 19:33:21 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: SMT On 4 Nov 2001, at 19:21, George Woltman wrote: > At 09:35 PM 11/4/2001 +0000, bjb@bbhvig.uklinux.net wrote: > >I'm not sure I fully understand the way in which a SMT processor > >would utilise cache. > > This is a prime95 problem, not a SMT problem. Prime95 is designed to > run efficiently in 128KB of L2 cache. This is interesting. (1) How much of the extra performance of the Athlon family processors is attributable to having 128KB L1 cache? Durons seem to run Prime95/mprime quite well, despite having only 64KB L2 cache. (2) The "old" benchmarks (v20) consistently showed "old" Athlon & Katmai PIII (which had 512KB of L2 cache running below core speed) outperforming Thunderbird & Coppermine PIII (256KB L2 cache at full core speed) respectively. Typically by around 4%. I just assumed that the extra L2 cache was doing more good than harm, despite running at half speed - or even less on faster Athlons! (3) Conversely I found about three years ago (probably running v16) that a particular Celeron 266 system (_no_ L2 cache) ran Prime95 a bit faster than a similar system with a PII-266 (same internals, but 512KB half-speed L2 cache). Probably this was a chipset/memory artifact but it does seem to point at L2 cache size/speed not being _crucially_ important. Now I'm not doubting that the more & the faster, the better, I'm just saying that the effect seems to be significant rather than overwhelming. > If I split the current FFT into > 2 threads, then either each thread is going to want 128KB of L2 cache > space (more cache contention) or I must recode the "passes" of prime95 > to run efficiently in just 64KB of cache (this might be a bad idea as > using less L2 cache may require adding another "pass" over the FFT > data - at least for some FFT sizes). Except that larger caches seem to be the order of the day - Celerons seem to be moving up to 256KB L2 and PIIIs to 512KB L2 now (or at least in the near future) - I doubt that SMT processors will come equipped with less than 256KB. In which case two threads each consuming 128KB seems to be realistic. Certainly I don't think we ought/need to be messing around with tuned versions; there's enough complication in the code & the efficiency improvements would seem to be small. > > However, I had not considered the idea of factoring and LL testing. > Even better, if we make the factoring code use mostly integer > instructions then the LL test thread would keep the FPU units busy and > the factoring thread would keep the integer units busy! Then the only > question becomes "Does the user want to slow down his LL tests in > order to increase his total (LL + factoring) throughput". _If_ SMT appears to the OS to be SMP (which I thought was the point - SMT is effectively a cheap way of mounting two processors in one package), then surely the user will have to run two processes. There is no design problem; at present a user with a dual-processor system can elect to run LL testing on one processor & trial factoring on the other - or LL testing on both, if he wishes. The problem, of course, is that probably 90% of users will be using an operating system that doesn't support SMP. Windows XP Home Edition (which is what is likely to be installed on new systems) supports only single-processor systems, just like Win 9x/ME. If you want dual processor support, you have to buy XP Professional Edition, at a considerable price premium. Or switch to linux, in which case SMP support is free :) Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 05 Nov 2001 14:47:20 -0500 From: Jud McCranie Subject: RE: Mersenne: Re: What will we do when anyone finds a number of 10 million+ digits which is prime? At 06:44 PM 11/5/2001 +0000, bjb@bbhvig.uklinux.net wrote: >A truly random distribution will have both unexpectedly dense >clumps and unexpectedly long gaps. I don't know if you would call them "unexpected", since you expect them. But very long gaps are rare. Also, I don't know if the distribution of Mersenne primes is truly random, for instance that heuristic estimate *might* have upper and lower bounds. There are upper and lower bounds on pi(x) and several other number theory functions (sigma, phi, etc). +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 05 Nov 2001 18:35:19 -0500 From: George Woltman Subject: Re: Mersenne: SMT At 07:33 PM 11/5/2001 +0000, bjb@bbhvig.uklinux.net wrote: >(1) How much of the extra performance of the Athlon family >processors is attributable to having 128KB L1 cache? Durons >seem to run Prime95/mprime quite well, despite having only 64KB >L2 cache. OK, a bit more detail than most people want... Prime95, when not running the SSE2 code, performs the FFT in two passes. The second pass runs through main memory 4KB at a time doing 8 FFT "levels" (4KB = 512 doubles = 256 complex values. 256 = 2^8). This 4KB value was chosen to fit completely in the L1 cache of the Pentium (assuming about 4KB of sin/cos data will also be needed). The remaining FFT "levels" (a 512K FFT requires 19 levels) cannot be done in one pass and fit in the L1 cache. So in pass1 prime95 grabs 128KB of data at a time from main memory and does 3 levels of the FFT, then reads 4KB of data at a time from the 128K L2 into the L1 cache and does 8 levels of the FFT. Thus, we see that L2 cache size is irrelevant in pass 2, and somewhat beneficial in pass 1. Note that the Athlon / Duron operate almost completely out of the L1 cache!! The P4 SSE2 code is different. Since the L1 cache is wretchedly puny, pass 2 instead operates on 128KB of data at a time so that data accesses come from the L2 cache. More FFT levels are done in pass 2 and fewer in pass 1. The astute reader will note that the Athlon/Duron code could be made a few percent faster by doing more FFT levels in pass 2 - taking advantage of the CPUs larger L1 cache. Now fewer FFT levels will be done in pass 1, resulting in fewer L2 cache accesses and fewer TLB cache misses (a weak point of the AMD chips). >(2) The "old" benchmarks (v20) consistently showed "old" Athlon & >Katmai PIII (which had 512KB of L2 cache running below core >speed) outperforming Thunderbird & Coppermine PIII (256KB L2 >cache at full core speed) respectively. Typically by around 4%. I >just assumed that the extra L2 cache was doing more good than >harm, despite running at half speed - or even less on faster Athlons! Now take all my above statements with a grain of salt! It is impossible to predict a program's L2 cache accessing patterns. The OS does not map consecutive pages in virtual memory to consecutive pages in physical memory. Throw in the difficulty in managing any global variables or allocated memory that are accessed as well as interrupt code tossing out cache lines every now and then, you soon get an impossible mess to keep track of. So, twice as much half-speed cache may very well run faster than half as much full speed cache. I remember it the other way around though (the faster caches had better times). Although its only one data point, the full speed PiII-500 is much faster on the benchmarks page than the half-speed PIII-450. But, as you point out, chipsets, etc can make a huge difference. >(3) Conversely I found about three years ago (probably running v16) >that a particular Celeron 266 system (_no_ L2 cache) ran Prime95 >a bit faster than a similar system with a PII-266 (same internals, >but 512KB half-speed L2 cache). Probably this was a >chipset/memory artifact but it does seem to point at L2 cache >size/speed not being _crucially_ important. The current benchmarks page does not show this (compare Cele300 to the Cele266) >Now I'm not doubting that the more & the faster, the better, I'm just >saying that the effect seems to be significant rather than >overwhelming. I agree. >Certainly I don't think we ought/need to be messing around with >tuned versions; there's enough complication in the code & the >efficiency improvements would seem to be small. Agreed again - one of the reasons a Athlon-specific version was never created. High cost - small gain. >_If_ SMT appears to the OS to be SMP , then surely the user will have > to run two >processes. Or just one process with two threads. >There is no design problem; at present a user with a >dual-processor system can elect to run LL testing on one >processor & trial factoring on the other - or LL testing on both, if he >wishes. Correct - which is why a SMT specific version of prime95 is unlikely. >The problem, of course, is that probably 90% of users will be using >an operating system that doesn't support SMP. Windows XP Home >Edition supports only single-processor systems, just like Win 9x/ME. Good point - that may be why Intel is planning on putting SMT in the P4 server chips only. Sorry for the long post, George _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #901 ******************************