Prime number module

[Stephen Horne]

On Wed, 01 Oct 2003 19:53:04 GMT, "Andrew Dalke"
<adalke at mindspring.com> wrote:

>You could also get better compression testing for %5, %7, %11, etc.

That was the point of the modulo 2*3*5 == 30 and modulo 2*3*5*7 ==
210. As I said, working with the pattern needs a rapidly increasing
modulo size and lookup table, and the advantages rapidly diminish as
you add more and more primes.

>Note that by doing so you convert your lookup system into a simple
>prime tester, and if you extend it along 2, 3, 5, ... then it is the seive
>of Eratosthenes and you don't need to store any bit patterns at all.

No, you don't need the bitset - but the whole thing becomes a waste of
time and space. If you extend it sufficiently to not need any bit
patterns at all, what you do need is a huge modulo-based lookup table
that serves no real purpose at all (it only has benefits for the
second and so-on repetitions of the repeating pattern) and a complete
list of the 'special case' primes (ie all primes up to 10^8).

Storing the list of special primes up to 10^8 would take much more
space than the original bitset, and the lookup table would take even
more space. The whole exercise would be far worse than pointless as
you could get more efficient results by discarding the method and the
lookup table, and just searching that list of 'special case' primes.

Optimisation problems often require a balance. In this case, I was
trying to balance prior knowledge of the repeating pattern of definite
non-primes in the program with externally stored data for the bulk of
the primes (the bitset on disk).


-- 
Steve Horne

steve at ninereeds dot fsnet dot co dot uk