Mersenne Digest Sunday, 7 March 1999 Volume 01 : Number 522
----------------------------------------------------------------------
From: [EMAIL PROTECTED]
Date: Sun, 7 Mar 1999 06:19:36 +0100 (MET)
Subject: Re: Mersenne: mersennes for our civilization
Spike Jones <[EMAIL PROTECTED]> asks:
> Thanks for the site Dr. Bob! Thats a cool one. Yesterday a coworker
> saw my six page printout of the Great Number on the wall of my office,
> asked, and I explained GIMPS and the LL algorithm, how the program
> checks to see if M(n) divides S(n). He is a clever chap and asked why
> prime95 starts from scratch calculating S(n) instead of getting it from
> a previous check: if you calculated S(6000001) and your needed
> S(6000031) for your next check, for instance, why would you not take
> the previously calced S(6000001) then square and subtract 2 thirty times.
> I pointed at the Great Number and said: Because S(3021377) has this
> many bits. Knock off a dozen digits, and it would take that many years
> just to send the data from one computer to another.
> I felt pretty smart. Then he asked: if S(n) has so many bits, how does a
> desktop computer handle it?
If the printout has 80 characters per line and 60 lines per page,
you'll need 190 pages for 910000 decimal digits. You must have
big pages. Do you use four walls, floor, and ceiling?
When checking whether M(n) divides S(n), the program successively
computes
remainder of S(1) modulo M(n)
remainder of S(2) modulo M(n)
....
remainder of S(n-1) modulo M(n)
remainder of S(n) modulo M(n)
It checks whether the last remainder is zero.
Suppose S(j) = quot(j) * M(n) + rem(j) and
S(j+1) = quot(j+1) * M(n) + rem(j+1), where 0 <= rem(j), rem(j+1) < M(n).
We claim that it is easy to get rem(j+1) from rem(j) without knowing quot(j).
More precisely, if
rem(j)^2 - 2 = q*M(n) + r
with 0 <= r < M(n), then we claim rem(j+1) = r. Indeed
rem(j+1) - r = S(j+1) - quot(j+1)*M(n) - rem(j)^2 + 2 + q*M(n)
= S(j)^2 - rem(j)^2 + (q - quot(j+1))*M(n).
= (quot(j) * M(n) + rem(j)^2 - rem(j))^2
+ (q - quot(j+1))*M(n)
The right side is divisible by M(n) since the rem(j)^2 terms cancel
and all other terms are divisible by M(n). This proves
rem(j+1) - r is a multiple of M(n). The assumptions
0 <= r, rem(j+1) < M(n) imply rem(j+1) - r = 0.
In other words, we can compute
remainder of S(j+1) modulo M(n)
directly from
remainder of S(j) modulo M(n)
We do not need to know S(j) itself for this computation.
Your coworker's proposal calls for computing
remainder of S(6000031) modulo M(6000031)
from
remainder of S(6000001) modulo M(6000001)
If we simply do 30 more iterations, we will have
S(6000031) modulo M(6000001). To change the divisor from
M(6000001) to M(6000031) we know no better method than starting afresh.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: [EMAIL PROTECTED]
Date: Sun, 7 Mar 1999 01:29:34 EST
Subject: Mersenne: Moo?
<<Yesterday a coworker
saw my six page printout of the Great Number on the wall of my office,
asked, and I explained GIMPS and the LL algorithm, how the program
checks to see if M(n) divides S(n). He is a clever chap and asked why
prime95 starts from scratch calculating S(n) instead of getting it from
a previous check: if you calculated S(6000001) and your needed
S(6000031) for your next check, for instance, why would you not take
the previously calced S(6000001) then square and subtract 2 thirty times.
I pointed at the Great Number and said: Because S(3021377) has this
many bits. Knock off a dozen digits, and it would take that many years
just to send the data from one computer to another.
I felt pretty smart. Then he asked: if S(n) has so many bits, how does a
desktop computer handle it?
Me: duuuuuuuh. I dont know. {8-[
Do you know? Can someone explain it to me in words an ordinary
person would understand, how the Prime95 LL algorithm works? spike>>
Wouldn't it be nice... (Beach Boys song). Nah. You see, we use a shortcut. At
every iteration, we only store S(whatever) mod 2^P - 1. It's that mod that
counts. This lets us run Prime95 on machines with 8MB of RAM. However, it
makes what you'd like to do utterly impossible. It would ONLY be possible if
we stored the FULL S(whatever) every cycle, and never took it modulo 2^P - 1.
However, we'd need machines with (insert fantastically large number, perhaps
more than the universe can handle) exabytes of RAM to store the full S for an
exponent around 3 million. And so forth. Aw. :-(
- -*---*-------
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #522
******************************
