> "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
