Sunday, May 03, 2009

JavaOne Talk: Prime Sieve

Next month I am speaking at JavaOne on the performance of various programming languages running on the JVM. For the talk, I am taking several algorithm/programming problems solved in each of the various languages, and comparing the relative performance and tuning tips. For each problem, I am using "native Java" as a reference point. This is the first of many blog posts that show these various programming problems solved in the various languages. I am posting these programs as a way for other folks to let me know where I've screwed up, i.e. done something that will negatively affect performance, etc.

I am not too interested in significantly different ways to solve these problems. For example, the first algorithm is a prime sieve. So I would not be interested in somebody letting me know that there are other ways to generate primes besides a sieve. However, I am interested in finding mistakes in my implementations. I will not claim to be an expert in any of these languages -- in fact I have been learning two of the languages, Fan and Clojure, specifically for this talk -- so there is a good chance that I did screw something up. Even in the languages that I'd like to think I am pretty good at (including Java), I figure there is always a good chance of me doing something screwy there too. So without further ado, here is my prime sieve in Java.


import java.util.Arrays;

// calculates the first n primes
public class Primes {
final private int[] primes;
private int cnt = 0;

public Primes(int n){
primes = new int[n];
init();
}

private void init(){
int i=2;
int max = calcSize();
boolean[] nums = new boolean[max];
Arrays.fill(nums, true);
while (i < max && cnt < primes.length){
int p = i;
if (nums[i]){
// add it to the list of primes
primes[cnt++] = p;
int j = 2*p;
// remove all the multiples of the prime
while (j < max - p){
nums[j] = false;
j += p;
}
}
i += 1;
}
}

public int last(){
return primes[cnt-1];
}

// calculates number of integers needed to find n primes
private int calcSize(){
int max = 2;
while ((max/Math.log(max)) < primes.length && max < Integer.MAX_VALUE && max > 0){
max *=2; // memory inefficient, but fast
}
return max;
}
}

No comments:

Post a Comment