mersenneforum.org Computer and the Math
 Register FAQ Search Today's Posts Mark Forums Read

 2003-11-29, 17:16 #1 Quacky   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
 2003-11-29, 17:58 #2 ET_ Banned     "Luigi" Aug 2002 Team Italia 2·29·83 Posts 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 Last fiddled with by ET_ on 2003-11-29 at 18:00
 2003-11-29, 18:11 #3 dsouza123     Sep 2002 2·331 Posts 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
 2003-11-29, 19:00 #4 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 52·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^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. Last fiddled with by patrik on 2003-11-29 at 19:06
 2003-11-30, 08:14 #5 HiddenWarrior     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^p-1. Every iteration can have various length!
 2003-11-30, 12:10 #6 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 52×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^33489583-1 = 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% 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.
 2003-12-01, 07:58 #7 HiddenWarrior     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^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 :))
 2003-12-02, 03:54 #8 Quacky   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 2003-12-02 at 03:55
 2003-12-02, 07:19 #9 Unregistered   874610 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.
 2003-12-02, 21:17 #10 dsouza123     Sep 2002 2·331 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Aramis Wyler Math 40 2014-12-18 11:15 swl551 Math 2 2014-02-20 16:33 ET_ Operazione Doppi Mersennes 4 2012-09-20 19:33 DSC Miscellaneous Math 2 2005-09-11 04:53 DSC Homework Help 13 2005-08-31 07:16

All times are UTC. The time now is 21:29.

Tue May 18 21:29:48 UTC 2021 up 40 days, 16:10, 0 users, load averages: 2.02, 2.18, 2.27