Re: Mersenne: Question about double checking
George Woltman wrote: The optimal breakeven point for factoring vs. LL testing changes every time the factoring code or LL code changes. In the old days, the breakeven point was 2^56, now its 2^57. Does that take into account the fact that a factor found does not require time to check, whereas a LL residue needs to be computed twice? Interesting. Actually double-checking factors found *is* required, but it's *very* cheap since you can just do the trial division, omitting all the failed attempts. The optimum amount of factoring to do is (obviously?) to balance the factoring time against the LL test time multiplied by the probability of finding a factor. Just how this is done (or "guessed at") I don't know, however having "partial" factorization attempts done already seems to muddy the water a bit, as does the extra time to double-check a LL test, as you say. I think the real point is that trial factoring with the current program only works to 2^64 (approx. 20 decimal digits). ECM is expensive, running enough curves to be reasonably sure of finding all factors up to approx. 40 decimal digits takes *much* longer than running an LL test, and is in any case impractical for exponents 1,000,000 (until we get processors with much greater precision basic data types i.e. longer registers!) factoring rules! Well, up to a point ... but just how long would it take you to *prove* that, e.g., Clarkson's Number (M3021377) is prime, by eliminating all possible factors? Regards Brian Beesley
Re: Mersenne: 128 floatingpoint operations
Testing Mersenne primes involves a lot of multiplication (and division) of very large numbers, but better algorithms are used so that the multiplication time is something line O( n^2 log(n) log(log(n)) ). This is probably a typo: with FFT or similar methods multiplication time is aproximately O( n log(n) log log(n) ). BTW, there is a simple method, simple enough to be used by hand, which already reduces multiplication time to O( n^a ), where a = log 3 / log 2 = 1.584962501. In order to multiply two numbers with two digits each, say M = Ad + B and N = Cd + D, d being the base, we normally perform four multiplications: AC, AD, BC and BD in order to get the answer: MN = AC d^2 + (AD + BC) d + BD This expression however shows that AD and BC are never used alone: only the sum matters. This sum can be computed as AD + BC = (A+B)(C+D) - AC - BD; notice that AC and BD will be computed anyway so that now we perform three multiplications instead of four. We may recursively repeat this process in order to reduce the number of products from n^2 to n^a; true, there are many sums, but sums are cheap. The library gmp (GNU multi-precision) uses this algorithm although it is much slower than FFT-like methods. Maybe because it only involves integers, and there is no danger at all of rounding errors. I once wrote a gmp-based program to perform LL tests: for low exponents it worked fine but for the prime 65537 it already took much longer that mprime.
Re: Mersenne: 128 floatingpoint operations
At 11:47 AM 11/4/98 -0200, Nicolau Corcao Saldanha wrote: is something line O( n^2 log(n) log(log(n)) ). This is probably a typo: with FFT or similar methods multiplication time is aproximately O( n log(n) log log(n) ). That's right - my error. +--+ | Jud McCranie [EMAIL PROTECTED] | +--+
Re: Mersenne: Question about double checking
George responded: At 07:49 PM 11/3/98 +0100, you wrote: Does that take into account the fact that a factor found does not require time to check, whereas a LL residue needs to be computed twice? Yes and no. I don't take it into account when I compute the breakeven point, but I always use the best case factoring code. Thus I compute the limit using PPro and PII factoring timings which are twice as fast as a Pentium of similar clock speed. Thus Pentiums are probably over-factoring and PPros and PIIs are under-factoring. Regards, George
Mersenne: Version 17.1
Hi all, Version 17.1 (with 2^N+1 ECM factoring and INI files that support a new Time= option) is now available for Linux and Windows NT service users (http://www.mersenne.org/freesoft.htm). To those using the Windows 95 version to do 2^N+1 factoring, you should download a new version. A bug was fixed: stopping a 2^N+1 ECM run incorrectly updated the worktodo.ini file, upon restart the program would start 2^N-1 ECM runs. The source code has also been updated (http://www.mersenne.org/source.htm). Best regards, George
Mersenne: Another distributed project
Thought that this might interest you all. -- Visit my new and improved home page at http://www.fireantproductions.com/cannona -- Forwarded message -- Date: Wed, 4 Nov 1998 11:23:51 -0800 (PST) From: "SETI@home" [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: SETI@home Project Update Dear SETI@home volunteer: Thank you for signing up for SETI@home. We're on schedule to distribute the SETI@home screensaver program in April 1999, and we'll send you another email when that happens. On October 30 we began recording data at the world's largest radio telescope, located in Arecibo, Puerto Rico. Preliminary versions of the screensaver program and the data distribution system have been completed. On November 20 we will begin testing the system with a group of 100 users analyzing real data (sorry - no more volunteers needed). Over the next few months we will complete the testing, making sure the system will handle large numbers of users. We are pleased to thank SETI@home's sponsors and technology partners: the Planetary Society (a 100,000 member organization founded by Carl Sagan), Paramount Studios (in conjunction with their new movie, Star Trek IX: Insurrection), Sun Microsystems, EDT, Fuji Film Computer Products, Informix, and individual donors like you. The screen saver will be free for everyone, but if you can consider making a tax-deductible donation to SETI@home, please visit http://setiathome.ssl.berkeley.edu/donor.html. We also invite you to become a member of The Planetary Society. You can visit their site at http://www.planetary.org. For further SETI@home information and news, please see http://setiathome.ssl.berkeley.edu. Thank you again for offering to participate in SETI@home. Our work is enhanced and inspired by the enthusiasm of thoughtful, adventurous, and generous people like you. If you wish to remove your name from the SETI@home email list, please send an empty email message to this address with subject header "remove". Best wishes, The SETI@home project
Re: Celestial bodies (was RE: Mersenne: Re: Is 128 bit instruction code needed ?)
Aaron Blosser wrote: Over billions of years, wouldn't most free-floating dust have been attracted to some heavy object by now? I know there are still a lot of large bodies such as comets, meteorites, asteroids (though I doubt the existence of the hypothetical "Oort Cloud"). I don't know, it just seems that after so much time, most small bodies, especially dust and what not, would have accumulated into larger objects, just as the stars and planets did. Certainly none of it would still be in little pieces, hurtling around aimlessly, orbiting each other wihtout actually accumulating enough to start fusion reactions. Orbits decay, you know. It's a wonder Earth hadn't fallen into the sun by now. __ David Nicol 816.235.1187 UMKC Network Operations [EMAIL PROTECTED] download IE4 for Linux from ftp.microsoft.com
Mersenne: A TEST
Hi.
