Computer and the Math

[Quacky]

After reading over the board here thoroughly I have realized that learning the math to all this is just something your not going to be able to do without much study and a certain propensity for it.(which I do not )
With that said I do have some questions that I will probally be capable of understanding.
I am currently working on M33489583. I am 87% done! (My 4th 10,000,000 number.
I run a Barton 2500+ at 2.0ghz and it takes .192 seconds to do an iteration. Now in microcpu terms, .192 seconds is an eternity...my question is can anyone explain exactly what the cpu is doing during that iteration? Is it doing math like this? Ex: 29430000 is current iteration. So it goes 2^29430000 -1 for 1 iteration, 2^29430001 -1 for the next, 2^29530002 -1 and so on.
Am I correct in assuming this? If that is the case then how do the answers to each iteration tell us if the number is prime or not?
Also if you could, try to explain what the cpu is doing in stages 1 and 2. I am mainly concentrating on the iterations because that is the bulk of the work.
Thank you for any help you provide and I will clarify anything that doesnt make sense

[ET_]

From mersenne.org math page:
(http://www.mersenne.org/math.htm)

"The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2^P-1 is prime if and only if S(p-2) is zero in this sequence: S0 = 4, SN = (S(N-1)^2 - 2) mod (2^P-1)."

First iteration starts at S0 = 4, then calculate S1 as a function of S(0), then goes on to S(2) as a function of S(1) and steps on until S(P-2) is reached.

Each iteration squares the number of previous iteration, subtracts 2 and checks the result with a mod operation that gives the remainder of the division with the number to check.

As we are working with numbers having millions of digits, each step must be divided into simpler substeps (computer words have generally 32 or 64 bits).

Here's the reason of your .192 secs iterations: each substep takes few milliseconds, but the whole operation involved in one iteration takes more.

As for stage 1 and stage 2, I guess they relate to a previous operation which tries to find out small factors of the number before starting LL-test: if a factor is found, then the number is divisible and not prime, and a LL-test is not needed.

Luigi

[dsouza123]

My understanding of the math is

For each iteration in lucas-lehmer ( LL ), except the first, it does the equivalent of

take the result of the previous iteration
square it
subtract 2
mod it by the mersenne ( mod is the remainder after integer division )

It is really doing DWT, a optimized/specialized FFT routine that because of some property does the equivalent of the square without needing a mod.


From the help file

The Lucas-Lehmer primality test is remarkably simple. For example, to prove 2^7 - 1 is prime:

S (0) = 4
S (1) = 4 * 4 - 2 mod 127 = 14
S (2) = 14 * 14 - 2 mod 127 = 67
S (3) = 67 * 67 - 2 mod 127 = 42
S (4) = 42 * 42 - 2 mod 127 = 111
S (5) = 111 * 111 - 2 mod 127 = 0

The exception was the start where 4 is used to start it going.
With the final iteration result being 0, it is prime.
With the exponent 7, it does 7 - 1 iterations.
2^7 - 1 = 128 - 1 = 127

[patrik]

Just to be clear: There is a theorem that says this. It is noting one can just "see" (at least not I).

Specializing to your number M33489583 the theorem says:
Start with 4.
Repeat 33489581 times:
Square, subtract 2 and take remainder after dividing by 2^33489583-1.

If the final remainder is zero, 2^33489583-1 is prime, (and if it is not zero your number is composite).

The number 2^33489583-1 has got 10081370 digits. The fastest way to multiply numbers this large is to use a Fast Fourier Transform (FFT). Prime95 does this. (Since you take the remainder after division by 2^33489583-1, the remainder also has 10081370 digits, except for the first few iterations.)

The P-1 stage 1 and 2 is trying to find small factors before the Lucas-Lehmer test starts. The amount of time it spends on factoring is adjusted to maximize the throughput of the Mersenne search.

[HiddenWarrior]

Patrik! I'm not quite sure that only first few iterations give the result of mod the length smaller than the 2^p-1.
Every iteration can have various length!

[patrik]

Well maybe not exactly 10081370 digits, but I'm treating the residue as a random number. Is it wrong to do that? Then I get (to the precision of my calculator)

2^33489583-1 = 10^10081369.03 = 1.07 x 10^10081369

significant      expected
digits in        fraction
residue          of residues

10081370         0.07 / 1.07 =  6.5%
10081369         0.90 / 1.07 = 84.1%
10081368         0.09 / 1.07 =  8.4%
10081367         0.009/ 1.07 =  0.8%
10081366 or less 0.001/ 1.07 =  0.1%

So the probability of having fewer than say 10081355 significant digits in the residue during any time (except the beginning) of the LL test would be very small.

[HiddenWarrior]

Ok, I'll done some calculations and will put some result this week. I think that resudue can vary from length of 1 to (2^p-1 digits length)... Maybe except the resudes of 1 and 2... As we know we can get an zero resudue in the finish to get a Mersenne!

But if we on a step will get a resudue of 1 or 2 then we can 100% say that on all next steps we'll get the same resudes as:

1*1-2 mod *=1 (i mod is >1)
2*2-2 mod * = 2 (if * is >2)

Even more: if on X step we'll get an resude Y and on Z step we get the same resude Y than on every step X*K=Z*K (K is integer) we'll get the resudue Y. So we can greatly minimize the numbers of iterations... But if we'll thing about comparison of current resudue with previous ones we'll come to great calculations => not very good way for us :))

[Quacky]

Wouldnt 10 million digits take up 10 megabytes of space? So if your computer is doing LL tests would not the minimum ram needed be 10 megs? If so I could see how having a fast FSB and good ram would really help Prime95.



Also, if each iteration can be a different length like we are discussing atm,why is each iteration time the same?. Times are the same .192 since the beginning up to now, 90% done.


Interesting info at the least...thanks a lot

Partially because those values (0.192) are generally (default) an average over around 1000 iterations, which would smooth it out a lot. Try setting it to average over one and then see... only not for too long because output could than become a bottleneck.

[dsouza123]

2^33489583-1 would take 4186198 bytes or 4088 KB or 3.992 MB to store as a binary integer.

Exactly what is stored while doing the DWT, I am not sure, but I don't think it is the Mersenne number because the DWT doesn't do a mod by the Mersenne at the end of each calculation, like an straight forward unoptimized algorithm would.