Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

View RSS Feed

helloworld922

Optimizing the Sieve of Eratosthenes

Rate this Entry
The Sieve of Eratosthenes is one of the fastest methods for generating a list of prime numbers less than a given number n. A general description of the algorithm is given below:

1. Initialize a list representing the numbers [2,n). This denotes whether a given number is prime or composite.
2. Start from the beginning of the list. If the number is denoted as prime, save it. Otherwise, move on.
3. For every multiple of the current prime, mark it as a composite number.

Below is code implementing the Sieve of Eratosthenes as naively as possible:

public static List<Integer> eratosthenes_naive(int n)
	{
		boolean[] is_composite = new boolean[n];
 
		List<Integer> results = new ArrayList<Integer>();
		for (int i = 2; i < is_composite.length; ++i)
		{
			if (!is_composite[i])
			{
				results.add(i);
				for (int j = i; j < is_composite.length; j += i)
				{
					is_composite[j] = true;
				}
			}
		}
		return results;
	}

While fairly quick, there are several optimizations which can be made. The first such optimization is to reduce the inner loop's span. It only needs to start from j = i*i because all values smaller have been marked already.

	public static List<Integer> eratosthenes_optimized1(int n)
	{
		boolean[] is_composite = new boolean[n];
 
		List<Integer> results = new ArrayList<Integer>();
		for (int i = 2; i < is_composite.length; ++i)
		{
			if (!is_composite[i])
			{
				results.add(i);
				for (long j = (long) i * i; j < is_composite.length; j += i)
				{
					is_composite[(int) j] = true;
				}
			}
		}
		return results;
	}

Another optimization that can be made is that the external loop only needs to run for every odd number.

	public static List<Integer> eratosthenes_optimized2(int n)
	{
		boolean[] is_composite = new boolean[n];
 
		List<Integer> results = new ArrayList<Integer>();
		results.add(2);
		for (int i = 3; i < is_composite.length; i += 2)
		{
			if (!is_composite[i])
			{
				results.add(i);
				for (long j = (long) i * i; j < is_composite.length; j += i)
				{
					is_composite[(int) j] = true;
				}
			}
		}
		return results;
	}

A third optimization is to provide an upper bound for the list of prime numbers. An approximation of the upper bound of the prime counting function (the number of primes below a given number n) is 1.25506 * n / ln(n).

	public static List<Integer> eratosthenes_optimized3(int n)
	{
		boolean[] is_composite = new boolean[n];
 
		List<Integer> results = new ArrayList<Integer>((int) Math.ceil(1.25506 * n / Math.log(n)));
		results.add(2);
		for (int i = 3; i < is_composite.length; i += 2)
		{
			if (!is_composite[i])
			{
				results.add(i);
				for (long j = i * (long) i; j < is_composite.length; j += i)
				{
					is_composite[(int) j] = true;
				}
			}
		}
		return results;
	}

The last optimization is to completely remove all even numbers from the is_composite array. This requires a transpose of all indices.

	public static List<Integer> eratosthenes_optimized4(int n)
	{
		boolean[] is_composite = new boolean[n - 2 >> 1];
		List<Integer> results = new ArrayList<>((int) Math.ceil(1.25506 * n / Math.log(n)));
		results.add(2);
		for (int i = 0; i < is_composite.length; ++i)
		{
			if (!is_composite[i])
			{
				results.add(2 * i + 3);
				for (long j = 4L * i * i + 12L * i + 9; j < 2 * is_composite.length + 3; j += 4 * i + 6)
				{
					is_composite[(int) (j - 3L >> 1)] = true;
				}
			}
		}
		return results;
	}

Results
As with any attempts at optimizing code, it's important to benchmark the code. For this, I created a simple test which runs each method 10 times for n = 0x4000000 (~67 million). The results are given below. All times are in milliseconds.

 
naive
min: 2626
avg: 2928
max: 3121

optimized 1 (inner loop optimization)
min: 1607
avg: 1808
max: 1994

optimized 2 (outer loop optimization)
min: 1532
avg: 1658
max: 1835

optimized 3 (memory optimization)
min: 1516
avg: 1618
max: 1738

optimized 4 (structure optimization)
min: 845
avg: 930
max: 1040




I also tracked ideal memory use. Method 4 uses by far the least memory ~50 MB, method 3 is next at ~82 MB. The other methods are difficult to track due to the expanding nature of ArrayLists, but it's sufficient to say they will at best use at least ~82 MB of memory.

The test was also run with a larger data set with n = 0x3FFFFFFF (~1 billion).

 
naive
min: 57899
avg: 62960
max: 73454

optimized 1
min: 34069
avg: 35855
max: 38507

optimized 2
min: 26480
avg: 27870
max: 30047

optimized 3
min: 25290
avg: 27920
max: 30100

optimized 4
min: 17201
avg: 17324
max: 17914




Summary

Through careful testing and analysis it's possible to achieve ~2-3 times speedup over the naive Sieve of Eratosthenes. There are other programs which implement various features such as segmented sieves, wheel factorization, and multi-threading to achieve some very impressive results. The current leader as far as I know is primesieve. It can compute primes up 1 billion in ~0.08 seconds utilizing multi-threading, or in ~0.4 seconds with just a single thread.

Update

Rather than have a boolean (which takes ~ 1 byte) represent each number, I made a recent change which represents each number as a bit in a char. This drastically cuts memory use by ~50%. Performance is not drastically affected, possibly slightly faster.

	public static List<Integer> eratosthenes_optimized5(int n)
	{
		if (n < 2)
		{
			return new ArrayList<Integer>();
		}
		char[] is_composite = new char[(n - 2 >> 5) + 1];
		final int limit_i = n - 2 >> 1, limit_j = 2 * limit_i + 3;
		// boolean[] is_composite = new boolean[n - 2 >> 1];
		List<Integer> results = new ArrayList<>((int) Math.ceil(1.25506 * n / Math.log(n)));
		results.add(2);
		for (int i = 0; i < limit_i; ++i)
		{
			if ((is_composite[i >> 4] & 1 << (i & 0xF)) == 0)
			{
				results.add(2 * i + 3);
				for (long j = 4L * i * i + 12L * i + 9; j < limit_j; j += 4 * i + 6)
				{
					is_composite[(int) (j - 3L >> 5)] |= 1 << (j - 3L >> 1 & 0xF);
				}
			}
		}
		return results;
	}

Updated September 29th, 2012 at 06:26 PM by helloworld922

Categories
Uncategorized

Comments