7
\$\begingroup\$

I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> because of the performance of removing items to the list while looping through it. Also, I'd want to know if I respect the Java conventions with my code.

import java.util.*;
import java.lang.*;
import java.io.*;

public class PrimeFinders
{
    public static void main (String[] args) throws java.lang.Exception
    {
        LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();
        final int maxNumber = 1000; //This is N

        //Add only uneven numbers, as even numbers won't be prime
        for(int i = 3; i <= maxNumber;i+=2){
            naturalNumbers.add(i);
        }

        int primeIndex = 1; //Starting at 1 since we need to count the number 2, not added in the list
        int primeNumber = 2; //First prime number is 2

        while(naturalNumbers.size() > 0){
            primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop.
            System.out.println("Prime " + primeIndex + " : " + primeNumber);
            applyEratosthenesSieve(primeNumber, naturalNumbers);
            primeIndex++;
        }
    }

    private static void applyEratosthenesSieve(int prime, LinkedList<Integer> numbers){
        Iterator<Integer> numbersIterator = numbers.iterator();

        while(numbersIterator.hasNext()){
            int number = numbersIterator.next();
            if(number % prime == 0){ //Remove all multiples of the number.
                numbersIterator.remove();
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You're taking the sieving much too literally. It doesn't work by first storing all numbers somewhere. I mean, drop the LinkedList. \$\endgroup\$ – maaartinus Sep 9 '14 at 6:34
  • \$\begingroup\$ I read that there is an implementation of this sieve that sieves primes up to a billion in 0.2 seconds. To answer your question, measure how long your code takes and compare the results. \$\endgroup\$ – gnasher729 Sep 9 '14 at 9:35
  • 1
    \$\begingroup\$ @TopinFrassi All you need for storing an arbitrary set of numbers up to 1000 is 1000 bits (or bytes as there's no reason to economize). Don't store the number, just remember if you'd store it. \$\endgroup\$ – maaartinus Sep 9 '14 at 11:55
  • 1
    \$\begingroup\$ Well, a billion in 0.2 seconds is world record. 50 times slower would be reasonably decent for a first attempt. \$\endgroup\$ – gnasher729 Sep 9 '14 at 15:24
  • 2
    \$\begingroup\$ I ain't mad or anything, but could the downvoter explain me why is my question deserving a downvote? \$\endgroup\$ – IEatBagels Sep 10 '14 at 2:24
3
\$\begingroup\$

You're close to a sieve, but you're missing some points.

First and foremost your applyEratosthenesSieve is incorrect - this should step though the range in steps of prime; this very fact precludes the use of a LinkedList.

The usual approach uses a boolean[] nonPrime , on which you carry out the following steps:

  1. Set everything to false as you don't know if anything is a composite. This isn't really required as in Java boolean is false by default.
  2. Starting with i = 2 to Math.sqrt(target), if !nonPrime[i], loop over nonPrime for j = i * 2 while j < nonPrime.length in increments of i and set nonPrime[j] = true.
  3. You now have an boolean[] where anything that is false (>=2) is a prime.

The simplest implementation I can think of is:

List<Integer> primesUpTo(final int target) {
    final boolean[] nonPrime = new boolean[target + 1];

    for (int i = 2; i <= Math.sqrt(target); ++i) {
        if (!nonPrime[i]) {
            for (int j = i * 2; j <= target; j += i) {
                nonPrime[j] = true;
            }
        }
    }

    final List<Integer> primes = new ArrayList<>();

    for (int i = 2; i <= target; ++i) {
        if (!nonPrime[i]) primes.add(i);
    }

    return primes;
}

Using Caliper this method has a runtime of around 5ms for target=1,000,000.

I have done a few experiments with speeding up the code. For example, using the Prime number theorem we know that there are approximately x/ln(x) prime numbers between 1 and x. Using this information we can create the ArrayList used for storing the primes to almost the right size:

final int approxPiX = (int) (target / Math.log(target));
final List<Integer> primes = new ArrayList<>(approxPiX);

This should reduce the amount of time the ArrayList spends resizing itself. This reduces the runtime by about .1ms for target=1,000,000 - so has little effect. These sort of micro-optimisations should always be tested using benchmarks to see if the additional code complexity warrants their addition.

A few comments on the code:

Use of final

You use final sometimes to delimit references that won't change:

final int maxNumber = 1000;

But not in other places:

LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();

I don't like this. I think if you are going to down the route of using final then use it for all references that won't change, that includes:

  • fields
  • method parameters
  • variables
  • loop iterators

Scope

It is generally good practice to scope variables in the minimum possible scope. I don't like this:

int primeIndex = 1; //Starting at 1 since we need to count the number 2, not added in the list
int primeNumber = 2; //First prime number is 2

while(naturalNumbers.size() > 0){
    primeIndex++;
}

Firstly because of the scope of primeXXX and also because loop indicies should be incremented inside a for declaration unless you have a good reason not to.

I would prefer the following construct as it show that I have two variables used in the loop, that the termination condition is naturalNumbers.size() > 0 and that I increment primeIndex every iteration.

for (int primeIndex = 1, primeNumber = 2; naturalNumbers.size() > 0; ++primeIndex) {

}

Iterators

Kudos for correctly using an Iterator to remove() from a Collection while iterating. But, as described above, this is not the correct approach to implementing a Sieve.

Programming to the interface

I don't link this method declaration:

private static void applyEratosthenesSieve(int prime, LinkedList<Integer> numbers){

You don't use any of the properties of LinkedList. You do not need to know that it is a LinkedList. I would specify the argument as Iterable and leave the invoking class to decide on an implementation.

Brackets

There are two styles of using curly brackets in Java, and either are valid:

thing {
    ...
}

thing
{
    ...
}

But (and this is a big one for style) you should only use one type. You have got one type in some places and the other type in other places. Set a preferred style in your IDE and stick to it. Also, if using Egyptian brackets (the first style) please leave a space between the statement and the opening bracket.

Comments

Comments like this:

final int maxNumber = 1000; //This is N

Are horrible! If you need to label a variable declaration with what that variable is, you have picked the wrong name.

Further, if you are going to use inline comments, avoid the case where the comment makes the line so long that it's illegible.

\$\endgroup\$
  • \$\begingroup\$ Why do you initialize nonPrime to target + 1, isn't target correct? \$\endgroup\$ – IEatBagels Sep 9 '14 at 16:15
  • 1
    \$\begingroup\$ Because an array has n slots. If you init it to target then the index of the last element is target - 1. As we are using the index to represent the numbers, we need to use target + 1. \$\endgroup\$ – Boris the Spider Sep 9 '14 at 18:12
8
\$\begingroup\$

This doesn't look like a Sieve of Eratosthenes. This sure looks like trial division:

  while(numbersIterator.hasNext()){
      int number = numbersIterator.next();
      if(number % prime == 0){ //Remove all multiples of the number.
          numbersIterator.remove();
      }
  }

Unless I'm misunderstanding what your iterators are doing. A simple SoE will have something that looks like:

for i from 2 to sqrt(n):          /* Loop from 2 to square root of max */
  if A[i]:                        /* If this location indicates prime, */
    for j from i*i to n step i:   /* then for each multiple of i,      */
      A[j] = false;               /* mark composite                    */

See the examples at RosettaCode or Wikipedia for example. For comparison, RosettaCode's Trial Division task has a loop like your function.

So the immediate performance issue is that a sieve will be much faster than trial division.

\$\endgroup\$
  • \$\begingroup\$ In fact your loop and mine have the same purpose, but I'm removing numbers instead of marking them as "non-primes". That is, if I understand your code corectly, what language is it? \$\endgroup\$ – IEatBagels Sep 9 '14 at 12:18
  • 1
    \$\begingroup\$ It's pseudocode, but translating to most languages is pretty easy -- how one stores the array differs, and then we get into wheel optimizations (e.g. odds only, mod 6, mod 30). One thing to note is that there is no division or modulo anywhere. The inner loop is very efficient as it is just: add,mark. The slowdowns come as this gets so large our array doesn't fit in cache, at which point we move to a segmented sieve to keep memory access localized. \$\endgroup\$ – DanaJ Sep 9 '14 at 14:54
  • \$\begingroup\$ Ooh, pseudocode makes sense, I was wondering if there really was a language where if A[i]: meant something. Yes, the inner loop is really efficient. \$\endgroup\$ – IEatBagels Sep 9 '14 at 14:59
  • 2
    \$\begingroup\$ @Topin, if A[i]: is legal syntax in at least one language (Python), assuming A is an array of boolean values. The for-loop syntax is wrong for Python, but Dana wasn't trying to write Python. (Python would use something like for i in range(2, sqrt(n)): and for j in range(i*i, n, i):.) \$\endgroup\$ – Brian S Sep 9 '14 at 15:34
  • \$\begingroup\$ The second and third Python examples on RosettaCode indeed have: if is_prime[n]:. But as Brian said the rest isn't literal Python and wouldn't use my C-style comments either. The RosettaCode link should allow you to see examples in many languages, and many of them recognizably have this basic structure. \$\endgroup\$ – DanaJ Sep 9 '14 at 16:18
4
\$\begingroup\$

There is a bug in your program; it doesn't print the number 2. Here is the problematic code:

int primeNumber = 2; //First prime number is 2

while(naturalNumbers.size() > 0){
    primeNumber = naturalNumbers.pop();
\$\endgroup\$
  • \$\begingroup\$ True, do you think it would be better for me to print it manually before I start the loop? \$\endgroup\$ – IEatBagels Sep 9 '14 at 12:19
4
\$\begingroup\$
  • It may be preferred to just list the specific imports (not using *). It may not matter for this small program that uses a few, but it could be nicer to know exactly which imports are being used.

  • Users of your code may want to know exactly which exceptions could be thrown. By just throwing Exception from main(), the user may just try to catch anything. I believe that Exception is put there by default with some IDEs (such as Ideone), while it doesn't imply that it'll always be needed, especially if the program won't potentially throw any exceptions.

    Basically, just remove it. If you know that main() could throw some exception (the compiler may alert you of the specific one at the specific location), then throw it.

  • Since this while loop increments its counter each time:

    while(naturalNumbers.size() > 0){
        primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop.
        System.out.println("Prime " + primeIndex + " : " + primeNumber);
        applyEratosthenesSieve(primeNumber, naturalNumbers);
        primeIndex++;
    }
    

    it can just be a for loop:

    for (primeIndex = 1; naturalNumbers.size() > 0; primeIndex++) {
        primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop.
        System.out.println("Prime " + primeIndex + " : " + primeNumber);
        applyEratosthenesSieve(primeNumber, naturalNumbers);
    }
    
\$\endgroup\$
4
\$\begingroup\$

First thing, I don't like the idea of building a list with all numbers. As @maaartinus pointed out in the comment, it's not necessary.

Secondly, I disagree with @DanaJ, trivial division is a primality test and not an algorithm to find all prime numbers up to a given limit. This looks like a variation of the "Sieve of Eratosthenes" (this algorithm "discards" composite numbers while the "Sieve of Eratosthenes" "marks" numbers as composite).

Also, I don't think there is the error @mjolka states because the code already comments that 2 is the first prime number. I just think that the following is missing before the loop:

System.out.println("Prime 0 : 2");

Following that,primeNumber could be declared inside the loop since the scope of local variables should always be the smallest possible.

And finally, is usually faster using a HashSet than Lists in Java because this class ensures constant time for basic operations like remove and contains (source)

The following example is a bit rough, I'm sure lots of optimizations could be made and that the presented algorithm is not the best one. But It shows the difference in performance between using a LinkedList and a HashSet. I've removed the System.out.println line from inside the loop and tried to make both alternatives as fair as possible.

And here is the code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class PrimeFinders {
    public static void main(String[] args) throws java.lang.Exception {

        for (int i=10; i <= 1000000; i*=10) {
            algorithmA(i);
            algorithmB(i);
        }
    }

    private static void algorithmA(int maxNumber) {
        LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();

        // Add only uneven numbers, as even numbers won't be prime
        for (int i = 3; i <= maxNumber; i += 2) {
            naturalNumbers.add(i);
        }

        int primeIndex = 1; // Starting at 1 since we need to count the number
                            // 2, not added in the list

        long time = System.currentTimeMillis();
        while (naturalNumbers.size() > 0) {
            int primeNumber = naturalNumbers.pop(); // Always a prime since
                                                    // non-prime numbers are
                                                    // removed in the loop.
            applyEratosthenesSieve(primeNumber, naturalNumbers);
            primeIndex++;
        }

        long delta =  (System.currentTimeMillis() - time);
        System.out.println("A Done in " + delta
                + "ms and primes found " + primeIndex + " for maxNumber " + maxNumber);
    }

    private static void applyEratosthenesSieve(int prime,
            LinkedList<Integer> numbers) {
        Iterator<Integer> numbersIterator = numbers.iterator();

        while (numbersIterator.hasNext()) {
            int number = numbersIterator.next();
            if (number % prime == 0) { // Remove all multiples of the number.
                numbersIterator.remove();
            }
        }
    }

    private static void algorithmB(int maxNumber) {
        HashSet<Integer> primeNumbers = new HashSet<Integer>(maxNumber / 2);

        // Add only uneven numbers, as even numbers won't be prime
        for (int i = 3; i <= maxNumber; i += 2) {
            primeNumbers.add(i);
        }

        long time = System.currentTimeMillis();

        for (int i = 3; i <= maxNumber; i +=2) {
            if (primeNumbers.contains(i)) {
                applyEratosthenesSieveB(i, primeNumbers, maxNumber);
            }
        }

        primeNumbers.add(2); // 2 is also a prime number

        // Sort prime numbers so this algorithm is "fair" with the other one
        List<Integer> primeNumbersOrdered = new ArrayList<Integer>(primeNumbers);
        Collections.sort(primeNumbersOrdered);

        long delta =  (System.currentTimeMillis() - time);
        System.out.println("B Done in " + delta
                + "ms and primes found " + primeNumbersOrdered.size() + " for maxNumber " + maxNumber);
    }

    private static void applyEratosthenesSieveB(int prime,
            HashSet<Integer> numbers, int maxNumber) {

        // Remove all odd multiples of prime 
        for (int x=2*prime; x <= maxNumber; x += prime) {
            numbers.remove(x);
        }
    }
}

Adding to @Boris answer (sorry that I cannot comment yet but I agree with almost everything):

I don't see any performance problems for computing such a small number of primes as the example in the question. Just follow the style and principle designs recommendations in these answers and that's it.

If we scale this algorithm to compute a large range of prime numbers and performance is really a concern, I would suggest the following:

  1. We know even numbers (but 2) are composite, so we can modify @Boris' code to use less memory and be a bit faster if we only check for odd numbers. In a few words, we can allocate half the booleans and consider they're all odd (i.e.: 3, 5, 7, ...). The performance is better for a high target (if not is about the same) and consumes about half memory.

    List primesUpTo(final int target) {

    // 0,1 and 2 are not considered (-3) and even numbers neither (/2)
    // The inverse function is y = 2 * x + 3
    final boolean[] nonPrime = new boolean[(target - 3) / 2];
    
    for (int i = 0; i < Math.sqrt(nonPrime.length); i++) {
        if (!nonPrime[i]) {
            // We know that this position is a prime since still false
            int prime = 2 * i + 3;
            for (int j = i + prime; j < nonPrime.length; j += prime) {
                nonPrime[j] = true;
            }
        }
    }
    
    final List<Integer> primes = new ArrayList<>();
    primes.add(2); // 2 is the first prime
    
    for (int i = 0; i < nonPrime.length; i++) {
        if (!nonPrime[i]) {
            int prime = 2 * i + 3;
            primes.add(prime);
        }
    }
    
    return primes;
    

    }

  2. For high performance algorithms, I don't think that using boolean or byte arrays is appropriate. First, in Java booleans are everything but 1 bit (their size is platform dependent) and it's usually faster to loop through a int since its size is 32 bits and how the JVM works. I would substitute this by a more complex solution with a int[] and using bit masks and bit operations. That would reduce memory to 1/4 (if we assume that 1 boolean is 8 bits). However, I'm confident that it would lead to a much faster and more optimized algorithm.

  3. I would study about using multiple threads to speed it up.

  4. If JNI is available, it's the way to go.

\$\endgroup\$
  • 1
    \$\begingroup\$ I would remove the benchmarks - since you run A first then B and do not JIT warming they don't tell you much. It's almost certain that A is slower but the numbers don't say by how much. If you want to do actual benchmarking use Caliper. \$\endgroup\$ – Boris the Spider Sep 9 '14 at 11:57
  • \$\begingroup\$ @Boris you're completely right, these are not proper benchmarks, just a naive way to show that it's actually faster. \$\endgroup\$ – FranMowinckel Sep 9 '14 at 12:27
3
\$\begingroup\$

There are a lot of improvements possible, ranging from simple to very hard.

List of possible basic optimizations (no particular order, a few of these may have been covered in other answers):

  1. Use booleans to store a simple yes/no answer, and the index for the number. For example, I could have an array of 1000 booleans, where true means a number at index i is composite and false means i is possibly prime (i.e. hasn't been sieved away yet).

1a. Improvement on 1 is to not use the boolean type, but do some direct bit twidling. A boolean usually takes 8 bits (1 byte) even though only 1 bit is needed for a true/false answer (I think in Java 7/8 they might have finally standardized it's size to 1 byte, but I don't know for sure). I didn't find a significant speed performance increase using this, but the 8x reduction in memory for the sieve is very helpful for going to large N. Have an array of ints/longs, and then index into these with bit twiddling to set/query it.

  1. Don't use linked lists! Linked lists automatically means you'll miss out on cache coherency (it's a huge problem when you get into larger sieves). Use some array-type datastructure. For pure speed I recommend raw arrays, for clarity I recommend ArrayList. The reason arrays are much faster is because they don't have to play this auto boxing/unboxing game ArrayList does. There's about a 2x speedup for larger N. You can pre-allocate a space for storing found primes that's guaranteed to be large enough by using the equation: \$1.25506 * n / ln(n)\$.

  2. The point of a sieve is that you never have to do a mod prime check; You simply start with every prime number in increasing order, and mark off multiples as not being prime. The next number larger than the current prime that hasn't been marked as not prime yet is guaranteed to be prime.

  3. You only need to keep sieving until your sieving prime is greater than \$\sqrt{n}\$. Every number in your sieve after this that hasn't been marked as not prime is guaranteed to be prime.

  4. For the outer sieve loop which finds the next valid prime you can either increment by 2, or implicitly ignore all even numbers in the sieve. Simply incrementing the outer loop by 2 has modest speedups (~10%), and implicitly ignoring all even numbers has a significant speedup, but your code does get more complicated (~50% speedup). Incidentally these methods roughly amount to a very small wheel factorization technique (more on this later).

Further reading of my results with associated code blocks:

Basic Sieve optimizations

Arrays vs. ArrayList Prime Sieve

The next big step is to implement segmented sieves and wheel factorization. The basic idea of segmented sieves is you only store part of the sieve in memory at a time and re-use it, leading to memory savings and more importantly very good cache usage. The idea of wheel factorization is to quickly mark of small primes "in bulk" from your sieve. Both of these are more advanced techniques, but they can provide good speedups.

My first attempts at a segmented sieve had an ~70% speedup over the non-segmented version: Simple Segmented Sieve

I also have a somewhat refined implementation of wheel factorization was able to get an additional ~40% speedup over my segmented sieve: wheel factorization sieve

I've made further improvements over the wheel factorization sieve, but this code switched to C++ and I don't remember exactly what I did (I didn't post this code online). I seem to recall that I was able to get this to run under 2 seconds for primes less than ~1 billion, possibly 1 second, but I can't remember for sure. Note that it wasn't switching to C++ which made my code automatically faster, but I made some actually algorithmic improvements to my code. Also, funny enough the biggest difference is my code ended up looking nicer because I had to play fewer of these funny tricks such as using raw arrays to avoid auto boxing/unboxing to get good performance.

The world record is currently held by primesieve. On roughly comparable hardware to mine, it is ~5x+ faster than my fastest implementation. I'm not entirely sure where he's able to get that much speedup over my code, but I haven't had enough time to look over his code and figure out what optimizations he's been able to make that I'm missing.

As far as programming style goes, quite a few of these optimizations lead to horrible looking code from a pure programming standpoint. Some of them can be cleaned up to look nicer, but many of them can't (for example, using raw arrays vs. ArrayList or all of the bit twiddling code). In these cases comments are your friends (unfortunately some of the posted links have good comments, and others don't)! I think the other answers do a decent job covering the other details of good coding style.

Also, Boris pointed out a key detail I would like to re-iterate on: benchmark your code often! You won't really know what changes will do to your performance unless you actually try them out. Some changes which theoretically sound like a good idea can give you terrible results. Other changes which seem like they shouldn't matter give unexpectedly large improvements in speed.

\$\endgroup\$
1
\$\begingroup\$

I see no advantage to using a linked list over an array. With an array you won't need to store the actual numbers since what you'll be checking for being prime is the INDEX, not the VALUE at the index. The VALUE at the index can be used to indicate whether the index is prime.

The most glaring thing I see in this is that after you find a prime you're iterating through the list by 1 to cast out all of the multiples of that prime. This is horribly wasteful of time since you can simply add a factor of twice your prime to reach the next number that is a multiple of your prime.

Also, iterating through the list each time by 1 to find the multiples of a known prime is not efficient. You know what the prime is, so just generate the multiples and throw them out. This eliminates any need for a division or modulus operation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.