Mersenne Digest Thursday, August 5 1999 Volume 01 : Number 610 ---------------------------------------------------------------------- Date: Thu, 05 Aug 1999 13:50:37 +1200 (NZST) From: Bill Rea <[EMAIL PROTECTED]> Subject: Mersenne: Testing times I've not been long involved in GIMPS and noticed the following:- >So for an exponent like 8027219, you'd save the partial residue at the 10%, >or 802722th iteration (rounding up or down as normal). Of course, the >number of iterations varies just slightly from the exponent, but >whatever...you get the idea. >From this I understand that it takes around about the same number of interations as the size of the exponent to establish primality. I've got several UltraSPARCs I've pressed into service and currently have 7 exponents checked out being tested with MacLucasUNIX. When I filled out the manual checkout form I assumed, for lack of better information, that an UltraSPARC would perform like a Pentium. This doesn't appear to be at all close to the truth. My first assignment was for 7902277. The account details indicated this would take 600 hours of CPU on a 270MHz Pentium. It's doing fractionally more than one iteration every second. That's judging by the times between checkpoint files at 5000 iterations between checkpoints. So far it's used 716.7 hours of CPU. At this rate it's probably done a bit over 2,500,000 iterations or is about one-third of the way there. Is this about right for this type of system? Details:- Ultra-5 270Mhz CPU, 128Mb RAM Solaris 7 gcc version 2.8.1 Also, I've tested MacLucasUNIX with the Sun CC compiler using the - -fast option and it's about a third faster than when compiled with gcc, but there are warnings like:- The -fast option is unsuitable for programs that require strict conformance to the IEEE 754 Standard. Should I be using this option? Thanks for any help. Bill Rea, Information Technology Services, University of Canterbury \_ E-Mail b dot rea at its dot canterbury dot ac dot nz </ New Phone 64-3-364-2331, Fax 64-3-364-2332 /) Zealand Unix Systems Administrator (/' _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 4 Aug 1999 23:28:50 -0400 (EDT) From: Chip Lynch <[EMAIL PROTECTED]> Subject: Mersenne: Free Big computer time. So, I've run across a really nice computer that noone needs for a few months... Solaris 2.6; 4 Processors, 4GB Ram, 500GB of drive space... that sort of thing. Is there any useful project out there that can really make use of this sort of power? I mean, sure, I can run some factoring programs on the CPUs, but that doesn't really do justice to the RAM and the available Hard Drive space. And the system isn't available long term enough for me to commit to four separate large factoring projects (four exponents... whatever) really. Most of the stuff around doesn't parallelize very well either (well, not at the single computer level). Any ideas? Thanks, - ---Chip \\ ^ // (o o) ---oOO--(_)--OOo------------------------------------ | Chip Lynch | Computer Guru | | [EMAIL PROTECTED] | | | (703) 465-4176 (w) | (202) 362-7978 (h) | ---------------------------------------------------- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 4 Aug 1999 21:51:02 -0600 From: "Aaron Blosser" <[EMAIL PROTECTED]> Subject: Mersenne: Multiple residues - enhancing double-checking > This scheme makes almost no sense for normal double checking. > This is becuase > it would save *no* time at all. Think about it, even if you > identify that an > error ocurred in the second week of a 3-month test, you still > have to run it > to completion, and a third test must also be run. (So 3 LL tests > must still > be run if an error ocurrs). It won't make "normal" double checks run any faster, true. What it will do is save a good amount of time for those instances when the double check doesn't match the first time check. Example, a first time LL test is run, spitting out (partial) residues every 10% along the way. A double check is running and at 30% along, it notices that it's partial residue does NOT match the one from the first check. We now know *MUCH* sooner that something is awry, than if we only checked at the end. How does this save us time? Well, it depends. Once the mismatch is noticed, the exponent is assigned to someone else for a double-check, while the double-check currently in progress is put on hold. Once the "triple-check" gets to the same 30% mark, it can compare it's partial residue to that of the 1st and 2nd checks. a) The 3rd check matches the first check. The one running the double-check on hold is cancelled and the one doing the 3rd check will finish up. - -or b) The 3rd check matches the second check. Both the double and triple checks run to completion and the final residues compared. Hopefully, if the 2nd and 3rd checks run to completion, they'll agree with each other at the end as well. I suppose it is even possible that if a 2nd and 3rd check run simultaneously, there's the chance that one or the other will have an error some time *after* that point where they did happen to agree. Oh well...time for a 4th check, but those should be pretty rare. If I recall, there are rare occassions even now when 4 checks have been necessary? Maybe not? I know that some exponents have taken 3 tests to resolve. We ONLY really save any time when: 1) The first check is correct, and 2) The second check is incorrect, and 3) The second check noticed a discrepancy somewhere before the last iteration This doesn't happen often, but as has been pointed out, the number of errors are likely to increase as exponents get larger. And runtimes per exponent also get much longer. The time saved could be months of CPU time. At worst, it's at least no *slower* than the way we do it now, and at best, it saves a lot of time when triple checks become necessary. I think it's worth it, but that's my opinion. Some more formal estimates of how long exponents take to calculate, the probable error rate, etc. should be done to really say how much time could be saved, but I think in the final analysis, the work involved to set this up would be well worth it, especially when we move into exponents larger than 20M, or for primes going into the deca-megadigit range (2^33M-1 and beyond). _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 4 Aug 1999 21:50:42 -0600 From: "Aaron Blosser" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Testing times > I've got several UltraSPARCs I've pressed into service and currently > have 7 exponents checked out being tested with MacLucasUNIX. > It's doing fractionally more than one iteration every second. That's > judging by the times between checkpoint files at 5000 iterations > between checkpoints. So far it's used 716.7 hours of CPU. At this rate > it's probably done a bit over 2,500,000 iterations or is about > one-third of > the way there. > > Is this about right for this type of system? > > Details:- > > Ultra-5 270Mhz CPU, 128Mb RAM > Solaris 7 > gcc version 2.8.1 It's been noted that GCC isn't the best at compiling under Solaris, for this type of code anyway. Someone else (my brother?) will probably have more info on this. Unfortunately, the Sun I was supposed to get showed up while I was on vacation, and some other group managed to "steal" it away before I could put up a fight for it. :-( I think they're getting my RS/6000's also! Double :-( At least I got lots of P-166's... Aaron _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 00:56:10 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing times > From this I understand that it takes around about the same number of > interations as the size of the exponent to establish primality. Correct. See the FAQ at the end of this message for more info. > I've got several UltraSPARCs I've pressed into service and currently > have 7 exponents checked out being tested with MacLucasUNIX. When I > filled out the manual checkout form I assumed, for lack of better > information, that an UltraSPARC would perform like a Pentium. This > doesn't appear to be at all close to the truth. My first assignment > was for 7902277. The account details indicated this would take 600 > hours of CPU on a 270MHz Pentium. It should perform aproximatly like a Pentium, if you check MacLucasUNIX compiled on a pentium and a sparc. However, on intel chips, we have a nice edge: George Woltman's highly optimized assembler version. I doubt any C code could even aproach it. - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 05 Aug 1999 01:57:25 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: RE: Mersenne: Multiple residues - enhancing double-checking At 03:01 PM 1999/08/04 -0600, "Aaron Blosser" <[EMAIL PROTECTED]> wrote: >I think we could keep it simple by just saving every x% iteration's residue >(in truncated form). Using a WAG of saving it every 10% along the way, >you'd only have 9 partial and 1 full residue when all is said and done. > >So for an exponent like 8027219, you'd save the partial residue at the 10%, >or 802722th iteration (rounding up or down as normal). Of course, the >number of iterations varies just slightly from the exponent, but >whatever...you get the idea. > >These partial residues could be sent (for the first LL test) during the >check-ins, or saved up and all sent at once when the test is done. The 2^n least significant bits of the residue make a good check value, since once the modulo operation begins to have an effect, the lsb's quickly change. It is essential to have agreement among different programs, on exactly which iterations' residue LSB's are to be saved. This encompasses both the save interval in iterations, and agreeing on whether the starting value of 4 is iteration 0, 1, 2, etc., as well as agreeing on the starting value, which can be other values besides 4 according to the math. It is more efficient but not necessary to have agreement on how many bits to save. Even n=4, 2 bytes, gives a fairly good error detection rate, but n=6, 8 bytes is much better! I suggest that the number of iterations between residue saves be made a function of the FFT length, since those scale with the runtime for a given cpu. As we move to exponents that require months even on fast machines, we will see an increase in the rate of erroneous results per exponent on the same hardware and same small error rate per execution hour. We will eventually reach exponents with runtimes long enough that the system hardware reliability drops significantly before an exponent completes, due to hardware aging! My feeling is that a P-90-month is about the right interval at which to kick out intermediate residues of 64-bits or so. In a case where two runs are taken to completion, for a large exponent, such that dozens of interim residues are recorded for the first LLtest and for the second, the third tie-breaker need only be run to the point where the first two diverge and the third agrees with one but not the other. On average this will save about half the third-test, which now we need about 1% of the time, but in a few years we may need much more often. By shortening the third-test duration before we can make a comparison, it halves the probability of the third-test being in error and so lessens the amount of time spent on fourth-tests. This saving will also become more significant at higher exponents. Total runtimes are going up drastically. When I joined GIMPS in mid 1996, runtimes per exponent were 12 hours (572k on a P-120). Soon we will have the capability to run exponents requiring more than 12 months on PIII-500's. >> Might the v.17 problem have been trapped with something like >> this? I do not >> recall enough of the discussion to know and the ensuing belly-aching >> overshadowed the real content of finding/fixing/reworking. (I know I am >> never going to rise high on the list, so I do not worry a whole lot about >> how much my report shows.) There is another trick for dealing with the v17 shift bug, which I've suggested to George Woltman. Before the modulo kicks in, the rightmost 2n+2 bits should follow a set pattern that is calculatable for n< log(2)p or so. Math wizards, please be kind re errors in what follows. In hexadecimal, the first several iterations for any value P of current interest follows a predictable pattern. The pattern persists until the result of an iteration grows larger than Mp, and so is independent of P for a time. L(n+1)=Ln^2-2; (using the convention here that we iterate from 2 to n) n hex Ln binary Ln 2 4 3 E 4 C2 1100 0010 5 9302 1001 0011 0000 0010 6 5468 4C02 0101 0100 0110 1000 0100 1100 0000 0010 7 1BD6 96D9 F03D 3002 ... 1101 0011 0000 0000 0010 least significant 64-bits only below: 8 8cc8 8407 a9f4 c002 9 5559 9f9d 37d3 0002 10 f460 d65d df4c 0002 11 e180 d807 7d30 0002 12 9bdb 491d f4c0 0002 13 4ceb b477 d300 0002 etc for all n I found to check, where Mp> Ln, & Ln<=2^(2^(n-1)); Mp>2^(2^(n-1)) 2^p>2^(2^(n-1))+1 p>2^(n-1) log(2)p+1>n log(2)33,219,281=24.985>n log(2)5,000,000=22.25>n (In practice I've found the limits at low n occur at slightly lower p than expected.) That is, the rightmost 2(n+1) bits begin with binary 0011, then in the middle there are 2(n-2) zero bits, then a 1 and another 0. For exponents 16,777,215<p~33,000,000, the max n for this to hold is only around 24, so it is only useful as a check of the first iterations. But that may be sufficient to catch programming errors like occurred in V17's shift count bug. It seems to me that this check would be extremely fast, since the bit lengths are short and given by formula. The test only need be done once per LLtest, before the iteration whose input squared would exceed Mp. The number of bits that should match is respectable for exponents of current interest; over 40 bits. If the shifting of these check values to the shift count of the LLtest was done by a separate algorithm, those bits should still match. It presents an opportunity for defensive programming. It does not help with detecting mildly inadequate FFT lengths, however, since according to George that requires more randomized bit patterns. It's possible if the check pattern is determined with entirely integer instructions, and compared to the result obtained using the FFT in the FPU, that it might smoke out a pattern-sensitive floating multiply or other error in the underlying hardware, akin to the early-Pentium FDIV bug. A part of the QA effort is to run limited numbers of iterations on many exponents, on more than one chip architecture, OS, and program, and compare the 64-bit residues. For example, run the first 400 iterations of an exponent in the millions, on prime95 v19 and something like maclucasunix, and compare the results for a match, for many different exponents. Since the convolution error is larger for the larger exponents in an FFT runlength, these limit exponents will figure prominently. A select set of full LLtests of prime95 v19 (prerelease version) against already-double-checked results will also be made before release; these will be limited by George's tentative release date to smaller exponents than the primenet server is currently issuing for first LLtest. Ken _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 12:57:57 +2 From: "Oscar Fuentes" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Multiple residues - enhancing double-checking From: Lucas Wiman <[EMAIL PROTECTED]> Subject: RE: Mersenne: Multiple residues - enhancing double-checking To: [EMAIL PROTECTED] Date sent: Wed, 4 Aug 1999 19:19:56 -0400 (EDT) > > >Double-Check: > >M23780981,64,863FF87,678676AA,FF637BC,[...],CRC:9923FDA. > > This scheme makes almost no sense for normal double checking. This is becuase > it would save *no* time at all. Think about it, even if you identify that an > error ocurred in the second week of a 3-month test, The errors can occur with the same probability during de double-check. So, when a mismatch is found, the double-check stops this exponent and a triple check is started on another computer (hopefully with another program). The triple check decides who is wrong. If the double check were wrong you saved a partial LLTest. If the first check is wrong, the double check continues just when it stopped, this time as a first time check. In any case, the triple check turns to be a double check. Check it ! :-) After all, maybe the major advantage of all this is the ability to catch bugs early, when some people volunteers to run simultaneous LLTests with different programs. As time passes, the coordinator can compare results quickly. Note that some bugs can be very subtle. Nothing replaces the testing on the field. I would like to know how George notified the v17 bug. > you still have to run it > to completion, and a third test must also be run. (So 3 LL tests must still > be run if an error ocurrs). Correct. > > This schema makes possible simultaneous checking, > > though. But the start-stop mechanism you describe has little > > sense. Sorry, I mean "has little sense given the individualism of certain GIMPS members". A lot of people says "It's _my_ exponent. Dare to work on it before I finish !" Practical or not, I respect this attitude. Saludos Oscar Fuentes _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 05 Aug 1999 15:46:02 +0200 From: Alex Kruppa <[EMAIL PROTECTED]> Subject: Mersenne: New web page with factoring status of M33219281+ Hello all, I have set up a web page with the current factoring status for Mersenne numbers with prime exponents >= 33219281 and <36000000, the ten megadigit mersenne prime candidates. The URL is http://www.informatik.tu-muenchen.de/~kruppa/M33M/index.html The status information currently consists of two files, factors10M.txt and nofactor10M.txt . I�ll try to add some statistical info to the page, but currently I am struggling with finishing the scripts to update the factors and nofactor files. If you want to participate in factoring, please send me an email so I can reserve a range for you. You�ll need suitable software to participate, Prime95 v18 will only let you go up to an exponent of 30000000. On my page there�s Peter-Lawrence Montgomery�s Mfactor as C source code which is fine for RISC architectures. I�ll try to get Intel/Windows-Software, too. If you have any questions/suggestions, please email me. Ciao, Alex. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 11:26:03 -0400 From: Bryan Fullerton <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing times On Wed, Aug 04, 1999 at 09:50:42PM -0600, Aaron Blosser <[EMAIL PROTECTED]> wrote: > > It's been noted that GCC isn't the best at compiling under Solaris, for this > type of code anyway. Someone else (my brother?) will probably have more > info on this. I admin several Sparc machines with Solaris which are currently running SETI@Home which I'd like to switch over to searching for primes. I was originally holding out until there was a PrimeNet client for Sparc, but what the hell - I log into the machines all the time anyways. However, I don't have a Sun compiler - does anyone have precompiled, best-optimized MacLucasUNIX binaries for Sparc processors? I have a Sparc 5, a couple of Sparc 10/20s, and four CPUs on an E450 which sit idle much of the time. Thanks, Bryan - -- Bryan Fullerton http://www.samurai.com/ Core Competency Samurai Consulting "No, we don't do seppuku." Can you feel the Ohmu call? _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 05 Aug 1999 09:05:38 -0700 From: Eric Hahn <[EMAIL PROTECTED]> Subject: RE: Mersenne: Multiple residues - enhancing double-checking Based on previous messages in this thread, I'm going to throw in my 2 cents... (and avoid a lot of quoting!) While the reporting of partial residues at specific points, say every 10% (or 5% over 20M), isn't a bad idea, it won't necessarily save a whole lot of time. The only thing this scheme would accomplish is to allow a third test to begin (if a mismatch is found somewhere along the way) before the second one finishes. If the third test did match the first, there would be savings in discarding the second. What if, however, the third test matched the second? Both tests would have to complete, and some safeguard would have to be a place should the third test complete before the second. This will increase the logistics a lot (but not make it impossible). The client would be required to report most of the information to the server, without receiving much from the server (a stop, go, or discard maybe). A checksum figure as part of the work file, as somebody suggested (shown below), wouldn't work well if the latter case above occurred (2nd and 3rd test match). >Double-Check= >M23780981,64,863FF87,678676AA,FF637BC,[...],CRC:9923FDA. Much more than the logistics, however, would be the confusion facter. This would likely increase exponentially, especially when attempting to determine the current overall status of the project. We might even have to have George committed eventually, when he starts running his fingers up and down across his lips or rubs the side of his head to the bone with his fingers or palm of his hand... :-( I think as the time increases for each LL test, there would be much more time savings in attempting to do higher trial-factoring. Let's look at some figures using the following: 1) We assume to be using a PII 233MHz. 2) an LL test takes a year (around 19.3M) (AND HEY! This is 4 to 5 years away!!) 3) current trial-factoring to 2^64 takes 2 days if no factor is found. 4) currently, only about 13% of exponents are actually factored, with the rest requiring an LL test. 5) 2 LL tests are done for each exponent (an original and a double-check) Current trial-factoring saves 12.5% of the total time that would be spent without any trial-factoring. If we were to trail-factor to say, 2^70 (which should cause factor time to increase to 1 month), without any additional improvement to exponents being factored this will cause a drop to about 8.8% overall time saved. However, for each % improvement in exponents being factored, overall time saved would increase by a little over 1%. As a result, if we were to improve to 20% of the exponents being factored, we would save close to 16% of the overall time spent without any factoring. Of course, even more time would be saved by factoring, if an exponent that would have been factored had it been trial-factored to 2^70, was to be determined to need a triple-check during LL testing because it wasn't factored during a trail-factor process to 2^64 In conclusion, even with a new algorithm that halves the time for an LL test, 1 month to factor an exponent still beats a year to perform an LL test and its corresponding double-check. In addition, it should be easier to speed up the factoring process than the LL testing process. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 10:57:55 -0600 From: "Blosser, Jeremy" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Testing times > -----Original Message----- > From: Aaron Blosser [mailto:[EMAIL PROTECTED]] > Sent: Wednesday, August 04, 1999 10:51 PM > To: Mersenne@Base. Com > Subject: RE: Mersenne: Testing times > > > > I've got several UltraSPARCs I've pressed into service and currently > > have 7 exponents checked out being tested with MacLucasUNIX. > > > It's doing fractionally more than one iteration every second. That's > > judging by the times between checkpoint files at 5000 iterations > > between checkpoints. So far it's used 716.7 hours of CPU. > At this rate > > it's probably done a bit over 2,500,000 iterations or is about > > one-third of > > the way there. > > > > Is this about right for this type of system? > > > > Details:- > > > > Ultra-5 270Mhz CPU, 128Mb RAM > > Solaris 7 > > gcc version 2.8.1 > > It's been noted that GCC isn't the best at compiling under > Solaris, for this > type of code anyway. Someone else (my brother?) will > probably have more > info on this. > Yeh, Sun's CC is WAY better than GCC is for UltraSparc code. I think this is due to the fact that GCC (even 2.95) isn't optimized for V8plus instructions. Anyway, I was compiling with this... OPT=-fast -xO4 -xtarget=ultra -xarch=v8plusa -xsafe=mem -xdepend -xparallel - -dalign (Note: If you are running Solaris 7, you can specify -xarch=v9 which might get you some performance gain) I think that I can speed it up by adding: - -xlibmil And I'm not sure if IEEE754 is needed, this can be turned off by: - -fsimple=1 -fns (I'm not sure what speed increase would be seen here) Umm... I haven't tried the -parallel flag, but I doubt there is much the compiler would find to parallelize in MacLucasUNIX.... Some day, I'll get the time to write the assembly for the Sparc and stuff... but first I need to figure out who in our company holds the Sun Workshop license, cuz I was just playing around with the demo... I'll try and find some place to put a binary for UltraSparcs sometime today and let the list know or whatever. Oh, plus I hacked in some timing code so as to get some benchmarks, nothing super special, but it is nice to know what iteration your box is on, and how fast its performing etc... Plus, some day I might get around to porting it to our AS/400 or something. That'd be interesting... - -Jeremy _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 15:03:21 -0400 From: "Arnold R. Hart" <[EMAIL PROTECTED]> Subject: Mersenne: Closing a 9x Program I have a laptop and can't seem to figure out how to run prime95 when the laptop is plugged in, but not when it is operating on battery power. I'm running MS Win'98. (release 2???) The powermanagement software will let me start prime95 (18.1) when I boot, but if I log-off, then prime95 exits. If I install prime95 as a service, then I can't seem to shut it down via the power save since I didn't start it via the power save software. As I see it, the easiest solution would be to find a way to close it from the command line. My power save software allows me to set "warnings" that will run given programs when the batery gets below a certain level. I'd like to, unless there is a better solution, set a warning at 99% that would run a batch file to close prime95. Is this possible? Thank you already, - --Andrew Hart _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 05 Aug 1999 15:08:33 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: RE: Factoring more Hi, At 09:05 AM 8/5/99 -0700, Eric Hahn wrote: > >I think as the time increases for each LL test, there >would be much more time savings in attempting to do >higher trial-factoring. In version 19, now being QA'ed, prime95 will factor as follows: Numbers above are factored to - ------------- --------------- 71000000 2^72 57020000 2^71 44150000 2^70 35100000 2^69 28130000 2^68 21590000 2^67 17850000 2^66 13380000 2^65 8250000 2^64 Note the new lower limit for 2^64 factoring. Previously, prime95 balanced the "chance of finding a factor" times "cost of factoring" against the "cost of one LL test". Prime95 now balances this against the cost of two LL tests. What's coming in version 20: 1) Optimized factoring above 2^64. The present factoring code is not optimized. This will lower factoring limits even further. 2) P-1 factoring. I already know that P-1 factoring will be beneficial for exponents above 10 million or so. This means there will be a new work type! I need to optimize the P-1 code further and implement a faster GCD. Extra credit: Can someone tell me the probability that P-1 factoring will find an n-bit factor? This is but one piece of the puzzle in determining the best trial factoring limits and P-1 bounds. To compute this probability the k in the 2kp+1 factor must be "smooth", that is all factors must be less than bound #1 except for one factor that must be less than bound #2. I'm sure I have the info around here somewhere, but everyone might be interested in the math behind deriving trial factoring limits and P-1 bounds. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 13:07:08 -0700 From: "Joth Tupper" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Multiple residues - enhancing double-checking, test factoring - ----- Original Message ----- From: Eric Hahn <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, August 05, 1999 9:05 AM Subject: RE: Mersenne: Multiple residues - enhancing double-checking > > The only thing this scheme would accomplish is to > allow a third test to begin (if a mismatch is found > somewhere along the way) before the second one > finishes. If the third test did match the first, > there would be savings in discarding the second. This thought may sound awfully like poaching, but here goes anyway... Some folks want to do first time LL tests. Some folks ask for best suited tasks -- I do. If I have a machine doing double-checks I really do not know or care if it happens to start the double-check the same day as the first time LL test starts. Primenet can track if I am the first LL or the check LL. If the check finishes before the first LL on a prime Mp, George will need to set the rules. Perhaps both parties get co-discoverer status rather than discoverer status. This could make concurrent double-checking a lot more attractive. Concurrent double checking might speed up some of the activities, especially finding the need for triple checks. >Current trial-factoring saves 12.5% of the total time >that would be spent without any trial-factoring. > >If we were to trail-factor to say, 2^70 (which should >cause factor time to increase to 1 month), without any >additional improvement to exponents being factored this >will cause a drop to about 8.8% overall time saved. Another thought: does the factor test already use Goldbach's conjecture? Someone with more cleverness and time than I have right now might think about using this fact: Given p,q integers and r = p+q. Then Mr = Mp.Mq + Mp + Mq This is just: Mp.Mq = (2^p - 1)(2^q - 1) = 2^(p+q) - 2^p - 2^q + 1 = Mr - Mp - Mq So what, right? Suppose we want to factor test Mr. We can (by trial and error) find primes p and q with r = p+q. Usually there are lots. (Hey, if we don't then we just found a counterexample to Goldbach's conjecture. That would be big news, too.) Mr, Mp and Mq are relatively prime in pairs, so none of the factors of Mp or Mq divide Mr. Now, if F is a test factor in the range, suppose we keep a database of Fp = Mp mod F. This is big, but once we have r=p+q, we just calculate Fp.Fq + Fp +Fq mod F. If 0, then F divides Mr. One practical question is how bloody big is this collection of Fp's? Could this make test factoring run faster? Joth _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 5 Aug 1999 15:31:55 -0600 From: "Blosser, Jeremy" <[EMAIL PROTECTED]> Subject: Mersenne: odd thought... I know that OpenGL supports double precision matrix transforms, and with todays super duper 3D accelerator cards, wouldn't it be possible to do an FFT via OpenGL and take advantage of the 3d hardware? Or am I completely off my rocker. (as usual) :) I was just thinking about how you can run a program on just about anything, like, oh, a floppy controller, or whatever. Heck I was playing around upgrading my Cisco 2900XL and noticed it uses a PPC603, (with a whopping 4MB of ram!) :) I guess the question really boils down to whether or not the transforms are handled by the hardware or not... (I dunno, graphics aren't my sort of thing baby). - -J (I suppose I just had to air this out before I even thought any more about it, because as usual, someone else has probably thought of this before and figured out it'd be a waste of time and effort). _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 05 Aug 1999 13:40:34 -0500 From: [EMAIL PROTECTED] (Mikus Grinbergs) Subject: Re: Mersenne: Multiple residues - enhancing double-checking I agree with everything that Lucas said. For the project to benefit, the participants would have to AGREE to restructure the work. Savings would result from stopping the diverging work earlier. (And if "passing around" intermediate files was accepted, by starting any triple-check work later.) In essence, the idea is to take that 1_year_to_complete LL test of an exponent and BREAK IT DOWN into (n) discrete serial work units. mikus Proposed procedural steps: (b) When 'Tester 1' requests work, assign ONLY work unit (1) to him. Howewver, the project RESERVES exponent (EEEE) to 'Tester 1' - only *he* will (in the future) be assigned initial testing of further work units within exponent (EEEE). (c) Eventually, Tester 1 finishes that work unit, and begins to work on some other work unit on some other exponent. HOWEVER, 'Tester 1' saves the intermediate file (of how far he got with exponent EEEE). Somewhere along the line, exponent (EEEE) work unit (1) becomes available to be assigned to a double-checker. (d) Now, when 'Checker 2' requests work, assign exponent (EEEE) work unit (1) to him for double-checking. Since this is work unit (1), there is as yet no intermediate file for exponent (EEEE). If, however, this was a subsequent work unit, and Checker 2 was *not* the person who performed the preceding work unit's test/check, then Checker 2 might OBTAIN the intermediate file from whoever did that preceding work unit. (e) When Checker 2 finishes work unit (1) of exponent (EEEE), his (work unit "final") residue is compared to the residue reported for work unit (1) by Tester 1. HOWEVER, 'Checker 2' saves the intermediate file (of how far he got with exponent EEEE). (f) If the residues match, exponent (EEEE) work unit (2) becomes available to be assigned to 'Tester 1'. Now, 'Tester 1' and 'Checker X' repeat steps (b) - (e), until the residues of the FINAL work unit on exponent (EEEE) agree. ---- If the residues of the most recently tested AND checked work unit of exponent (EEEE) do not match, then that work unit becomes available to be assigned to a triple-checker. (g) Now, when 'Checker 3' requests work, assign the diverging work unit within exponent (EEEE) to him for re-checking. Checker 3 might OBTAIN from Tester 1 the intermediate file for exponent (EEEE) as of two work units back. Checker 3 will perform the first of those two work units (i.e., the one previous to the divergence) to verify that his (work unit "final") residue matches the (known good) one from Tester 1. (h) Checker 3 will then go on to triple-check the diverging work unit. When Checker 3 finishes that work unit of exponent (EEEE), his (work unit "final") residue is compared to the residue reported by Tester 1. (i) If the residues match, the next work unit of exponent (EEEE) becomes available to be assigned to 'Tester 1', and testing and checking continue the same as with a successful step (f). ---- If Checker 3's (work unit "final") residue does not match Tester 1's, but does match Checker 2's, then exponent (EEEE) is un-reserved from 'Tester 1', and is instead RESERVED to 'Checker 2'. Testing and checking of the work units of (EEEE) continue with step (i), where 'Checker 2' replaces 'Tester 1'. ---- (k) If Checker 3's (work unit "final") residue on the diverging work unit of exponent (EEEE) matches neither Tester 1's nor Checker 2's, maybe the best thing to do is to start all over with a new set of participants. Comment: If the breaking down of a long LL computation into discrete units of work is adopted, thought might be given to having prime95 generate a "universal interchange" intermediate file at the end of a unit of work - in other words, special output that would be acceptable as input across a number of operating systems and/or hardware chip types. Note: For the sake of "fairness", becoming the 'reserved owner' on a 10-unit exponent might require 10 'credits' earned through doing checking. In article <[EMAIL PROTECTED]>, Lucas Wiman <[EMAIL PROTECTED]> wrote: > > This idea is rather obvious, and no, I don't remember seeing it either. > > This had been discussed earlier. Brian and I talked about it for a little > while, he came up with the original idea. > > > I think the idea has definite merit. If an error does occur, it's equally > > likely to happen at any step along the way, statistically. Errors are every > > bit as likely to happen on the very first iteration as they are during the > > 50% mark, or the 32.6% mark, or on the very last iteration. > > True, but if the system is malfunctioning then the errors should start > early. > > > Especially as the exponents get larger and larger, I see a *definite* > > possibility to reduce double check times by having first time LL tests > > report residues at certain "percentages" along the way. > > Yeah. The error rate should be proportional to the runtime which is increases > with the square of the exponent (ouch!). > > > Just for example, every 10% along the way, it'll send it's current residue > > to the Primenet server. > > I'm guessing that you mean a certain amount of the residue. Sending in > 10 2meg files for *each* exponent in the 20,000,000 range would get very > unwieldy, and inconvenient for people and primenet. > > Of course, this would only help if we were running more one test for the > same exponent at the same time (otherwise, this would just be a pointless > way to do a triple check). They would either have to be coordinated > (running at the same time, logistical knightmare), or (as Brian suggested) > have a "pool" of exponents running on one computer. That is to say when > one computer finishes to X%, it reports its 64-bit residue to primenet, and > waits for the second computer working on the same LL test to do the same. > Until the other (slower) computer reports in, the (faster) computer works on > another exponent. > > This would speed up the entire project, but it would slow down the individual > exponent, which would make people mad :(. > > > I forget the numbers being tossed around, > > but you'd only save 50% of (the error rate) of the > > checking time. > > As I pointed out above, the error rate should increase with the square of the > exponent (plus change). This means that if 1% have errors at 7mil, 22% will > have errors at 30mil. > > -Lucas Wiman > _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #610 ******************************
