Re: Mersenne: ROUND OFF error
Hi all, At 08:13 PM 7/20/99 -0700, Daniel Swanson wrote: Iteration: 6128000/7812379, ERROR: ROUND OFF (0.4026489258) 0.40 [Tue Jul 20 16:35:33 1999] Disregard last error. Result is reproducible and thus not a hardware problem. I consulted the readme file, but it wasn't very helpful. What is a "ROUND OFF" error? While it's nice that it's reproducible, will it invalidate the result of this LL test? Does the fact that this exponent (7812379) is so close to the FFT size breakpoint (782) make this type of error more likely? Yes, the fact that you are testing an exponent near the FFT size breakpoint makes this error much more likely. It will not invalidate the result of your LL test. Note that in version 19, I've decided to be a bit more conservative with the FFT breakpoints. Your exponent will be double-checked with a larger FFT size (if the double-checker uses v19). Regards, George P.S. Double-checking has not revealed any problems near the upper ranges of any FFT sizes. The more conservative FFT breakpoints will reduce the chance of an incorrect result due to an excessive convolution error. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mp and E-Cash
On 20 Jul 99, at 0:26, Luke Welsh wrote: That would be me. But I don't like the money because I think it opens a can of worms. ('can of worms' -- what do you say in Russian or Japanese or Flemish?) I happen to like money (you can buy beer with it and cover green fees). Primenet is a lot more powerful than just managing exponents for GIMPS. And e-cash is in the near future. Eventually, PrimeNet should be able to move small (and large) amounts of money around the world with ease. Unfortunately, e-cash opens several other cans of worms! BTW I agree with your general sentiments, but you seem to be glossing over some of the details. e.g. what happens if the winner comes from an "unfriendly" country? Can we transfer e-cash to a citizen of, e.g., Iraq, and could that citizen convert it into goods even if (s)he receives it? We really do need a formula for [e]. Set aside $25,000 and each x% improvement in GIMPS throughput wins x% of the $25,000? (what do we do if there are multiple improvements?) What's wrong with having a panel (possibly consisting of previous Mersenne prime discoverers) to evaluate any contenders for this judge how much, if any, of the fund should be awarded for each improvement? Some will definitely be more valuable than others... and, if there's money left because not all was awarded, then it can be held over, given to charity, distributed pro-rata for CPU cycles contributed, or whatever. Award $10,ooo for each new Mp, regardless of size. Suppose M(777) is prime. The finder is credited $10,ooo (to be awarded when GIMPS finds a decamega prime). The decamega finder also gets $10,ooo. [Nah, 777 is not prime (it's divisible by 7), therefore 2^777-1 definitely isn't prime either.] This would seem to be a bit unfair. I think the decamega finder should definitely get a large share (25% minimum). The point here is that, if I can freely download a program use it to check Mersenne numbers in the 10 million digit range, why should I bother to contribute to a cooperative project if, by doing so, I'm going to have to give up almost all the prize if I get lucky? The fact that even poor people are prepared to throw a few dollars at the remote chance of a lottery jackpot would tend to indicate that a few dollars recompense for CPU cycles contributed to a cooperative project will not attract contributors in the way that a large cash prize will. I'd prefer to keep a slice (smaller than the discoverer's slice) for discoverers of non-qualifying Mersenne primes, but don't pay anything out until the range up to 10 million digits is (more or less) completely searched. Then divide it equally between them. Carry the sum forward if it happens that we discover that we already know all the Mersenne primes with less than 10 million digits. Is $10,ooo about right? I've lived in different countries, and I lived around the USA. In Silicon Valley, $10K will barely pay 6 months rent, but in Leblon I could live quite nicely (qual e', malandro? :-) For the near future, $10,ooo should cover the cost of a *nice* PC, with money to spare. I reckon $10K would buy a small collection of *nice* PCs, however... Also, those people paying $20K pa rent in Silicon Valley presumably do so because they're getting paid proportionately bigger salaries than most of us. Conversely, in some parts of the world, $10K is several times a good salary ... if we try to link the amount of the prize to income, then how much would we have to pay Bill Gates if he won it? (And he probably could, quite easily, if he turned half his wealth into PCs running Prime95) Another thought. we cannot allow people to started hoarding their residues in hopes of being paid tomorrow for today's computations. Perhaps this should be made retro-active --- pick a date -- retro- active to the date/time when Nayan's machine reported M38? I reckon, by the time that the division of the hypothetical $100K into chunks is done, it's very unlikely that anyone is going to deprive themselves of much more than a few cents income by hoarding residues, so I can't see this as a serious problem. Nevertheless I think the suggestion makes sense. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
On 19 Jul 99, at 22:21, David M Einstein wrote: You will want to do P-1 in addition to, and after seiving. It would be foolish to use p-1 to discover a 30 bit factor. Not half - trial factoring with numbers that small, and _very_ heavily constrained, is _extremely_ fast. I tested 159,975 exponents (the prime numbers between 33219278 and 3600) for factors up to 2^32 in less than 20 seconds on a PII-350. If you are doing stage 1 only I believe that I had looked at a b1 of at least 100K which would translate to about 140K (I'm trusting your numbers) squarings. I think that that is still less than 5% of the number of squarings for a current LL test, and would reap factors for about 5% of the numbers so would at least break even. Interesting ... There is obviously a breakeven point between trial factoring (which will _definitely_ find any factors up to the limit specified) and P-1 (which might not). So, are we in any sort of position to estimate where that breakeven point might be, for exponents say around 10 million? What about smaller exponents, say around 5 million, which have (mostly) already been LL tested but haven't been double checked yet? (Finding a factor saves running the double check) The fact that we would still be running trial factoring up to some limit (though maybe a little lower than we are at present) would to some extent remove the objection that an exhaustive search of at least part of the range of possible factors is useful. There is going to be another breakeven point between P-1 factoring and LL testing - if we run a LL test, then (barring accidents) we get a definitive result in a predictable time, whereas we could run P-1 "for ever" on even quite a small exponent without arriving at a definite result. Not exactly. With a reasonable B1 I doubt that it would be the most time consuming part, but a straight euclidean or lehmer algorithm would be quite slow. A divide and conquer algorithm would be much faster, but extremely memory hungry (Violating GIMPS's unstated (but very positive) invisibility constraint (No noticable effect on the host systems operation). Can we speculate on approximately how much memory would be needed, as a design exercise? In any case, it needn't rule the scheme out altogether if we find that some systems aren't able to contribute usefully by reason of limited memory. After all, not all systems can contribute usefully to some other tasks, e.g. it's a bit pointless to try to run a LL test on a 7 million range exponent on a 486, though the program _will_ try, if you ask it to! I believe that one of the reasons that the next version of prime95 will contain a straight FFT multiply is to support a divide and conquer GCD, but that is supposition on my part. I thought maybe it was something to do with making more efficient use of the L2 cache by keeping FFT data size reasonable using a recursive method to break large numbers down into small operations that would "fit". Implementing this would require a general m * n bit multiprecision multiplication function. I think that a P-1 would probably be neccessary. There may be enough room for ECM to have overcome P-1's free factor of P, but I dont think so. ECM actually has a moderate memory load even for small exponents, you need to keep _lots_ of n bit work vectors lying about. Though you don't need to access all of them all that often, so it doesn't hurt _too_ badly if some of them are forced out to a paging file. c.f. LL test becomes _impossibly_ slow if you run out of physical memory the system starts paging on you. I wonder if we already have the data we need to make some of the estimates I've indicated above, or whether someone will have to go try to make them - , if so, whether we actually need to code anything, or whether it would be possible to use George's existing P-1 factoring program to make them. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: The $100,000 award for 10,000,000 digit prime
On 19 Jul 99, at 18:40, Todd Sauke wrote: Alex, The group you seek always has 2^n elements. All bit combinations are possible. (P = 2^p-1 is "minus one" in n-bit words. 2*P is minus two, etc. up to 2^n*P which is 0. All bit patterns occur.) Todd Sauke In general, what you say is true - but try computing the LL sequence to one hexit precision (i.e. working to base 16). Starting from 4, we get 0x0E, then 2 ; since 2*2-2 = 2, _all_ the subsequent values are 2, so we can compute the low order 4 bits of the umpteen zillionth term of the LL sequence as fast as we can load the value 2 into a register! Oops - doesn't work - forgot to take the modulus - otherwise there could be _no_ Mersenne primes except 7 = 2^3-1 ;-) It's taking the modulus which is the key to the whole LL test, and what the problem essentially boils down to is _any_ way of computing the remainder of a division whilst working to a lower precision than the number of bits in the divisor. Now I wouldn't say that this is completely impossible, but the very idea seems about as counter-intuitive as the notion of having several networked processors cooperating on an FFT without being able to share data at memory bus speed and without being significantly delayed by waiting for each other's intermediate results to become available. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Search Status report
I noticed something slightly different on the search status page at http://www.mersenne.org/status.htm today (but it's probably been this way for a while). The "Expected new primes" column got some new nonzero numbers in rows where there are no exponents of unknown status. I presume this is taking into account the frequency of bad results that have turned up through double checking? Greg Hewgill _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
FAQ author Lucas Wiman [EMAIL PROTECTED] writes Well, this might not be a problem. If P-1 tries more than one base, all that is required (per Mn) is *one* gcd. We just multiply the remainders from the bases mod Mn, and then take the gcd on the final remainders. We could have the program prompt the user for the time when the computer is on but not being used when they ask for a P-1 assignment. Or, we could have it run so that the program stops functioning when the computer is being used. It could just save the intermediate files to disk, to free up memory for the user who (graciously) gives us their CPU cycles. You might rerun P-1 with larger limits, but don't bother rerunning using a new base. If q is a prime factor of Mp, and r is the largest prime factor of q-1, then a fraction 1 - 1/r of all possible bases will require us to include exponent r in step 1 or step 2 of P-1. If r 10, this is 99.999% of all potential bases. The base change can be useful if P-1 finds a composite GCD. For example 2717 = 11*13*19. If we start with base b = 7, using exponents 4 and 3, then b^4 = 2401 == -316 (mod 2717) (b^4)^3 == -31554496 == 742 (mod 2717) Here GCD(b^12 - 1, 2717) = 247 is composite (13*19). This is because 13-1 divides the exponent 4*3 and because our choice b = 7 is a cube (also a square) mod 19, with (19-1)/3 dividing 4*3. Choosing a b which is not a cube modulo 19 lets P-1 factor 247. Peter Montgomery _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: The sound of number searching
Hello Mersenne, Sorry for bad english its not my native language, thanks. I run mprime (or prime95 ntprime) on my laptop. When I start the programm on my notebook it makes a strange mechanical pulsing sound like an old damaged wheel or like an ill cricket. The sound doesn't come out of the speakers and is not the fan from the cpu. First I thought it is the fan probably it is getting hotter and then the spin is not perfect due the heat. But when I run other cpu stressing programms (rc5des) there's no sound. Then I thougth it is the harddisk but when the harddisk goes to sleep mode the noise is still there. Then I thought the speakers could be responsible. I removed the soundcarddrivers moved the volume control knob to 0: still hear the sound. When I press some areas on my notebook the sound disappers for a few seconds but then it comes back. The funniest thing is when I start other cpu stressing programms while (m)prime is running the sound is changing. Each programm plus (mp)prime changes the sound in a special way so I can recognize exactly on the noise which programms are currently runnig. Why the hell is my notebook making such strange noise when running this programm ? Any ideas ? I'm goning to get crazy listening that noise all the time. Best regards, Burlington mailto:[EMAIL PROTECTED] _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers