Mersenne: Basic question: Working modulo 2^n-1
Chris Caldwell's web page on Mersenne numbers descirbes the Lucas-Lehmer test briefly and mentions that it is quick on binary computers because they can quickly perform division by 2^n-1. I know how to find integer quotients and remainders modulo 2^n with shifting and masking, but I don't understand how it is done quickly modulo 2^n-1. Would anyone care to explain? __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: mprime for QA or performance?
Hi, At 12:24 AM 1/13/99 -0800, Leu Enterprises Unlimited wrote: On one CPU, after two days worth of burn-in, the time required to complete 100 iterations on the stock number went down, as I would expect. On a second CPU, the time actually *increased*. From 1 day, 18 hours, and 55 minutes, to 1d 19h 13m! I'd be surprised if burning in had an effect on iteration times. More likely, 100 iterations is not enough to get a truly accurate timing. I don't know about Linux, but it has been noted before prime95 iteration times can vary a few percent from day to day. If anyone knowledgeable would care to comment about mprime's suitability for Q.A. mprime is great for QA. It generates heat (by FPU use) and tons of memory accesses. If there are any hardware problems there, they are likely to show up in an extended torture test. and/or performance measurements, I'd guess its as good as but no better than any of hundreds of publicly available benchmarks. Best regards, George
Re: Mersenne: Basic question: Working modulo 2^n-1
On Fri, 15 Jan 1999, Foghorn Leghorn wrote: Chris Caldwell's web page on Mersenne numbers descirbes the Lucas-Lehmer test briefly and mentions that it is quick on binary computers because they can quickly perform division by 2^n-1. I know how to find integer quotients and remainders modulo 2^n with shifting and masking, but I don't understand how it is done quickly modulo 2^n-1. Would anyone care to explain? The remark was indended to refer to the classical algorithms (with the right choice of FFT algorithm this step is automatic): the key is that 2^n = 1 (mod 2^n-1), so if we write the number as A*2^n + B (that is, let B be the last n bits and A the rest, then A*2^n+B = A+B (mod 2^n-1). So we can reduce with just an addition. For exampe, take the number 23 modulo 7, 23 is (mod 7) 10111 = 10 + 111 = 1001 = 1 + 001 = 10 (mod 111) Chris.
Re: Mersenne: Let's recruit her for GIMPS
On Fri, 15 Jan 1999, Ernst W. Mayer wrote: The following article, titled "Irish teen's e-mail code could transform Internet commerce" should be of interest: http://www.cnn.com/TECH/computing/9901/14/email.genius/ Pretty impressive work for a person of any age, much less a 16-year-old. We should see if we can recruit her for the GIMPS effort. -Ernst I checked that article, it has no mention of her algorithm, no mention of the strength of the algorithm, no mention of whether the judges where competent to evaluate the strength of the algorithm and a very scary quote foretelling the future of her work. quote She said that she would prefer to publish her discovery rather than patent it, because making money from it would go against the spirit of science. /quote With the way the US patent law works, that will put it up for grabs to whoever gets the application done first, thus enabling them to prevent any unlicenced use by others, including the discoverer. She's showing her age with that comment:( -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Get the rest there.
Re: Mersenne: mprime for QA or performance?
On Fri, 15 Jan 1999, George Woltman wrote: At 12:24 AM 1/13/99 -0800, Leu Enterprises Unlimited wrote: On one CPU, after two days worth of burn-in, the time required to complete 100 iterations on the stock number went down, as I would expect. On a second CPU, the time actually *increased*. From 1 day, 18 hours, and 55 minutes, to 1d 19h 13m! I'd be surprised if burning in had an effect on iteration times. More likely, 100 iterations is not enough to get a truly accurate timing. I'd be extremely surprised, since the speed of the computations is strongly linked to the processor clock, so either you're measuring clock drift (and yes, that is temperature linked) or due to your small samples the variance mentioned which is about 1% is actually noice. -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Get the rest there.
