Re: greatest multiple algorithm

"Rod Pemberton" <spamtrap@xxxxxxxxxx> writes:
I've tried to write a few trivial (odd) prime number programs over the
years. I'm curious as to how you guys think those two compare to some of
the trivial methods I've tried (esp. Bernstein).

integer array
array stores found primes
modulo with found primes in array to find new primes
slows down rapidly with increasing number of primes in array
consumes large amounts of memory

That doesn't sound like a sieve, it sounds like trial division.
You're not reusing the results of prior computations.
I always advise a sieve.

bit sieve
using single bits to represent odd numbers
finds primes upto memory_in_bytes*8*2
requires no modulo computation
requires many memory accesses
slows down based on size memory used
limited to available memory

You can use a wheel to decrease the memory requirements. Most
fast sieves use the 8 residues mod 30 as their wheel. That
almost halves the memory requirements. Even a wheel of 6 saves
you a third.

See DJB's eratosthenes as part of the primegen package.
James' sieve was a 30 too, IIRC.

brute computation
simple loop
i+=2 for number to test as a factor of the prime
j+=4*(i-1) for the square of i
i.e., to stop when i is roughly sqrt of prime being tested
skip 6k+3
test 6k-1 or 6k+1 modulo with i
fast, no real memory requirements
limited to cpu's largest integer size

Again, that sounds like trial division rather than a sieve.

The brute computation is been the fastest by far, but is obviously limited
to "small" primes.

TOS's (Tomas Oliveira e Silva) GPL-ed C source is acceptably fast,
and very simple. 50% speedup should be possible without too much
work, by introducing the concepts of a mod 6 wheel to either or
both of the small primes and the sieving region.
You won't get much faster without cranking out specifically
optimised inner loops for all the different possibilities.
(Which is what both JvB and TOS have done.)

I'll stop rambling - this has everything you need to know:
http://www.ieeta.pt/~tos/software/prime_sieve.html

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

.

Relevant Pages

  • Re: [OT] gcc: maximum length of an array?
    ... one has to create a boolean array for that. ... of memory to store). ... Not by using the original Sieve of Eratosthenes, ...
    (freebsd-questions)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... modulo with found primes in array to find new primes ... That doesn't sound like a sieve, ... integers upto the largest cpu supported integer type, modulo is faster on ... slower with larger sieve sizes due to the large number of memory accesses. ...
    (comp.lang.asm.x86)
  • Re: [Clax86list] Can WXP handle 4 GB of Physical Memory
    ... determine if huge chunks of memory are able to speed up a sieve ... using L1 cache. ... Since there are about TEN times as many primes between ... sieve checks for primes up to 10**18. ...
    (comp.lang.asm.x86)