Mersenne Digest Thursday, 14 May 1998 Volume 01 : Number 360 ---------------------------------------------------------------------- From: Paul Leyland Date: Tue, 12 May 1998 01:25:01 -0700 Subject: RE: Mersenne: program > Errr ... the Intel FPU internal representation always has 64 bit > mantissa, 1 sign bit and 15 bit exponent - single (longword) and > double (quadword) are automatically converted to/from this 80-bit > internal format during memory write/read cycles. Correct so far... > You can also store "long real" (80-bit) quantities directly. In the > Good Old Days when we had only i286 processors and DRAM was fast > enough that cache wasn't neccessary, doing this Made Sense. I'm not Ah, the good old days. I microcoded an IEEE floating point instruction set based almost entirely on the 8087 manual. I *think* the 80286 was available then, but it certainly wasn't common. > In some special cases you may need to store error quantities like > +/- infinity (divide by zero, tan pi/2 etc). There are special codes > for this (using the most significant bit of the mantissa set to zero) > which can't be represented in the 32-bit and 64-bit formats - they > don't actually store the mantissa MS bit, always assuming it's 1 - > so, if you wish to store these special values outside the FPU, you > *have* to use the 80-bit representation. And this is where your memory fails you. The IEEE format allows NaNs (not a number)to be stored in 32- and 64-bit forms. A NaN is a value with all the exponent bits set to 1. Three special NaN values represent "undefined" (such as the result of 0/0) and positive and negative infinity (the result of non-zero/0), though there is a projective mode which treats both inifinities as identical and calculations only ever generate one of them, that with the same bit pattern as +infinity in affine mode. The remaining bit patterns are all NaNs and may be used for whatever the programmer wishes. Approximately half of them are "signalling NaNs" which mean that using them can generate an exception; the remainder are non-signalling. I am now desparately trying to remember how the two classes are distinguished in the bit patterns. It's something like whether the most significant bit of the mantissa is set or reset. It must be 15 years or so since I last thought about this stuff... Paul ------------------------------ From: "John R Pierce" Date: Tue, 12 May 1998 01:31:06 -0700 Subject: Re: Mersenne: program >I haven't actually disassembled George's code, but I'm truly amazed >at how much performance it delivers, I'd be amazed if you could get >any really significant improvement using current Intel CPUs. You don't need to disassemble it, you can read the source, its posted on www.mersenne.org. It would probably help to have a version of MASM (the Microsoft Macro Assembler) so you could assemble it and generate listing files, it uses a LOT of macros, and might be a wee bit hard to follow if you haven't done a lot of Intel macro assembler programming. - -jrp ------------------------------ From: John Renze Date: Tue, 12 May 1998 05:11:14 -0500 (CDT) Subject: Mersenne: A theoretical question Hello all, Is it true that all Mersenne numbers with prime exponents are pseudoprimes base 2? I don't have the list archives in front of me, so this question may have been answered here before. My suspicion is that it is true, but I have been unable to come up with a proof. If someone can produce a proof or a counterexample, I would be very interested. Regards, John ------------------------------ From: Jean-Luc Cooke Date: Tue, 12 May 1998 13:30:01 -0400 Subject: Re: Mersenne: A theoretical question This is a multi-part message in MIME format. - --------------294D629ABAB296F9F97610BF Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit As far as I a have read this theorem has been around a while. But no one has been able to proof it nor find a counter proof. http://www.utm.edu/research/primes/mersenne.shtml#known The counter proof may be difficult, why? Think of the first few M(x) primes: P Digits of M(P) 2 1 3 1 5 2 7 3 13 4 17 6 19 6 31 10 61 19 The largest know Prime has an exponent of 10 digits. You only have a small number of exponents to test for counter proof!!! To see the output of any number of the form M(x) = 2^x - 1. Try my little Mersenne Java Applet: http://www.engsoc.carleton.ca/~jlcooke/Numbers/ John Renze wrote: > > Hello all, > > Is it true that all Mersenne numbers with prime exponents are pseudoprimes > base 2? I don't have the list archives in front of me, so this question > may have been answered here before. My suspicion is that it is true, but > I have been unable to come up with a proof. If someone can produce a > proof or a counterexample, I would be very interested. > > Regards, > John - -- Jean-Luc Cooke Carleton University, Electrical Engineering There is a 90% chance that right at this moment I am doing Calculus. God damn Newton, damn him to hell! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- - --------------294D629ABAB296F9F97610BF Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Jean-Luc Cooke Content-Disposition: attachment; filename="vcard.vcf" begin: vcard fn: Jean-Luc Cooke n: Cooke;Jean-Luc org: Carleton University adr: 270A Dalehurst Dr.;;;Nepean;ON;K2G 4M8;Canada email;internet: jlcooke@ottawa.com title: Electrical Engineering Student tel;work: na tel;fax: na tel;home: na note: My web page address is: www.engsoc.carleton.ca/~jlcooke/ x-mozilla-cpt: ;0 x-mozilla-html: TRUE version: 2.1 end: vcard - --------------294D629ABAB296F9F97610BF-- ------------------------------ From: Jean-Luc Cooke Date: Tue, 12 May 1998 13:35:35 -0400 Subject: Mersenne: Confusing behavior!!! This is a multi-part message in MIME format. - --------------CF29D08F078C5E92F77FBD3D Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hello all, For some reason I came down today to my NY home computer and found Prime95 (NT..95? Yes I know) trying to factor an exponont I've never seen before. Now it's back to it previous work and I have no clu why it did this! Did someone almost find a prime number? TTYL JLC Here's my results file:, it's near the end that gets confusing. - --------- [Sun Apr 19 15:30:47 1998] UID: jlcooke, User: Jean-Luc Cooke, jlcooke@ottawa.com [Sun Apr 19 16:37:58 1998] Self-test 224 passed! [Mon Apr 20 01:01:15 1998] Iteration 100000 / 4100167 [Mon Apr 20 08:09:19 1998] Iteration 200000 / 4100167 [Mon Apr 20 18:23:27 1998] Iteration 300000 / 4100167 [Wed Apr 22 12:20:41 1998] Iteration 400000 / 4100167 [Thu Apr 23 11:21:58 1998] Iteration 500000 / 4100167 [Thu Apr 23 21:31:53 1998] Iteration 600000 / 4100167 [Fri Apr 24 04:46:14 1998] Iteration 700000 / 4100167 [Fri Apr 24 12:00:18 1998] Iteration 800000 / 4100167 [Fri Apr 24 20:23:30 1998] Iteration 900000 / 4100167 [Sat Apr 25 03:49:37 1998] Iteration 1000000 / 4100167 [Sat Apr 25 11:11:25 1998] Iteration 1100000 / 4100167 [Sat Apr 25 19:36:32 1998] Iteration 1200000 / 4100167 [Sun Apr 26 06:54:43 1998] Iteration 1300000 / 4100167 [Sun Apr 26 14:11:00 1998] Iteration 1400000 / 4100167 [Sun Apr 26 22:54:23 1998] Iteration 1500000 / 4100167 [Mon Apr 27 06:11:13 1998] Iteration 1600000 / 4100167 [Mon Apr 27 14:12:52 1998] Iteration 1700000 / 4100167 [Mon Apr 27 22:08:41 1998] Iteration 1800000 / 4100167 [Tue Apr 28 06:01:57 1998] Iteration 1900000 / 4100167 [Tue Apr 28 13:56:48 1998] Iteration 2000000 / 4100167 [Tue Apr 28 22:51:42 1998] Iteration 2100000 / 4100167 [Wed Apr 29 06:04:50 1998] Iteration 2200000 / 4100167 [Wed Apr 29 13:59:45 1998] Iteration 2300000 / 4100167 [Thu Apr 30 00:07:42 1998] Iteration 2400000 / 4100167 [Thu Apr 30 07:23:59 1998] Iteration 2500000 / 4100167 [Thu Apr 30 15:46:21 1998] Iteration 2600000 / 4100167 [Fri May 01 00:12:23 1998] Iteration 2700000 / 4100167 [Fri May 01 07:22:29 1998] Iteration 2800000 / 4100167 [Fri May 01 15:07:14 1998] Iteration 2900000 / 4100167 [Fri May 01 22:56:03 1998] Iteration 3000000 / 4100167 [Sat May 02 06:32:00 1998] Iteration 3100000 / 4100167 [Sat May 02 13:58:58 1998] Iteration 3200000 / 4100167 [Sat May 02 22:58:02 1998] Iteration 3300000 / 4100167 [Sun May 03 06:16:59 1998] Iteration 3400000 / 4100167 [Sun May 03 13:31:20 1998] Iteration 3500000 / 4100167 [Sun May 03 22:14:51 1998] Iteration 3600000 / 4100167 [Mon May 04 06:14:04 1998] Iteration 3700000 / 4100167 [Mon May 04 13:21:29 1998] Iteration 3800000 / 4100167 [Mon May 04 22:38:22 1998] Iteration 3900000 / 4100167 [Tue May 05 06:45:59 1998] Iteration 4000000 / 4100167 [Tue May 05 14:38:41 1998] Iteration 4100000 / 4100167 UID: jlcooke/Marvin, M4100167 is not prime. Res64: 1384536DDD569553. WR1: DC74F031 [Tue May 05 15:28:45 1998] Self-test 256 passed! [Thu May 07 12:53:51 1998] Iteration 100000 / 4699003 [Fri May 08 21:59:16 1998] Iteration 200000 / 4699003 [Sat May 09 07:20:42 1998] Iteration 300000 / 4699003 [Sat May 09 15:35:26 1998] Iteration 400000 / 4699003 [Sun May 10 02:47:40 1998] Iteration 500000 / 4699003 [Sun May 10 10:55:16 1998] Iteration 600000 / 4699003 [Sun May 10 20:10:08 1998] Iteration 700000 / 4699003 [Mon May 11 04:56:12 1998] Iteration 800000 / 4699003 [Mon May 11 13:52:33 1998] Iteration 900000 / 4699003 [Mon May 11 22:07:48 1998] Iteration 1000000 / 4699003 [Tue May 12 06:32:09 1998] Iteration 1100000 / 4699003 [Tue May 12 09:50:40 1998] Factored M4789517 through 176892843*2^32 (pass 4 of 16). [Tue May 12 12:00:33 1998] Factored M4789517 through 345397078*2^32 (pass 7 of 16). [Tue May 12 12:57:10 1998] UID: jlcooke/Marvin, M4789517 has a factor: 182908732768315511 - ---------------- - -- Jean-Luc Cooke Carleton University, Electrical Engineering There is a 90% chance that right at this moment I am doing Calculus. God damn Newton, damn him to hell! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- - --------------CF29D08F078C5E92F77FBD3D Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Jean-Luc Cooke Content-Disposition: attachment; filename="vcard.vcf" begin: vcard fn: Jean-Luc Cooke n: Cooke;Jean-Luc org: Carleton University adr: 270A Dalehurst Dr.;;;Nepean;ON;K2G 4M8;Canada email;internet: jlcooke@ottawa.com title: Electrical Engineering Student tel;work: na tel;fax: na tel;home: na note: My web page address is: www.engsoc.carleton.ca/~jlcooke/ x-mozilla-cpt: ;0 x-mozilla-html: TRUE version: 2.1 end: vcard - --------------CF29D08F078C5E92F77FBD3D-- ------------------------------ From: mihailes@inf.ethz.ch Date: Tue, 12 May 1998 19:40:54 +0200 (MET DST) Subject: Re: Mersenne: A theoretical question > Hello all, > > Is it true that all Mersenne numbers with prime exponents are pseudoprimes > base 2? I don't have the list archives in front of me, so this question > may have been answered here before. My suspicion is that it is true, but > I have been unable to come up with a proof. If someone can produce a > proof or a counterexample, I would be very interested. > All Mersenne numbers m = 2^p-1, p prime, are strong pseudoprimes base 2. Put m-1 = 2^p - 2 = 0 mod p (little Fermat), thus m-1= 2^s.k.p, for some odd k and s > 0. Since 2^((m-1)/2^s) = 2^(kp) = (2^p)^k = 1 mod m, it follows that m is strong pseudo prime base 2. Preda > Regards, > John > ------------------------------ From: Nick Craig-Wood Date: Tue, 12 May 1998 19:10:49 +0100 (BST) Subject: Re: Mersenne: A theoretical question In on Tue 12 May, John Renze wrote: > Is it true that all Mersenne numbers with prime exponents are pseudoprimes > base 2? I don't have the list archives in front of me, so this question > may have been answered here before. My suspicion is that it is true, but > I have been unable to come up with a proof. If someone can produce a > proof or a counterexample, I would be very interested. Here is a sketch of a proof If p is a pseudoprime to base 2 then 2^(p-1) mod p = 1 Where p = 2^n-1 for Mersenne numbers. So if Mn is a psudo-prime to base 2 then 2^(2^n-2) mod 2^n-1 = 1 However (exercise for reader to prove ;-) 1: 2^m mod 2^n-1 = 2^(m mod n) So 2^(2^n-2) mod 2^n-1 = 1 substitute m=2^n-2 in 1: => 2^(2^n-2 mod n) = 1 = 2^0 => 2^n-2 mod n = 0 => 2^n mod n = 2 divide both sides by 2 => 2^(n-1) mod n = 1 Which is precisely the test for a n being a psuedo prime. Therefore if n is a psuedo prime then Mn is a pseudo prime. Since all primes are pseudoprimes this proves your statement. - -- Nick Craig-Wood ncw1@axis.demon.co.uk http://www.axis.demon.co.uk/ ------------------------------ From: George Woltman Date: Tue, 12 May 1998 14:22:49 -0400 Subject: Re: Mersenne: Confusing behavior!!! At 01:35 PM 5/12/98 -0400, Jean-Luc Cooke wrote: >Hello all, > >For some reason I came down today to my NY home computer and found >Prime95 (NT..95? Yes I know) trying to factor an exponont I've never >seen before. Now it's back to it previous work and I have no clu why it >did this! When you near completion of an exponent, prime95 gets another exponent to test from the server (so you have no idle time). If this new exponent has not been trial factored sufficiently, prime95 will stop the Lucas-Lehmer test and trial factor the new exponent. This will insure that the new exponent requires an LL test and that you therefore have several more weeks of work queued up. In your case, you found a factor! You can expect prime95 to ask the server for another exponent - which may once again interrupt the LL test to do some factoring. Best regards, George ------------------------------ From: "Chris Harrison" Date: Tue, 12 May 1998 08:32:44 -0600 Subject: Re: Mersenne: program On Tue, 12 May 1998 09:02:01 GMT, Brian J Beesley wrote: >The argument started from the premise that perhaps the code could be >tweaked a bit to improve Prime95's performance on AMD CPUs. Well, >perhaps it could. But I'm afraid that the currently available AMD >processors will always deliver disappointing floating-point >performance compared with the nearest spec Intel chip. The code could be improved by as much 30-50% for the amd cpu. I have looked at it and researched it a bit, but unfortunatly have no time to recode it. The intel chips uses FXCH to make the stack based fpu look like it has registers and help with the pipelining of code. INtel gets FXCH for *FREE*. The amd k6 FXCH takes 2 clocks for this register rename. IF the code was reordered and setup not to use FXCH the amd k6 would get a big speed kick out of it. FXCH is used about ever other line of code. > >This doesn't mean that I'm opposed to AMD CPU's - for general usage, >the K6 is certainly worth considering as an alternative to an >equivalent spec Intel MMX, being much cheaper and arguably even a >little faster for integer work - but, considered purely as a platform >for running Prime95, the Intel CPUs are clearly superior. Actually, good asm on a alpha would be clearly superior =) Later chris could you forward this to the mailling list? i dont have the address here with me. ------------------------------ End of Mersenne Digest V1 #360 ******************************