Faster way to find primes?

Performance Tuning
#21

Primes are important. Number theory, encryption - that kind of thing.

#22

I need the primes to test a number crunching program I am writing.

I realized that I overlooked the need in my code to restrict factor checks to factors <= sqrt(candidate). so there is a good deal of useless calculation going on - for the millionth prime I am checking hundreds of thousands of unnecessary divisors. Correcting this makes the naive modulus method look somewhat better versus the Erastothenes sieve:

Run 1:

Ags1 v3 Took 2240ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 214ms to find 1000000 primes, highest being 15485863

Run 2:

Ags1 v3 Took 2306ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 224ms to find 1000000 primes, highest being 15485863

Run 3:

Ags1 v3 Took 2306ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 237ms to find 1000000 primes, highest being 15485863

Benchmark code: http://pastebin.java-gaming.org/83ef674134d1e

Only one order of magnitude between them now, and the naive code is even fast enough for practical purposes :slight_smile:

Also, to win this “contest” I only need to change scale of the problem:

Ags1 v3 Took 1ms to find 1000 primes, highest being 7919
Kaihh v2 Took 9ms to find 1000 primes, highest being 7919

Up till around 8000 primes, the BitSet-based solution performs a bit slower, of course only half a dozen milliseconds slower :slight_smile:

EDIT: If you put the two methods in a loop (which you wouldn’t do, because the program has a practical purpose), then the BitSet methods pulls ahead again even for small prime result sets. JIT doing it’s thing…

#23

Kaihh v3 :smiley: “BitSet traversal optimization”


public static void kaihh() {
    int n = (int) (NUM_PRIMES * (Math.log(NUM_PRIMES) + Math.log(Math.log(NUM_PRIMES)) + 1));
    BitSet notPrime = new BitSet(n);
    int sqrtN = (int) Math.sqrt(n);
    for (int i = 2; i <= sqrtN; i = notPrime.nextClearBit(i + 1)) {
        for (int j = i * i; j <= n; j += i) {
            notPrime.set(j, true); // <- true = this is NOT prime
        }
    }
    int primeCount = 1;
    int lastPrime = 2;
    for (int i = 2; primeCount <= NUM_PRIMES; i = notPrime.nextClearBit(i + 1)) {
        lastPrime = i;
        primeCount++;
    }
}

EDIT: First traversal can be optimized the same way.

#24

Kaihh v3 Took 179ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 321ms to find 1000000 primes, highest being 15485863
Ags1 v3 Took 2209ms to find 1000000 primes, highest being 15485863

Kaihh v3 Took 209ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 359ms to find 1000000 primes, highest being 15485863
Ags1 v3 Took 2207ms to find 1000000 primes, highest being 15485863

Kaihh v3 Took 180ms to find 1000000 primes, highest being 15485863
Kaihh v2 Took 296ms to find 1000000 primes, highest being 15485863
Ags1 v3 Took 2427ms to find 1000000 primes, highest being 15485863

#25

Nothing that’s remotely current.

If someone wants to knock themselves out: http://cr.yp.to/primetests/prime2004-20040212.pdf

#26

Sorry for the necro, but this fits perfectly in here:
This repository is probably going to become the industry’s standard for implementations of prime sieves. Originally, and which was how I found it, Dave’s Garage made a video about a competition: which language is fastest? Using the prime sieve as a candidate for evaluating the performance.

1 Like