20031129, 17:16  #1 
Sep 2002
2·5 Posts 
Computer and the Math
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 
20031129, 17:58  #2 
Banned
"Luigi"
Aug 2002
Team Italia
2·29·83 Posts 
From mersenne.org math page:
(http://www.mersenne.org/math.htm) "The LucasLehmer primality test is remarkably simple. It states that for P > 2, 2^P1 is prime if and only if S(p2) is zero in this sequence: S0 = 4, SN = (S(N1)^2  2) mod (2^P1)." 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(P2) 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 LLtest: if a factor is found, then the number is divisible and not prime, and a LLtest is not needed. Luigi Last fiddled with by ET_ on 20031129 at 18:00 
20031129, 18:11  #3 
Sep 2002
2·331 Posts 
My understanding of the math is
For each iteration in lucaslehmer ( 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 LucasLehmer 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 
20031129, 19:00  #4 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
5^{2}·17 Posts 
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^334895831. If the final remainder is zero, 2^334895831 is prime, (and if it is not zero your number is composite). The number 2^334895831 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^334895831, the remainder also has 10081370 digits, except for the first few iterations.) The P1 stage 1 and 2 is trying to find small factors before the LucasLehmer test starts. The amount of time it spends on factoring is adjusted to maximize the throughput of the Mersenne search. Last fiddled with by patrik on 20031129 at 19:06 
20031130, 08:14  #5 
Jun 2003
Russia, Novosibirsk
2×107 Posts 
Patrik! I'm not quite sure that only first few iterations give the result of mod the length smaller than the 2^p1.
Every iteration can have various length! 
20031130, 12:10  #6 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
5^{2}×17 Posts 
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^334895831 = 10^10081369.03 = 1.07 x 10^10081369 Code:
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% 
20031201, 07:58  #7 
Jun 2003
Russia, Novosibirsk
2×107 Posts 
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^p1 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*12 mod *=1 (i mod is >1) 2*22 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 :)) 
20031202, 03:54  #8 
Sep 2002
2×5 Posts 
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 Last fiddled with by Quacky on 20031202 at 03:55 
20031202, 07:19  #9 
8746_{10} Posts 
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.

20031202, 21:17  #10 
Sep 2002
2·331 Posts 
2^334895831 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I am so sorry for being bad at math.  Aramis Wyler  Math  40  20141218 11:15 
need some math help.  swl551  Math  2  20140220 16:33 
Math  ET_  Operazione Doppi Mersennes  4  20120920 19:33 
math help pls!  DSC  Miscellaneous Math  2  20050911 04:53 
help with math  DSC  Homework Help  13  20050831 07:16 