Re: Learning from Eratosthenes
On Mon, Oct 16, 2000 at 07:14:31AM -0700, Jonathan Walther wrote:
> If you think about it, you realize that if you have knocked out all
> multiples of the primes less than i, then all numbers left standing
> less than i^2 are prime. try with pen and pencil; I figured this one
> out in high school. its a common optimization. its also what lets
> you stop as soon as you hit the sqrt() of the highest number you want to
> check.
Things can get a great deal faster.
First off, for any squarefree modulus n, determine all 0 < k < n
with (n,k) = 1 and you can knock out 1-phi(n)/n of the candidates all
at once. Choosing n = 2 (as most people do) is not optimal. Try n = 30.
Second, if p | 30 m + k then p | 30 (m+pr) + k, so the same sort of
sieving procedure can be done, that is, once you've found a prime
divisor of a candidate 30 m + k you can cross off every pth entry
congruent to k mod 30.
Third, you can use a bit array for the placeholders for each candidate,
as all we need are "yes" or "no" answers for each. Each octet represents
(rather conveniently) one choice of m, and all the possible residue
classes mod 30 are bit fields in the octet (because phi(30) = 8).
Fourth, bootstrap the sieve with a small table of known primes, perhaps
the first 1024 or so; they can be located rapidly in the table by
computing their residue classes mod 30 (or whatever modulus you choose
to use).
Fifth, if you're on a parallel computer, you might try doing your evil
business to the various distinct residue classes mod 30 (or whatever
your modulus is) in parallel, as they do not interact (much, anyway).
This might require extra space for separating out the different
candidates' flags enough that loads and stores won't interact, or
perhaps less extra space for locking (but locking loses most of the
parallelism of all this). If you've got the money for a machine that
can actually use this, you probably have enough memory for it.
Sixth, if you're sieving some random interval out in la la land, you
won't be trying to get all the primes up to sqrt(10^100), instead you
knock out bad candidates first with a pass of gcd with a product of the
first 1024 primes or however many fit into a machine word or whatever,
then try a probabilistic primality test with a few rounds (Rabin-Miller
anyone?) to knock out a few more, and then do some deterministic tests
on the rest (Lucas-Lehmer?).
Just my thoughts on the subject,
Bill
--
<coolG:#math> there is at least one prime between 31337 and 2*31337
--
Reply to: