Mersenne Digest Monday, November 8 1999 Volume 01 : Number 657 ---------------------------------------------------------------------- Date: Sat, 6 Nov 1999 16:07:06 EST From: [EMAIL PROTECTED] Subject: Mersenne: Re: fast GCD George Woltman writes: >Since F24 is 5 million digits your computer would take 5 minutes * 5^2, >or 2 hours. Given your machine is faster, my code is 32-bit, my code >does an extended GCD, the Alpha is a better architecture, and your code >is probably better - you come up with the factor of 12 difference. Was your code doing a true Fermat-mod DWT, or were you attempting to factor instead the Mersenne number M(2^25-1) = (2^(2^24)-1)*(2^(2^24)+1)? In the latter case your GCD would involve vectors twice as long, which would mean a factor-of-4 runlength increase for an O(n^2) algorithm. >Now the good news. Crandall's giants code has an implementation of >the O (n * log n * log n) GCD in it. It was painfully slow. After two >days of optimizing, I will be able to do that 5 million digit >GCD in an estimated 30 minutes. Impressive - can you give us a brief summary of the most time-impacting changes you made, and were these to the C source or in ASM? >BTW, I know of no other publicly available implemetation of the fast GCD. >It was written by J. P. Buhler. I know little about it, except that Crandall mentioned it took them the better part of 6 months to get the thing written and debugged. Better them than you, right? :) Jason Papadopoulos writes: >I've heard lots of complaints that IA64 has no fully-integer multiply >(i.e. you have to load your numbers into an FPU register and pull the >result back). Actually, there have been a lot of gripes about IA64; >Intel's developers' guide is great reading but quite difficult at times. Respectfully, I believe this is a point on which the purists may be plain wrong. One thing that impresses me about the IA64 (at least judging from the hardware guide) is the flexibility regarding loading integers into either a 64-bit integer (a.k.a. general-purpose) register or into a floating register mantissa - sure, the IA64 has no separate integer multiply unit, but if it can quickly load two 64-bit ints into floating registers and then use the floating multiply unit (which is fully pipe- lined and very fast) to get either the low or high 64 bits of the 128-bit (exact integer) product, then that's a real gain. One thing about the above operation (specifically the upper 64-bit calculation) that intrigues me is how the IA64 effects error correction of the floating product. On an IEEE-compliant machine, one can use an FMUL to get the upper 52 bits of an integer product of up to 52+64=116 bits in length, a standard 64-bit integer MUL to get the low 64 bits, and one uses the remaining bit (the lowest-order bit of the 53-bit floating mantissa) to compare to the corresponding bit in the 64-bit integer product to effect error correction. Perhaps the IA-64 uses a 65-th mantissa bit in the floating multiplier to do this? Cheers, - -Ernst ftp://209.133.33.182/pub/mayer/home.html _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 06 Nov 1999 22:47:07 +0100 From: Francois E Jaccard <[EMAIL PROTECTED]> Subject: Mersenne: Version 19 for FreeBSD? Hi, Will a version 19 for FreeBSD be available? I would like to transfer a 33M exponent to a FreeBSD 4.0-current machine. Thanks! - -- Francois Jaccard Public Key: http://keys.pgp.com:11371/pks/lookup?op=get&search=0x11CA35A6 PGP Key Fingerprint:7268 1690 7448 0FE4 0B40 3BD6 E550 CBCE 11CA 35A6 ICQ: 270437 _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 06 Nov 1999 17:19:25 -0500 From: George Woltman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: fast GCD Hi, At 04:07 PM 11/6/99 EST, [EMAIL PROTECTED] wrote: >Was your code doing a true Fermat-mod DWT, or were you attempting to >factor instead the Mersenne number M(2^25-1) = (2^(2^24)-1)*(2^(2^24)+1)? Prime95 uses a true Fermat-mod DWT. >Impressive - can you give us a brief summary of the most time-impacting >changes you made, and were these to the C source or in ASM? There were a few things in giants that were not done efficiently. For example, dividing one huge number by another was done using reciprocals and then multiplying. Well, 99.9% of the time in a GCD the quotient will be less than 2^32 and can be derived by one floating point divide on just the high order bits. It was also a bit of a memory hog. I also upgraded giants from 16-bit to 32-bit, made use of some ASM helper routines, cleaned up memory management, etc. The changes I've made have been forwarded to Dr. Crandall for possible incorporation into a future release of giants. >>BTW, I know of no other publicly available implemetation of the fast GCD. >>It was written by J. P. Buhler. > >I know little about it, except that Crandall mentioned it took them >the better part of 6 months to get the thing written and debugged. >Better them than you, right? :) Absolutely! And it is quite elegant. You should be able to incorporate it into your code with little trouble. I had little trouble upgrading it to do modular inverses too. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 6 Nov 1999 18:09:09 -0500 From: Bryan Fullerton <[EMAIL PROTECTED]> Subject: Re: Mersenne: Version 19 for FreeBSD? On Sat, Nov 06, 1999 at 10:47:07PM +0100, Francois E Jaccard <[EMAIL PROTECTED]> wrote: > Will a version 19 for FreeBSD be available? I would like to transfer a 33M > exponent to a FreeBSD 4.0-current machine. I'm also waiting for the FreeBSD v19 client. Bryan - -- Bryan Fullerton http://www.samurai.com/ Core Competency Samurai Consulting 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: Sat, 6 Nov 1999 21:41:06 EST From: [EMAIL PROTECTED] Subject: Mersenne: Re: Mersenne Digest V1 #656 Who's sending mail to the list that makes the digests appear with a red background in my AOL mailreader? Arrgh... afterimage... AFTERIMAGE! S.T.L. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 7 Nov 1999 13:55:31 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Database files Hi everyone, (1) Unless I get a strong complaint, I am going to stop putting up the unzipped versions of the hrf3 and lucas_v database files on my anon ftp server (lettuce.edsc.ulst.ac.uk). (2) I intend to provide new files derived from the database, as follows: (a) a simple list of exponents which have had only one LL test result reported; (b) a simple list of exponents which have had at least two LL test results reported with the residue confirmed; (c) a simple list of exponents which have had two or more LL test results reported but with different residues; (d) a "cut down" version of the lucas_v file, format as at present but omitting exponents below 2 million. The limit to be raised progressively in step with the lowest remaining unverified exponent. Omitting the "small" exponents cuts the file to approximately half its present size, making for a more convenient download. The justification for (a), (b) and (c) is that sometimes one wants to know the status of an exponent without needing the other details stored in the complete database. Comments? (3) George, there are (a handful of) exponents over 10 million which have verified residuals. Would it be possible to add these into the lucas_v file? (4) As a consequence of refurbishment of the electrical system in the building where it lives, my anon ftp server lettuce.edsc.ulst.ac.uk will be offline from 17:00 UTC this Friday 12-Nov until 08:00 UTC next Monday 15-Nov. I apologize for the inconvenience. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 7 Nov 1999 11:25:52 -0800 From: Greg Hewgill <[EMAIL PROTECTED]> Subject: Mersenne: v17 double checking Now that double checking has surpassed exponent 4194304, what happens to all those machines out there running the old v17 that produced incorrect results for LL tests above that exponent? (I don't have any, but they almost certainly exist.) Up to this point they will have been successfully doing double checking LL tests. Now they will be producing incorrect double checking results. Perhaps they should be given factoring assignments by the Primenet server? Greg Hewgill _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 7 Nov 1999 16:09:00 -0500 (EST) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: v17 double checking > Now that double checking has surpassed exponent 4194304, what happens to all > those machines out there running the old v17 that produced incorrect results > for LL tests above that exponent? (I don't have any, but they almost certainly > exist.) Up to this point they will have been successfully doing double checking > LL tests. Now they will be producing incorrect double checking results. > > Perhaps they should be given factoring assignments by the Primenet server? I'm guessing so... Of course they will eventually run out too, then we will either have to admit that these computers are now basically worthless to us (unless there is some way to reach them), or just try and give them some kind of error from primenet (?). Perhaps if there were some way to give an error like: Primenet error 1221: Invalid assignment "IMPORTANT: SEE http://entropia.com/important.html" - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 7 Nov 1999 23:26:48 +0100 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Version 19 for FreeBSD? On Sat, Nov 06, 1999 at 10:47:07PM +0100, Francois E Jaccard wrote: >Hi, >Will a version 19 for FreeBSD be available? I would like to transfer a 33M >exponent to a FreeBSD 4.0-current machine. I've heard that mprime works in `Linux emulation mode', whatever that might be (I don't run FreeBSD myself), but I can't say anything for sure. You might want to try it. (I think I read it in some of the old (a few months back) traffic on this list.) I'm sure George would appreciate if FreeBSD'ers fixed the code (if it needs fixing), and sent some patches to him. /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 08 Nov 1999 12:14:33 +1300 (NZDT) From: Bill Rea <[EMAIL PROTECTED]> Subject: Mersenne: Mlucas on SPARC >>At 256K FFT I was seeing 0.11 secs/iter with >>Mlucas against 0.15 secs/iter for MLU, at 512K FFT the figures were >>0.25 secs/iter and 0.29 secs/iter respectively. > >...and don't forget the added benefits due to Mlucas being able to >test significantly larger exponents at the same FFT length, as well >as having intermediate runlengths between powers of two. 0.11 seconds >at 256K is impressive - that's faster than on my 400MHz Alpha 21164 >(0.16 sec) and Prime95 on a 400MHz PII (0.13sec), though, to be fair, >both of the latter systems have a smaller (512KB) L2 cache. Observing the running process with top, it looks to me as if the 256K Mlucas fits completely in the L2 cache, whereas MLU takes about 12Mb. At 512K FFT around 60% of the running process will fit in the L2 cache. It's a cache size issue here. On my Ultra-5 with a small 256Kb L2 cache I get 0.58 secs/iter for MLU against 0.78 secs/iter for Mlucas at 512K FFT. >>Mlucas runs significantly faster if you can compile and run it >>on a 64-bit Solaris 7 system. > >This is the first I've heard of this - roughly how much of a speedup >do you see? I'm a bit red-faced on this one. I just tried it again and it doesn't. This is still a mystery to me. It would seems to me that for this type of code that having full access to the 64-bit instruction set of the UltraSPARC CPUS and running it on a 64-bit operating system would give you the best performance. But that doesn't seem to be the case. Ernst, would you expect your code to run faster this way? 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: Sun, 7 Nov 1999 19:49:11 -0500 (EST) From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> Subject: Re: Mersenne: Mlucas on SPARC On Mon, 8 Nov 1999, Bill Rea wrote: > I'm a bit red-faced on this one. I just tried it again and it doesn't. > This is still a mystery to me. It would seems to me that for > this type of code that having full access to the 64-bit instruction > set of the UltraSPARC CPUS and running it on a 64-bit operating system > would give you the best performance. But that doesn't seem to be the > case. > As long as you talk only about floating point instructions, even the gnu assembler uses all the 64-bit code you're likely to see. The only extension the SPARC V9 instruction set has that would be of interest is a 64-bit load and store; but the gnu assembler seems to alias the assembly mnemonic for "ldd" and "std" to the V9 version automatically (I guess so that older FPU code can take advantage of the new faster instructions). Either that, or (more likely) the UltraSPARC doesn't support the V8 load and store double at all, but uses its opcode for the newer V9 version. jasonp _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 8 Nov 1999 01:28:05 -0500 From: Bryan Fullerton <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Version 19 for FreeBSD? On Sun, Nov 07, 1999 at 11:26:48PM +0100, "Steinar H. Gunderson" <[EMAIL PROTECTED]> wrote: > > I've heard that mprime works in `Linux emulation mode', whatever that might > be (I don't run FreeBSD myself), but I can't say anything for sure. You > might want to try it. (I think I read it in some of the old (a few months > back) traffic on this list.) Well, yes, that's possible - or we can just run the v18 client for FreeBSD. > I'm sure George would appreciate if FreeBSD'ers fixed the code (if it needs > fixing), and sent some patches to him. Given that there already is a v18 for FreeBSD, I'd assume that there's someone who's helping George with that. Is that a correct assumption? Bryan - -- Bryan Fullerton http://www.samurai.com/ Core Competency Samurai Consulting 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: Mon, 08 Nov 1999 18:18:43 +0100 From: Paul Landon <[EMAIL PROTECTED]> Subject: Mersenne: What's ERH? Sorry I'm stupid or ignorant (on Mondays), what's ERH? I guess the H is Hypothesis. > On Mon, Nov 01, 1999 at 07:35:03PM -0800, Stefan Struiker wrote: > >Haven't received any forwards since Friday Oct. 29th... > > That's because the list is so silent. > > We need more life. Allow me :-) > > Poaching is evil. The millennium starts year 2001. GIMPS is cooler that > distributed.net and SETI@Home combined. And of course, we shouldn't start > discussions like this ;-) > Erm, PCs are better than Macs. The first real computer was the Manchester Mark 1 aka the SSEM or the "Baby". Some people believe that factoring numbers with lots of zeroes is superior to primality checking lots of ones, but anyway Fermat numbers are merely Generalised Mersennes with the simple base 2^2^x and the trivial exponent of 2. ;-v - --Paul Landon _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 8 Nov 1999 13:09:33 -0800 From: "Joth Tupper" <[EMAIL PROTECTED]> Subject: Re: Mersenne: What's ERH? - ----- Original Message ----- From: Paul Landon <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Monday, November 08, 1999 9:18 AM Subject: Mersenne: What's ERH? > Sorry I'm stupid or ignorant (on Mondays), what's ERH? > I guess the H is Hypothesis. > The RH is for Riemann Hypothesis. The RH is that all zeros of the Riemann zeta function lie on the line x=1/2 in the Complex plane. The Riemann zeta function: zeta (s) = sum of n^(-s) for n=1,2,3,... zeta (2k) is known for k>0 an integer. I always remember zeta(2) = (pi^2)/4 and I think zeta(4) = (pi^4)/90. The zeta function has a rich history of which I, alas, know very little. I think the ERH is the extended RH. I will have to defer to someone who knows a lot more than I do. Joth _________________________________________________________________ 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 #657 ******************************
