Sieve of Eratosthenes, Iterative vs. Recursive

April 18, 2006 at 6:31 am · Filed under Uncategorized

A few weeks ago, some of us in the Silicon Valley Patterns Group implemented Java solutions for the Sieve of Eratosthenes as described in the most excellent Structure and Interpretation of Computer Programs (SICP). The book of course, implements it in Scheme.

Kevin and I were talking about it, and Kevin came up with a very tight, Java solution. His solution was not recursive though, instead it would iterate over the primes the program had already found so far. It certainly worked but I wanted to do it using recursion. I imagined a recursive approach would be more elegant. It would certainly look more like the Scheme version:

(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (filter-stream pred stream)
  (cond ((null? stream) '())
        ((pred (car stream))
         (cons-stream (car stream) (filter-stream pred (stream-cdr stream))))
        (else
         (filter-stream pred (stream-cdr stream)))))

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define sieved-primes (sieve (integers-starting-from 2)))

As it turned out, I was wrong about elegance. Performance is also much worse.

This is the iterative method, inspired by Kevin’s solution. The idea is very simple. For every new number starting with ‘2′, see if the number is prime by trying to divide it by all numbers in the “prime pool”. If the new integer is not divisible by any of the numbers already identified as prime, then this new number is itself a prime. The next integer coming in, should also be divided by the new prime. This is Eratosthenes algorithm, nothing new there.

package primes;

import java.util.Iterator;

public class IterativeSieve implements Iterator {

	private int[] primes = new int[]{};
	private NumberNode numbers = new AllNumbers(2);

	public boolean hasNext() {
		return true;
	}

	public Integer next() {
		return new Integer(nextprime());
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}

	private int nextprime() {
            while(true) {
                    int number = numbers.value();
                    if(prime(number)) {
                        addprime(number);
                        return number;
                    }
            }
        }

	private void addprime(int number) {
		int[] newprimes = new int[primes.length+1];
		System.arraycopy(primes, 0, newprimes, 0, primes.length);
		newprimes[newprimes.length-1]=number;
		primes=newprimes;
	}

	private boolean prime(int number) {
		for (int i = 0; i < primes.length; i++) {
			if((number % primes[i]) == 0 ) {
				return false;
			}
		}
		return true;
	}
}

Below is the recursive approach. Here we have two streams of numbers. One is the just the series of integers starting with 2, and the other stream is a linked list of prime numbers. Every time a new integer comes in, we see if that number divides by any of the numbers in the prime stream/linked list. If it doesn’t, we create a new node holding this new number (since this is also a prime) and add it to the list.

package primes;

import java.util.Iterator;

public class RecursiveSieve implements Iterator {
    private NumberNode numbers = new AllNumbers(2);

    public Integer next() {
        int number = numbers.value();
        numbers = new PrimeNumbers(numbers, number);
        return new Integer(number);
    }

    public boolean hasNext() {
        return true;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

package primes;

public class PrimeNumbers implements NumberNode {

    protected int factor;
    private NumberNode previous;

    public PrimeNumbers(NumberNode previous, int factor) {
        this.factor = factor;
        this.previous = previous;
    }

    public int value() {
        while(true) {
            int number = previous.value();
            if(number % factor != 0) {
                return number;
            }
        }
    }
}

package primes;

public interface NumberNode {
    int value();
}

package primes;

public class AllNumbers implements NumberNode {

    private int number;

    public AllNumbers(int number) {
        this.number = number;
    }

    public int value() {
        return number++;
    }
}

Then I ran the two sieves using the following code.

package primes;

import java.util.Iterator;

public class SieveTest {

    public static void main(String[] args) {
        test_sieve_recursive();
        test_sieve_iterative();
    }

    public static void test_sieve_iterative() {
        long t0 = System.currentTimeMillis();
        System.out.print("Iterative: ");
        for (int i = 0; i < 10; i++) {
            lots_of_primes(new IterativeSieve());
        }
        System.out.println((System.currentTimeMillis() - t0) + " msecs.");
    }

    public static void test_sieve_recursive() {
        long t0 = System.currentTimeMillis();
        System.out.print("Recursive: ");
        for (int i = 0; i < 10; i++) {
            lots_of_primes(new RecursiveSieve());
        }
        System.out.println((System.currentTimeMillis() - t0) + " msecs.");
    }

    private static void lots_of_primes(Iterator s) {
        for (int i = 0; i < 5000; i++) {
            s.next();
        }
    }
}

The outcome wasn’t that surprising after all. The iterative approach is faster and uses less memory. The recursive version throws a StackOverflowError after 7000 (with a 512 MB VM) whereas the iterative solution happily keeps going. So the recursive method takes longer, fails, and is uglier.

Output for 10 runs of 5000 integers with both methods:

Recursive: 2109 msecs.
Iterative: 1125 msecs.

Leave a Comment