Mersenne Digest Sunday, 7 March 1999 Volume 01 : Number 523 ---------------------------------------------------------------------- From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 11:44:55 -0000 Subject: A few more iterations? (was Re: Mersenne: Moo?) [EMAIL PROTECTED] writes: >I pointed at the Great Number and said: Because S(3021377) has this >many bits. Knock off a dozen digits, and it would take that many years >just to send the data from one computer to another. > >I felt pretty smart. Then he asked: if S(n) has so many bits, how does a >desktop computer handle it? M(3021377) has 3021377 bits (all ones) i.e. somewhat less than 400 kilobytes, so fitting M(3201377) into memory is not a problem for modern PCs. However, we start off with a 3-bit number (4) and perform 3021375 squaring operations on it. Now squaring a number either doubles its length, or results in a number double the length less 1 (irrespective of base). The "subtract 2" operation has little effect on the base-N representation of a large number. Therefore we can say that the residual obtained by LL testing M(3021377) without remaindering would have at least 2 to the 6 million bits. There's no way you get anywhere close to storing this in the entire Universe... You can start off with e.g. 14 instead of 4 and do one less iteration, or 194 and save 2 iterations, irrespective of the exponent (> 4) ... but, really, the potential saving in time is very, very small as a proportion of the total work. >makes what you'd like to do utterly impossible. It would ONLY be possible if >we stored the FULL S(whatever) every cycle, and never took it modulo 2^P - 1. >However, we'd need machines with (insert fantastically large number, perhaps >more than the universe can handle) exabytes of RAM to store the full S for an >exponent around 3 million. And so forth. Aw. :-( Precisely. However, there *is* some mileage in the idea - and a useful double-checking trick? Suppose we take a number of exponents that all need checking (or double-checking) - - say 3, which I'll call p, q and r. (The number doesn't matter to the theory). Now use the standard LL test algorithm to calculate the residues for each exponent, working modulo M(p)*M(q)*M(r), taking note of the values of the residues (the WHOLE value, not just the low n bits) S(p) at iteration p-2, S(q) at iteration q-2 and S(r) at iteration r-2. In other words, do the "few extra iterations" suggested! If we know S(p) mod (k*M(p)) for any integer k, then obtaining S(p) mod M(p) is essentially trivial - one operation, and M(p) being just a string of 1 bits, it's very easy to do with a few (extended precision) shift & add operations. The problem is that, superficially, this procedure doesn't seem to actually save any time - but it shouldn't take significantly longer than running the three independent tests. Practical implementation using DWT / FFT / NTT would obviously require a different transform size than would be used (optimally) to do the three tests independently. Also the data worked on would be different enough to ward off risks of data-dependent processor bugs. In practice, there may be some small time saving possible. It turns out that the fast multiplication algorithms are most efficiently implemented when the transform size is a power of 2. So, e.g., numbers around 3 million are relatively expensive to check (using Prime95) because they're too large for a 128K transform size but too small to need a 256K transform size. However, checking 3 at once would fit a 512K transform size reasonably well. There is, of course, a converse trend, in so far as larger transform sizes tend to cause more cache misses, therefore cache tuning for large transform size may become a significant issue. My suggested "trick" applies especially to other programs e.g. MacLucasUNIX which have no intermediate transform sizes between powers-of-two. A couple of days ago my Alpha system finished double-checking M(2361701) using a 128K transform; the next exponent I had lined up for it was M(2361721), and it's decided that a 256K transform is needed, thus doubling the run time 8-( (Don't forget this is DIFFERENT CODE to Prime95 - in fact, the Alpha FPU works to only 53 bits precision (IEEE G-floating), rather than the 64 bits precision which the Intel x86 FPU is capable of) Can anyone fault my logic? If not, then my suggested approach may possibly be more effective than writing extra code into MacLucasUNIX (and other LL testers) to cope with transform sizes intermediate between powers of 2. Also saves debugging a whole load of extra FFT code 8-) Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: "Floris Looyesteyn" <[EMAIL PROTECTED]> Date: Sun, 7 Mar 1999 12:51:07 +0100 Subject: Re: Mersenne: better way to strip trailing whitespace from a file >perl -pe 's/\s+\Z//' <prime3.txt Hey COOL, here's an alien! Now we can finally ask how they call mersenne primes! Let's see how do we make it clear... 2 3 5 7 13 17 19 .... ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 16:33:08 +0100 (MET) Subject: Re: A few more iterations? (was Re: Mersenne: Moo?) [EMAIL PROTECTED] suggests > Suppose we take a number of exponents that all need checking (or double-checking) > - say 3, which I'll call p, q and r. (The number doesn't matter to the theory). > Now use the standard LL test algorithm to calculate the residues for each > exponent, working modulo M(p)*M(q)*M(r), taking note of the values of the residues > (the WHOLE value, not just the low n bits) S(p) at iteration p-2, S(q) at > iteration q-2 and S(r) at iteration r-2. In other words, do the "few extra > iterations" suggested! > > If we know S(p) mod (k*M(p)) for any integer k, then obtaining S(p) mod M(p) is > essentially trivial - one operation, and M(p) being just a string of 1 bits, it's > very easy to do with a few (extended precision) shift & add operations. > > The problem is that, superficially, this procedure doesn't seem to actually save > any time - but it shouldn't take significantly longer than running the three > independent tests. Practical implementation using DWT / FFT / NTT would obviously > require a different transform size than would be used (optimally) to do the three > tests independently. Also the data worked on would be different enough to ward off > risks of data-dependent processor bugs. > > In practice, there may be some small time saving possible. It turns out that the > fast multiplication algorithms are most efficiently implemented when the transform > size is a power of 2. So, e.g., numbers around 3 million are relatively expensive > to check (using Prime95) because they're too large for a 128K transform size but > too small to need a 256K transform size. However, checking 3 at once would fit a > 512K transform size reasonably well. There is, of course, a converse trend, in so > far as larger transform sizes tend to cause more cache misses, therefore cache > tuning for large transform size may become a significant issue. > > My suggested "trick" applies especially to other programs e.g. MacLucasUNIX which > have no intermediate transform sizes between powers-of-two. A couple of days ago > my Alpha system finished double-checking M(2361701) using a 128K transform; the > next exponent I had lined up for it was M(2361721), and it's decided that a 256K > transform is needed, thus doubling the run time 8-( (Don't forget this is > DIFFERENT CODE to Prime95 - in fact, the Alpha FPU works to only 53 bits precision > (IEEE G-floating), rather than the 64 bits precision which the Intel x86 FPU is > capable of) > > Can anyone fault my logic? If not, then my suggested approach may possibly be more > effective than writing extra code into MacLucasUNIX (and other LL testers) to cope > with transform sizes intermediate between powers of 2. Also saves debugging a > whole load of extra FFT code 8-) > > Regards > Brian Beesley Try to keep your lines below 75 characters so they still fit on an 80-character screen after we copy and indent them. It is valid to compute a residue modulo M(p) * M(q) * M(r) and later reduce it modulo M(p), M(q), M(r). But how will the DWT (Discrete Weighted Transform) modulo this product be done? Presently, if we want a product modulo 2^p - 1 using a convolution of length n, we scale the input using powers of 2^(1/n), and the precise powers depend upon p. The individual digits of the multiple-precision residue do not all have the same base -- the pattern depends upon p. How to you resolve these? Peter ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 16:12:07 -0000 Subject: Re: Mersenne: Category 1,2 or 3 ? Gordon Spence writes: >>>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. This is a slight exaggeration. If you're running LL tests or double-checks at all, you've more chance than if you're not. Also, the "Big Bands" seem to be largely concentrating on first tests of largish exponents using lots of powerful systems, leaving double-checking to "ordinary humble joes". Taking the most recent figures / estimates available, there are approximately 20,000 Mersenne numbers less than "Spence's Number" M(2976221) which have been tested only once. If the error rate of 1 in 200 is accepted, approximately 100 of these residuals will be incorrect. The average of the exponents is approx. 2.4 million (by visual inspection of the table), and George's "a priori" estimate that an untested exponent around 2.4 million is 1 in 10,000. Therefore there is about 1 chance in 100 that another Mersenne prime less than Spence's Number remains to be found. (All above worked to very few significant figures, since so much is (hopefully) educated guess anyway) A couple of associated questions: 1. Does anyone know where the estimate of an exponent yielding a Mersenne prime that Prime95 outputs in its status pop-up comes from? (George, I can see & understand the source code, what I would like to know is the source of the algorithm) 2. Does our continued effort in eliminating possible Mersenne primes change that estimate in any way? Since I joined the project 10 months ago, we have found no new Mersenne primes (any day now?) but eliminated a great many exponents, nevertheless the formula doesn't seem to have changed, which it probably should have done if it's (even partly) based on empirical data. Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Spike Jones <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 09:54:39 -0800 Subject: Mersenne: biiiiig perfect number > [EMAIL PROTECTED] wrote: > If the printout has 80 characters per line and 60 lines per page, > you'll need 190 pages for 910000 decimal digits. You must have > big pages. Do you use four walls, floor, and ceiling? If one used readable fonts, then yes, one would need a couple hundred pages to print out the great one. If one uses two point font, then one gets several hundred characters per line and three hundred lines per page. Now of course, the pages look like grey goo. I have been asked why I have six pages of greyness on my wall. {8^D Those with *very* good eyes can resolve characters and even read them off of a two point printout from a good laser printer. I once had a great idea: I would express the Great Number in hex! Then I realized that I would get with 4 pages of tiny Fs. {8-[ Not so interesting. But if some clever GIMPSer were to generate the perfect number that is (M37*(M37+1))/2 then express *that* number in hex, I would clear off a space on my office wall for it. {8-] Anyone accept the challenge? Thanks for the explanation of the LL Peter! spike ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Dennis E Okon <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 13:24:28 -0500 Subject: Re: Mersenne: biiiiig perfect number >I once had a great idea: I would express the Great Number in hex! >Then I realized that I would get with 4 pages of tiny Fs. {8-[ >Not so interesting. But if some clever GIMPSer were to generate the >perfect number that is (M37*(M37+1))/2 then express *that* number >in hex, I would clear off a space on my office wall for it. {8-] Anyone >accept the challenge? This would just be a bunch of Fs followed by a bunch of 0s (with maybe a different character in the middle and at the very beginning). In binary: M37 = 1111111....111 M37 + 1 = 10000...00 M37*(M37+1) = 11111...110000...00 (M37*(M37+1))/2 = 11111...110000...0 <- one less zero This still is almost twice as long and just about as interesting as M37 itself. - -Dennis ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: George Woltman <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 12:57:36 -0500 Subject: Re: Mersenne: Errors in previous results Hi, At 03:22 PM 3/6/99 +0000, Gordon Spence wrote: >I have recently retested M2018167 and found a factor that was previously >missed. So what?, that surely is the whole point of double checking. This >number will now be tested a third time to dtermine which of these two >results is correct. Actually factors do not require a third check since a factor is very easy to verify. The previous run did not necessarily miss this factor as the later versions of prime95 are a little more efficient at factoring and thus trial factor a little deeper. The first LL result will be discarded and not considered either correct or incorrect when determining our error rate. >As long as we do the rigorous double and triple checking then why should we >be worried? There is no need to worry. However, knowing your error rate is important as are discussions on ways to reduce this error rate. Best regards, George ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 11:11:55 -0800 (PST) Subject: Re: Mersenne: Errors in previous results We should be worried because the statistical chance of error is never 0%. No matter what the odds are, EVENTUALLY it will tip out of our favor. - -Chuck On Sat, 6 Mar 1999, Gordon Spence wrote: > There has been speculation on the list recently about the chances of > finding previous errors and the implications for various things. > > I have recently retested M2018167 and found a factor that was previously > missed. So what?, that surely is the whole point of double checking. This > number will now be tested a third time to dtermine which of these two > results is correct. > > As long as we do the rigorous double and triple checking then why should we > be worried? > > 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 > -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW: http://www.silverlink.net/poke : Boycott Microsot : : E-Mail: [EMAIL PROTECTED] : http://www.vcnet.com/bms : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 11:27:31 -0800 (PST) Subject: Re: Mersenne: Moo? Yes, it would take an enormous amount of RAM to do this, but what if we stored the data in some kind of compressed format (a ZILLION to 1 compression???), or some kind of reference format? Then we could take advantage of everyone's clock cycles used on other searches. There's got to be a way of virtually referencing somthing that is not able to exist. Look at the way we use a MOD instead of the actual number. Just some ramblings... - -Chuck On Sun, 7 Mar 1999 [EMAIL PROTECTED] wrote: > <<Yesterday a coworker > saw my six page printout of the Great Number on the wall of my office, > asked, and I explained GIMPS and the LL algorithm, how the program > checks to see if M(n) divides S(n). He is a clever chap and asked why > prime95 starts from scratch calculating S(n) instead of getting it from > a previous check: if you calculated S(6000001) and your needed > S(6000031) for your next check, for instance, why would you not take > the previously calced S(6000001) then square and subtract 2 thirty times. > > I pointed at the Great Number and said: Because S(3021377) has this > many bits. Knock off a dozen digits, and it would take that many years > just to send the data from one computer to another. > > I felt pretty smart. Then he asked: if S(n) has so many bits, how does a > desktop computer handle it? > > Me: duuuuuuuh. I dont know. {8-[ > > Do you know? Can someone explain it to me in words an ordinary > person would understand, how the Prime95 LL algorithm works? spike>> > > Wouldn't it be nice... (Beach Boys song). Nah. You see, we use a shortcut. At > every iteration, we only store S(whatever) mod 2^P - 1. It's that mod that > counts. This lets us run Prime95 on machines with 8MB of RAM. However, it > makes what you'd like to do utterly impossible. It would ONLY be possible if > we stored the FULL S(whatever) every cycle, and never took it modulo 2^P - 1. > However, we'd need machines with (insert fantastically large number, perhaps > more than the universe can handle) exabytes of RAM to store the full S for an > exponent around 3 million. And so forth. Aw. :-( > -*---*------- > S.T.L. > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW: http://www.silverlink.net/poke : Boycott Microsot : : E-Mail: [EMAIL PROTECTED] : http://www.vcnet.com/bms : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Sun, 7 Mar 1999 11:43:59 -0800 (PST) Subject: Mersenne: Mersenne Processor If one were to build a microprocessor SPECIFICALLY suited to LL testing, what would the assembly instruction set look like? Approximately what would the architecture look like? Speed shouldn't be an issue because there's never enough anyway and we're trying to work smarter not harder. Thanks, - -Chuck -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW: http://www.silverlink.net/poke : Boycott Microsot : : E-Mail: [EMAIL PROTECTED] : http://www.vcnet.com/bms : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Ken Kriesel <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 15:03:59 -0600 Subject: Re: Mersenne: mersennes for exocivilizations At 07:42 PM 1999/03/06 -0600, "Robert G. Wilson v, PhD ATP" <[EMAIL PROTECTED]> wrote: > > >Ken Kriesel wrote: > >> >> 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.) >> > >2^p -1 is prime for the following ps: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, >127, 521, 607, 1279, 2203, ..., 1257787, 2976221, 3021377, ... . But all of >these are primes. Two is the first prime, denoted as p(1), three is p(2), five >is p(3), etc. So therefore the best data compression is represent the Mersenne >primes is to denote the n, such that 2^p(n) -1 is prime for the following ns: >1, 2, 3, 4, 6, 7, 8, 11, 18, 24, 28, 31, 98, 111, 207, 328, 339, 455, 583, 602, >1196, 1226, 1357, 2254, 2435, 2591, 4624, 8384, 10489, 12331, 19292, 60745, >68301, 97017, 106991, 215208, 218239, ... , . The above is a steadily increasing sequence, which could be used to advantage. One could represent delta n for additional compression. 1,1,1,1,2,1,1,3,7,6,4,3,67,12,... has fewer bits. Then put the message through something standard like Huffman or LZH. The difficulty is that with each step the message becomes more obscure. And the essence of a message is to communicate something. Ken ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Ken Kriesel <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 16:04:35 -0600 Subject: Re: Mersenne: Double-checking (was Chronons) At 11:59 AM 1999/03/05 GMT, "Brian J Beesley" <[EMAIL PROTECTED]> wrote: >> (Ken wrote) >> Right. The odds heavily favor both mismatched residues being nonzero. >> A zero residue at the last iteration is what indicates primality. > >Depends on what you mean. If a Mersenne number that has been >tested once really is prime, but the test "went wrong", then we >have a wrong result i.e. calling the number composite when it isn't. I mean that nearly all mersenne numbers are nonprime even if the exponents are prime, so of the numbers we bother to LLtest, when an error occurs, the odds are 99%+ that it does not conceal an actual Mersenne prime. And in the unusal case of a nonprime Mersenne number being erroneously identified as prime, it would be multiply-checked and so the error caught, rather than being announced as a prime. >This is why double-checking is so important, if we want to find *all* >the Mersenne primes for exponents up to a given limit. I agree that double checking is important in an exhaustive search, and that exhaustive search (rather than haphazard or opportunistic search) is valuable. >There *might* be one or two lurking somewhere in the mass of >exponents which have only been tested once. >> >> >Also what causes the errors, bugs in the code? >> >> What I've seen most often is that prime95 and its relatives provide >> early warning of unreliable hardware, whether cpu, RAM module, or motherboard. > >Usually caused by overheating - failed CPU fan, poor ventilation or >excessively hot environment, overclocking, poor thermal contact >between processor substrate and heatsink ... The sorts of things I've seen include, in systems with good cpu heat sinking, multiple case fans, cpu fans properly installed and no overclocking: mechanically ill-fitting case causing a system to be unreliable unreliable single SIMM out of a set of 4 unreliable CPU chip unreliable motherboard whether these component-level problems were due to electrical stress (power outages, spikes, brownouts, static), thermal stress (overheating or too-frequent power on/off), or latent defects in manufacture is unknown. Ken ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: brandon j whitehead <[EMAIL PROTECTED]> Date: Tue, 2 Mar 1999 09:54:46 -0600 Subject: Mersenne: LL testing? hello. i was wondering if somebody would mind explaining (briefly) LL testing. maybe even include some basic C code to look at...thanks brandon ___________________________________________________________________ You don't need to buy Internet access to use free Internet e-mail. Get completely free e-mail from Juno at http://www.juno.com/getjuno.html or call Juno at (800) 654-JUNO [654-5866] ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Gordon Spence <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 23:10:10 +0000 Subject: Mersenne: Reference to Donald Knuth > >From: Jud McCranie <[EMAIL PROTECTED]> >Date: Wed, 03 Mar 1999 14:05:29 -0500 >Subject: Mersenne: [ Mersenne] Re: Mersennes for Martians [snip] > >You've heard of Knuth, I'm impressed. If you see section 4.3.3 you'd know that >there are algorithms (for mult and div) that are faster than what are currently >used. > I hate to be a name dropper, but Donald phoned my house to make sure he spelt my name correctly for inclusion into his book. He was revising the section on primes. regards Gordon 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 ------------------------------ From: Gordon Spence <[EMAIL PROTECTED]> Date: Sun, 07 Mar 1999 23:13:05 +0000 Subject: Mersenne: PC that found M2976221 >From: Spike Jones <[EMAIL PROTECTED]> >Date: Wed, 03 Mar 1999 20:05:40 -0800 >Subject: Re: Mersenne: Category 1,2 or 3 ? > >Gordon Spence wrote: > >> Nowadays I still have the trusty P100 that found the prime... > >Gordon, that machine will make a great museum piece some day. >Is it for sale? I suspect such a thing would be quite valuable. >spike > At the time we tried to interest Intel into acquiring both mine and Joel's P90, but we never got any response. If anybody out there is *seriously* interested in getting hold of this pc then please contact me off list. regards Gordon 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 ------------------------------ End of Mersenne Digest V1 #523 ******************************
