> When you square S over and over and over in one LL test, does that same
> value of S come up in a test for another exponent?
Well, the first few values are the same ... until the remaindering
kicks in. And we know that S(n) = 2 for all terms >= n, if 2^n-1
happens to be prime (since S(n-2) = 0).
> Is there a pattern
> of S values that can help us shorten the LL test?
Find one & tell us about it ;-)
> If there is a
> pattern, and it can be used to calculate a certain S value for some
> other (untested?) exponent at some given iteration, then it could cut
> weeks off of testing exponents
Indeed.
I had a semi-crackpot idea like this, that we know what S(n) is for
n>=p-2 if 2^p-1 happens to be prime. So, searching for larger
exponents, if we can find a set of (smaller) p(i) such that the sum
of the p(i)'s is at least equal to the exponent we want to test, then
we should be able to get the residual directly using the Chinese
Remainder Theorem.
Of course, it doesn't work, the modulo operation fouls things up.
The reason I call the idea "semi-crackpot" instead of completely
stupid is that there is _some_ mileage in it. I managed to find a
"new" (well, different) way of doing a LL test, as follows:
Find a set of about 16 p(i) such that the product of the 2^p(i)-1 is
greater than or equal to (2^P-1)^2. The p(i) need to be prime but
2^p(i)-1 doesn't need to be, the fact that the p(i) are all prime
guarantees that the gcd of any pair of the 2^p(i)-1 is 1.
Then we can compute the LL sequence for each of the p(i) by
some normal method. Each time it the next iteration _could_
exceed (2^P-1)^2 (we can work mod 2^p(i)-1 so long as we bear
this in mind), use the CRT to get the residual, reduce it modulo
2^P-1 (easy, just shift & add) then regenerate the residuals for the
p(i)'s from the result.
If you take about 16 p(i), then you will only have to do the CRT
reduction about every 4 iterations ... a big saving on having to do it
every time.
This method can be applied recursively until the 2^p(i)-1's are small
enough to deal with in CPU registers.
Compared with the DWT, this method has some disadvantages
(memory usage is probably one) but some advantages too (no fear
about rounding errors, etc, also suited to systems with no/slow
floating point). The idea _does_ work, but it's not well suited to Intel
processors (not enough named CPU registers, integer multiply is
too slow). Anyone who wants to develop this idea is welcome to do
so ... the "intellectual property" involved in writing efficient code is
huge compared with that in the (rather simple) idea.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
