Mersenne Digest Tuesday, July 18 2000 Volume 01 : Number 759 ---------------------------------------------------------------------- Date: Sun, 16 Jul 2000 12:46:03 +0200 From: Martijn <[EMAIL PROTECTED]> Subject: Mersenne: Algorithm improvements? Hello, Maybe a smaller fft size can be used, anyone noticed that (((n^2 - 2) mod m )^2 - 2) mod m is the same as ((((n^2 - 2) mod m) - m )^2 - 2) mod m. This means that it is possible to take the smallest number of ((n^2 - 2) mod m) and |((n^2 -2 ) mod m) - m| in lucas lemer testing, which will lead to smaller numbers to square. Furthermore, one could save the value of for instance the 10 000th iteration, and check if a later iteration gets the same value, if it does, one knows that the value will never get to 0 anymore. If the value 2 keeps repeating one knows that one iteration had as result a 0, the value will always remain 2 after that. (unless 0 < m < 4) Kind Regards, Martijn - -- http://jkf.penguinpowered.com Linux distributies voor maar Fl 10 per CD, inclusief verzendkosten! _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 16 Jul 2000 12:50:03 +0100 From: "Michael Bell" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Algorithm improvements? Hi, > > Furthermore, one could save the value of for instance the 10 000th > iteration, and check if a later iteration gets the same value, > if it does, one knows that the value will never get to 0 anymore. This has been discussed - I seem to remember that the conclusion was that because the chance of it happening is negligible, it's not worth the computing time to check, or the memory to store the value of the sequence at particular intervals. This is discussed in the FAQ (Question 2.3) > If the value 2 keeps repeating one knows that one iteration had as > result a 0, the value will always remain 2 after that. (unless 0 < m < > 4) > I don't know if it is possible for this to happen before the p-1'th iteration (I don't think it is). If it is then I assume it is already checked for. I'm not sure about you're first idea - I think it may suffer from the problem of increasing the time of each iteration, therefore even though it saves a bit of speed on each iteration it might not cause an overall speed up. Michael Bell. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 16 Jul 2000 23:42:36 +0800 From: "Dave Mullen" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Algorithm improvements? This is a multi-part message in MIME format. - ------=_NextPart_000_0032_01BFEF7F.857B5240 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I remember looking at this myself a while back - is this what you meant = ? For a given modulus e.g. M(7) =3D 127, ignoring the -2 for a while ... 1 ^ 2 =3D 1 (mod 127) 2 ^ 2 =3D 4 (mod 127) ... 63 ^ 2 =3D 32 (mod 127) and then the results are the same but in reverse order i.e. 64 ^ 2 =3D 32 (mod 127) ... 125 ^ 2 =3D 4 (mod 127) 126 ^ 2 =3D 1 (mod 127) So effectively, if the MSB of whatever bit length of the exponent you = are testing is 1, you could invert the current value before doing the = FFT and get the same answer. But that only saves one bit of calculation, which I don't think makes = any difference when the FFT length is rounded up to a power of 2 anyway. = So the overhead of inverting the current value only adds to the time = taken for an iteration. With regard to storing arbitrary iteration results and comparing with = the current value to detect "loops" - how much time would comparing = these numbers take - with my limited number theory, I understood that = unless you were lucky and happened to have a prime factor in your test = value with a low periodicity, you are very unlikely to hit one of these = "loops" anyway.=20 I think the next true breakthrough on LL testing will only come when = someone finds how to do an FFT or other transform without the need to = "spread" the 2^N-1 values into a 2^N FFT space (my terminology might be = bad, I hope you know what I mean) - and avoid the floating point = inaccuracies (and the subsequent required error checking) - anyone done = any more reseach on the NTT or similar integer transforms ? I did have a "play" with NTTs, in an attempt to try and do more that one = iteration per forward and reverse transform, but found the difficulty is = finding a big enough prime with suitable roots to cope with the = magnitude of numbers ^2, never mind ^4 ! Dave - ------=_NextPart_000_0032_01BFEF7F.857B5240 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.2614.3500" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV><FONT face=3DArial size=3D2>I remember looking at this myself a = while back - is=20 this what you meant ?</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>For a given modulus e.g. M(7) =3D 127, = ignoring the=20 - -2 for a while ...</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>1 ^ 2 =3D 1 (mod 127)</FONT></DIV> <DIV><FONT face=3DArial size=3D2>2 ^ 2 =3D 4 (mod 127)</FONT></DIV> <DIV><FONT face=3DArial size=3D2>...</FONT></DIV> <DIV><FONT face=3DArial size=3D2>63 ^ 2 =3D 32 (mod 127)</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>and then the results are the same but = in reverse=20 order i.e.</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>64 ^ 2 =3D 32 (mod 127)</FONT></DIV> <DIV><FONT face=3DArial size=3D2>...</FONT></DIV> <DIV><FONT face=3DArial size=3D2>125 ^ 2 =3D 4 (mod 127)</FONT></DIV> <DIV><FONT face=3DArial size=3D2>126 ^ 2 =3D 1 (mod 127)</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>So effectively, if the MSB of whatever = bit length=20 of the exponent you are testing is 1, you could invert the current = value=20 before doing the FFT and get the same answer.</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>But that only saves one bit of = calculation, which I=20 don't think makes any difference when the FFT length is rounded up to a = power of=20 2 anyway. So the overhead of inverting the current value only adds = to the=20 time taken for an iteration.</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>With regard to storing arbitrary = iteration results=20 and comparing with the current value to detect "loops" - how much time = would=20 comparing these numbers take - with my limited number theory, I = understood=20 that unless you were lucky and happened to have a prime factor = in your=20 test value with a low periodicity, you are very unlikely to hit one of=20 these "loops" anyway. </FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>I think the next true breakthrough = on LL=20 testing will only come when someone finds how to do an FFT or other = transform=20 without the need to "spread" the 2^N-1 values into a 2^N FFT space (my=20 terminology might be bad, I hope you know what I mean) - and avoid the = floating=20 point inaccuracies (and the subsequent required error checking) - anyone = done=20 any more reseach on the NTT or similar integer transforms ?</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>I did have a "play" with NTTs, in an = attempt to try=20 and do more that one iteration per forward and reverse transform, but = found the=20 difficulty is finding a big enough prime with suitable roots to cope = with the=20 magnitude of numbers ^2, never mind ^4 !</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>Dave</FONT></DIV> <DIV> </DIV> <DIV> </DIV></BODY></HTML> - ------=_NextPart_000_0032_01BFEF7F.857B5240-- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 16 Jul 2000 17:23:22 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Algorithm improvements? On Sun, Jul 16, 2000 at 12:46:03PM +0200, Martijn wrote: >Furthermore, one could save the value of for instance the 10 000th >iteration, and check if a later iteration gets the same value, >if it does, one knows that the value will never get to 0 anymore. This is quite unlikely to happen, as there are so many possible values to choose from! Think 2^(1024^2) (approx.) for a 1024kB FFT -- as you are only doing a couple of million iterations, the chance of getting a `loop' quickly becomes extremely slim, and it really isn't worth checking for. /* 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: Sun, 16 Jul 2000 15:40:29 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: the Mersenne Faq has moved The FAQ of the mersenne mailing list has moved to http://www.exu.ilstu.edu/mersenne/faq-mers (or faq-mers.txt). The old adress will continue to work until the 18th. Sorry for the trouble, Lucas P.S. Luke, could you please tell Gordini to change the line at the end of each message. Again, sorry for the trouble. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 16 Jul 2000 17:36:14 -0400 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Algorithm improvements? "Steinar H. Gunderson" wrote: > > On Sun, Jul 16, 2000 at 12:46:03PM +0200, Martijn wrote: > >Furthermore, one could save the value of for instance the 10 000th > >iteration, and check if a later iteration gets the same value, > >if it does, one knows that the value will never get to 0 anymore. > > This is quite unlikely to happen, as there are so many possible values > to choose from! Think 2^(1024^2) (approx.) for a 1024kB FFT -- as you > are only doing a couple of million iterations, the chance of getting a > `loop' quickly becomes extremely slim, and it really isn't worth checking > for. > > /* Steinar */ It might also be noted that in order to be sure that the value is being repeated, the entire term in the LL sequence would have to be saved (or matches would have to be found in, say, 20 consequative residues). Even saving every residue for a 10 M range exponent would take 21 megabytes of hard drive space, all of which would have to be searched every time you checked for repeats! Nathan > -- > 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 _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Sun, 16 Jul 2000 23:22:15 +0100 From: "Michael Bell" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Algorithm improvements? > "Steinar H. Gunderson" wrote: > > > > On Sun, Jul 16, 2000 at 12:46:03PM +0200, Martijn wrote: > > >Furthermore, one could save the value of for instance the 10 000th > > >iteration, and check if a later iteration gets the same value, > > >if it does, one knows that the value will never get to 0 anymore. > > > > This is quite unlikely to happen, as there are so many possible values > > to choose from! Think 2^(1024^2) (approx.) for a 1024kB FFT -- as you > > are only doing a couple of million iterations, the chance of getting a > > `loop' quickly becomes extremely slim, and it really isn't worth checking > > for. > > > > /* Steinar */ > > It might also be noted that in order to be sure that the value is being > repeated, the entire term in the LL sequence would have to be saved (or > matches would have to be found in, say, 20 consequative residues). > > Even saving every residue for a 10 M range exponent would take 21 > megabytes of hard drive space, all of which would have to be searched > every time you checked for repeats! > > Nathan I think the suggestion was that only every 10,000th residue (or so) was actually saved (it is not necessary to save every residue because what you are looking for is a repeating loop - if the same value occurs twice, then it causes a loop.) You could take the bottom 32K or something instead of just 64 bytes, and lets say you took 10 consecutive ones each 100,000 iterations. by the end of an exponent in the 10M range you would have 320K*100=32M, though you would only have to hold 3.2M in memory, and check this much *each iteration*. However, you have about 1 in 2^10000000 chance of getting a match on any given iteration, overall you have a 10000000 in 2^10000000, or 1 in 2^9999975 (approx) chance. So if we are exceedingly lucky one exponent in the range might match, but the chances are incredibly tiny, so however little time it takes is almost certainly wasted. Michael. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Mon, 17 Jul 2000 10:13:35 +0200 (CEST) From: Henrik Olsen <[EMAIL PROTECTED]> Subject: Re: Mersenne: Algorithm improvements? On Sun, 16 Jul 2000, Dave Mullen wrote: > I think the next true breakthrough on LL testing will only come when > someone finds how to do an FFT or other transform without the need to > "spread" the 2^N-1 values into a 2^N FFT space (my terminology might > be bad, I hope you know what I mean) - and avoid the floating point > inaccuracies (and the subsequent required error checking) - anyone > done any more reseach on the NTT or similar integer transforms ? Already being used in mprime/prime95, with Crandall's algorithm the convolution is tightly packed and the modulus is given for free. Also, a floating point algorithm is used because modern processors does more bits accurately in the same time with floats than with integers, even if you have to throw some bits away with floats. As a result integer algorithms are slower on current hardware, so is used mainly to validate the floating point algorithm implemementations. > I did have a "play" with NTTs, in an attempt to try and do more that > one iteration per forward and reverse transform, but found the > difficulty is finding a big enough prime with suitable roots to cope > with the magnitude of numbers ^2, never mind ^4 ! > > Dave - -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Linux isn't at war. War involves large numbers of people making losing decisions that harm each other in a vain attempt to lose last. Linux is about winning. Alan Cox on linux-kernel _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Mon, 17 Jul 2000 09:28:32 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Algorithm improvements? I think most of this has been covered before, but a few comments may be in order. 1) There are other residual values worth checking for as well as 0. In fact detection of any closed loop is useful information because it enables us to "write down" the residual at _any_ subsequent iteration without the bother of actually doing the calculation. 2) You do _not_ need to store the whole residual every time. If you store only the bottom 64 bits you will get about one spurious match every 2^64 iterations ... but we're doing far fewer than that number of iterations. Only on the rare occasions when we do get a match is it worth looking at the whole residual; the best method of doing this (given that we now know where the cycle starts, so we need to keep only that value) is to repeat the calculation from the start, or nearest previous checkpoint file, if one is available. (InterimFiles!) 3) Since the Lucas-Lehmer algorithm is a suitable function, if we _do_ happen to detect a looping value of the residual, a proper factor can be extracted by Pollard's rho method. 4) Existence of a residual loop within the first p-2 iterations is most unlikely. If we want to use Pollard's rho method to find factors of 2^p-1, we would be much better advised to use a formula of the type x(n+1) = (x(n))^(4*p)+a rather than the Lucas sequence; since this type of formula selects for factors of type 2kp+1, the extra work per iteration would be worthwhile. 5) Note that, statistically, there are "about" 2 values x such that x^2-2 = a (mod 2^p-1) for an arbitary a. In general, then we would "expect" to have to execute "about" p iterations before hitting a recurrence, rather than the maximum possible cycle length of 2^p-1. This statement seems to be opposed to the point above, I don't know the reason! (Probably something to do with a large number of values (a+2) which are quadratic non-residues modulo 2^p-1 ?) 6) Another possible line of approach related to the suggestion is as follows. Does there exist an x such that x^2 - 2 = 0 (mod 2^p -1), i.e. is 2 a quadratic residue residue modulo 2^p-1? If not, then the (p-2)th term in the L-L sequence cannot possibly be zero, so there's no point in executing the L-L test. Unfortunately, since 2^p-1 = -1 (mod 8) for all odd primes p, it follows that 2 is a quadratic residue modulo 2^p-1 for all odd primes p. Hence the observation is useless. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Mon, 17 Jul 2000 06:59:35 -0700 From: Stefan Struiker <[EMAIL PROTECTED]> Subject: Mersenne: Overclocking, RAMBUS And Special Relativity Good Monday Morning! Wound up the weekend with a very special (relativistic?) phenomenon. Finishing up a factoring assignment, about 88% through the 65-bit stretch, I had reason to shut down W98 all the way to power off. Up came the system again at 92% complete, not 88%. Another orderly shut-down at 94% and back it came at 97% and finished. Began the next assignment and found a factor. Picked up the next victim... The machine has mucho RDRAM cranked to 438MHz, and a PIII overclocked from 866 to 950. But time-travel? Now _that_ would be a RAMBUS plus! Input? Best Wishes, Stefan "Lorentz Contraction" Stefanovic _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Mon, 17 Jul 2000 07:58:19 -0700 From: Stefan Struiker <[EMAIL PROTECTED]> Subject: Mersenne: Follow-Up To "Overclocking, RAMBUS..." Meanwhile, back at 866 MHz and the Auto RAMBUS setting of 400 MHz, the "improvement" and time-travel vanished. Overclocking can be a Very Bad Thing, sneaking past the OS and other checks and balances to give --- The Wrong Answer. Ouch. Stefanovic _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Tue, 18 Jul 2000 12:50:13 -0500 From: "Griffith, Shaun" <[EMAIL PROTECTED]> Subject: RE: Mersenne: distributing the $$$ [EMAIL PROTECTED] wrote: > Check out > > http://www.cnn.com/2000/TECH/computing/07/07/seti.implication.idg/index.html > > - -Ernst Wired 8.08 has a long feature story similar to this, but it's not on the web yet (the magazine is still on newstands). - -Shaun _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ End of Mersenne Digest V1 #759 ******************************
