mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Closed Thread
 
Thread Tools
Old 2003-11-29, 17:16   #1
Quacky
 
Sep 2002

2×5 Posts
Default 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
Quacky is offline  
Old 2003-11-29, 17:58   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

113028 Posts
Default

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
ET_ is offline  
Old 2003-11-29, 18:11   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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
dsouza123 is offline  
Old 2003-11-29, 19:00   #4
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

52×17 Posts
Default

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
patrik is offline  
Old 2003-11-30, 08:14   #5
HiddenWarrior
 
HiddenWarrior's Avatar
 
Jun 2003
Russia, Novosibirsk

2×107 Posts
Default

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!
HiddenWarrior is offline  
Old 2003-11-30, 12:10   #6
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

52·17 Posts
Default

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.
patrik is offline  
Old 2003-12-01, 07:58   #7
HiddenWarrior
 
HiddenWarrior's Avatar
 
Jun 2003
Russia, Novosibirsk

21410 Posts
Default

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 :))
HiddenWarrior is offline  
Old 2003-12-02, 03:54   #8
Quacky
 
Sep 2002

2·5 Posts
Default

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
Quacky is offline  
Old 2003-12-02, 07:19   #9
Unregistered
 

3×23×59 Posts
Default

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.
 
Old 2003-12-02, 21:17   #10
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

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.
dsouza123 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I am so sorry for being bad at math. Aramis Wyler Math 40 2014-12-18 11:15
need some math help. swl551 Math 2 2014-02-20 16:33
Math ET_ Operazione Doppi Mersennes 4 2012-09-20 19:33
math help pls! DSC Miscellaneous Math 2 2005-09-11 04:53
help with math DSC Homework Help 13 2005-08-31 07:16

All times are UTC. The time now is 00:07.

Wed Mar 3 00:07:57 UTC 2021 up 89 days, 20:19, 0 users, load averages: 3.06, 2.88, 2.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.