Mersenne Digest Wednesday, April 26 2000 Volume 01 : Number 724 ---------------------------------------------------------------------- Date: Mon, 24 Apr 2000 18:41:39 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: why sieving to > 64 bits is slow On 21 Apr 00, at 16:24, [EMAIL PROTECTED] wrote: > The reason is quite simple: Prime95 can do speedy > factoring up to 64 bits by using the 64-bit mantissa of > an x86 register float to store the trial factor (and > various intermediate quantities modulo the trial factor) > and doing integer multiply (which is normally quite slow > on x86) by way of the FPU, which can pipeline the MULs. > As soon as the trial factor size exceeds this 64-bit > natural wordsize, one must go to a double-word > representation, hence the factor-of-four-or-so slowdown. Well, 96-bit integer operations on IA32 architecture are reasonably natural. But, in general, you get less help from the FPU, & you need 1.5 ^ 2 times as many operations to do triple-precision arithmetic as you do to do double-precision arithmetic. Plus, on the Intel, you start running out of registers & need to write intermediate results to memory, which costs extra cycles ... > > I'm in agreement with Brian Beesley on this issue: > especially now that there's the capability to do P-1, I > think sieving to > 64 bits will prove to be a waste of > time, since we should be able to find nearly all the > factors > 64 bits that sieving would turn up more > cheaply using P-1. No - we will only find _some_ of the factors > 64 bits, but P-1 is running a lot quicker than trial factoring out at the large end. e.g. less than one week to run P-1 on 33219281 (B1=145000, B2=1015000) compared with about 3 weeks to trial factor to 69 bits. If we get only one in four of them, that's cost effective. BTW P-1 will find _some_ factors > 69 bits as well. > > That assumes that our priority is maximizing GIMPS > throughput, rather than being able to say with certainty > that such-and-such a number has no factors less than, > e.g., sixty-eight bits. Precisely. > > George, when do you expect sufficient data to be able > to quantify the relative effectiveness of sieving vs. > P-1 for these larger factor size ranges? The statistical probabilities are reasonably well modelled in, e.g., Riesel "Prime Numbers & Computer Methods for Factorization" p156 ff. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 18:41:39 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Double Checking Finds A Factor On 22 Apr 00, at 12:41, Dieter Schmitt wrote: > this 71-bit factor was found by P-1 out of 17 exponents (so far): > > [Sat Apr 15 01:47:40 2000] > P-1 found a factor in stage #1, B1=25000, B2=275000. > UID: dismit/P233MMX, M4428701 has a factor: 3035629975521900014017 > > It was found at stage 1 by V20 beta 4. I'd have expected finding > factors at lower bits first. All the factors of M4428701 are of the form 2.4428701.k+1, in this case k = 342722389197408 = 2^5.3.11^2.17.53.251.283.461 Note that all the prime factors of k are (considerably) less than 25000 which is why the factor was found in stage 1. In this case, running P-1 stage 1 only with B1 = 500 would have sufficed! > > Well it finally happened to me...., I was double checking an > exponent in > > the 5M range, using the beta of V20 and it found a factor! I often > wondered > > about how often that happened, anyone have any other hard data? I've been lucky & found a couple in about 40 runs. (Since I was in early on the QA trials...) Actually the theoretical chance of finding a factor with particular B limit values appears to be working out pretty well. Not surprising really! This chance is printed in the console window when a P-1 run starts, or resumes after being stopped. > > > > 5008021 63 DF 7054282710141713489 10-Apr-00 07:09 gateway k = 704298435464 = 2^3.13.103.4639.14173 Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 21:08:46 +0200 From: Henk Stokhorst <[EMAIL PROTECTED]> Subject: Mersenne: FPU vs ALU Hi, The new IA-32 processor under development, codenamed 'Willamette', has a 64 bit FPU and an ALU running at twice the clockfrequency. However, the latencies are different from the existing Pentiums. Did anybody have a look at the processor and determined if the ALU or the FPU of the Willamette should be preferred for LL testing? YotN, Henk Stokhorst. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 12:56:07 -0700 From: Michael Gebis <[EMAIL PROTECTED]> Subject: Re: Mersenne: Electron Winds and Prime00 >>>>> "STL137" == STL137 <[EMAIL PROTECTED]> >>>>> wrote the following on Fri, 21 Apr 2000 17:40:55 EDT STL137> All the recent stuff about HDs and what would cause Prime95 STL137> to fail first got me thinking. I know theoretically about STL137> "electron wind", the phenomenon that pushes around metal and STL137> other atoms in chips, albeit slowly. Does anyone know of a STL137> real instance of a CPU failing due to the electron wind? I STL137> remember reading that it would take 20 or so years to do so. When I was still a lad in school, I once went to a presentation given by AMD. I forget the overall topic of the presentation, but I do remember one bit quite well. A detail of a small section of the chip was put up; it looked something like this: XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXXX XXX XXX XXX XXXXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX This is a four-bit bus, running up and down, where the X's represent the metal making up the individual wires. The reason the guys from AMD had this photo was because this chip had been returned as defective, after already leaving the plant as functional. They spent a lot of effort examining this escape. Notice the defect on the leftmost wire in the bus. The explanation for the failure was this: The chip was made with an (unintentional) bump on that wire. The bump wasn't big enough to cause any problems initially. However, the electric field was stronger at the bump, making the metal atoms drift that much faster. At some point, the bump shorted the two wires on the bus, and things stopped working. Mike _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 16:37:20 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Re: p-1 Dieter Schmitt wrote: > P-1 found a factor in stage #1, B1=25000, B2=275000. > M4428701 has a factor: 3035629975521900014017 > It was found at stage 1 by V20 beta 4. I'd have > expected finding factors at lower bits first. You're misunderstanding how the p-1 algorithm works. p-1 run to stage 1 bound B1 succeeds if any of the the factors of the number in question is of the form f1*f2*...*fn + 1, and all the f's are no greater than B1. For Mersennes, things are even better: we know that all factors of 2^p - 1 (p prime) are of the form 2*k*p + 1, i.e. we already know a priori what one of the f's (and in fact often the largest one) must be, so all we need is for the integer k to be B1-smooth. For the factor F which your run found, note that F - 1 = 2^6.3.11^2.17.53.251.283.461.4428701 = 2*k*p, so in this case k is exceptionally smooth - had the stage 1 limit been just B1 = 500 (say), it would have still found this factor. Of course this analysis is retrospective; in general k won't be this smooth, and since the cost of running the GCD on numbers this big is appreciable, we prefer to run p-1 to a rather deeper bound before testing for a factor. In your case a second stage wasn't necessary, but in general stage 2 succeeds if k has just one factor in the interval [B1+1, B2], and all other factors are no greater than B1. That's because stage 2 uses a different powering algorithm which is substantially cheaper on a prime-for-prime basis than that used in stage 1, but which is restricted to the case of there being a single outlying prime. We do things this way because a high percentage of general composites are of this form, i.e. have only one large prime factor. Cheers, - -Ernst _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 18:13:32 -0400 (EDT) From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> Subject: Re: Mersenne: FPU vs ALU On Mon, 24 Apr 2000, Henk Stokhorst wrote: > Hi, > > The new IA-32 processor under development, codenamed 'Willamette', has a 64 bit FPU > and an ALU running at twice the clockfrequency. However, the latencies are different > from the existing Pentiums. > > Did anybody have a look at the processor and determined if the ALU or the FPU of the > Willamette should be preferred for LL testing? Preliminary results seem to indicate that comapartively speaking, integer multiplies take *longer* on Willamette than on previous Intel processors. The big difference here is that "Willie" will have a quad 64-bit bus to memory, 128-byte cache lines(I think), and SSE extensions that allow for full 53-bit double precision floating point from SSE, i.e. working on pairs of doubles at a time. I think that there will also be SSE extensions to do 32-bit integer multiplies, meaning that the vector stuff can finally be effectively used for crypto and multiprecision integer arithmetic. jasonp _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 24 Apr 2000 20:33:06 -0400 From: "Marc Honey" <[EMAIL PROTECTED]> Subject: Mersenne: HD Heads stuck This is a multi-part message in MIME format. - ------=_NextPart_000_0046_01BFAE2C.4C1371C0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I apologize if this has been addressed but I read an e-mail that I feel = I need to address. If you hard drive is a maxtor under 20 gigs and it clanks like the heads = are hitting the side of the drive inside you are in luck. 99.9% of the = time this is an electronics failure and not a physical head assembly = prob. I have fixed this at least 50 times by simply replacing the = electronics portion of the HD with an identical one from a good drive. = In fact my exact process would be to call Maxtor and arrange an advance = ship RMA and once I got the good drive I would swap boards and send back = the bad electronics along with the new hda they sent. Normally I would = think this sorta un-ethical but in all honesty I was told to do this by = a maxtor tech rep. - ------=_NextPart_000_0046_01BFAE2C.4C1371C0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-1" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2314.1000" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV><FONT size=3D2>I apologize if this has been addressed but I read an = e-mail=20 that I feel I need to address.</FONT></DIV> <DIV> </DIV> <DIV><FONT size=3D2>If you hard drive is a maxtor under 20 gigs and it = clanks like=20 the heads are hitting the side of the drive inside you are in = luck. 99.9%=20 of the time this is an electronics failure and not a physical head = assembly=20 prob. I have fixed this at least 50 times by simply replacing the=20 electronics portion of the HD with an identical one from a good = drive. In=20 fact my exact process would be to call Maxtor and arrange an advance = ship RMA=20 and once I got the good drive I would swap boards and send back the bad=20 electronics along with the new hda they sent. Normally I would = think this=20 sorta un-ethical but in all honesty I was told to do this by a maxtor = tech=20 rep.</FONT></DIV> <DIV> </DIV> <DIV> </DIV></BODY></HTML> - ------=_NextPart_000_0046_01BFAE2C.4C1371C0-- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 25 Apr 2000 09:06:57 EDT From: "Nathan Russell" <[EMAIL PROTECTED]> Subject: Mersenne: Version ID Buglet Hi, I was just checking my account report. I have always kept about 2 weeks of double checking assignments in case my QA work finishes and I am unable to get more for some reason. Those assignments that I have checked out with v20 (some combination of betas #2-4 I believe) state on the account report that they were checked out using v16. I have a hunch that this is the server's fault, possibly due to a rollover of some sort, but it may be something that you want to have them look at before it starts mistaking v21 for v17. I suppose another possibility may be due to my using the manual testing forms to obtain the assignments, however I have updated the completion dates since then, and the manual forms never prompt for version numbers. Regards, Nathan ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 25 Apr 2000 09:18:12 EDT From: "Nathan Russell" <[EMAIL PROTECTED]> Subject: Mersenne: Re: buglet Sorry, almost forgot. Here's the relevant snippet, it'll look a touch funny because of the short line length Hotmail will force on me: ------- Exponents Assigned ------- Assignment overdue check-in is set at 60.0 days (0.0 days to expire) prime fact current days exponent bits iteration run / to go / exp date updated date assigned computer ID Mhz Ver - -------- -- ---- --------- ----------------- --------------- - --------------- ------------ ---- --- 4481069 D 61 5.3 25.4 78.4 23-Apr-00 23:20 20-Apr-00 07:54 Bucephalus 600 v16 4783861 D 62 5.3 31.4 78.4 23-Apr-00 23:20 20-Apr-00 07:56 Bucephalus 600 v16 4790309 D 62 23.1 20.4 78.4 23-Apr-00 23:20 02-Apr-00 11:25 Bucephalus 600 v19 4822121 D 62 5.3 20.8 80.8 20-Apr-00 07:56 Bucephalus 600 v16 Lucas-Lehmer testing : 0 Factoring only : 0 Double-checking LL : 4 - ---------------------- ------- TOTAL : 4 ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 25 Apr 2000 08:21:15 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Mersenne: Version ID Buglet I've forwarded Nathan's message to Scott Kurowski. (He usually reads the digest version, IIRC, so this may speed a solution.) Please do not send duplicate messages to him regarding the possible primenet bug that Nathan described. Thanks, Ken _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 26 Apr 2000 01:39:13 EDT From: "Nathan Russell" <[EMAIL PROTECTED]> Subject: Mersenne: Priority double-checking Hi everyone, I recall reading about a priority queue for double-checking those exponents whose original tester reported hardware errors. I estimate at a glance that there are seventy or eighty such exponents now queued, compared with about 5k regular double-checking assignments. What I am wondering is, who does this testing? Is the next person to log on given the exponent, which may be larger than they expect, or than their machine can do in a reasonable time? Or is there a group that has volunteered? If so, how would one request such assignments? Curious, Nathan ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 26 Apr 2000 15:21:33 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Generalizing Mersenne The generalized form of Mersenne (x^n -1)/(x-1) can be generalized further to x^n - ((x-2)(x^k) +1)/(x-1) this formula computes x^n - (x^p - (x^(p-1) + x^(p-2) + x^(p-3) + . . . + x ^2 + x + 1) ). If n = p, x = 2, the result is a Mersenne. You can go back farther and farther into this, but I think the three variable solution is the best of them. _________________________________________________________________ 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 #724 ******************************
