Prime Numbers

The motivation for this entry is based on chapter 5 of the book Agile Software Development Principles, Patterns and Practices by Robert Martin. In that chapter the author writes an initial program with correct output. The issue is that it is not as simple to follow (and possibly maintain) as the final one. The final one is longer but much easier to follow.

I was not able to find the source code in the URL specified by the book: www.objectmentor.com/PPP (the domain is up for grabs). I wanted to determine if the performance would be different (better) for the short program when compared against the longer one, which also outputs the same results.

Following is the initial slightly modified program that generates prime numbers:

package com.john.canessa.primes;

import java.util.Scanner;

public class Solution {

	/*
	 * test class
	 */
	public static void main(String[] args) {

		int[] primes	= null;
		long  begin		= 0;
		long  end		= 0;
		long  average	= 0;
		long  duration	= 0;
		int   loops 	= 10;
		
		// **** ****
		Scanner sc = new Scanner(System.in);
		System.out.print("main >>> maxValue: ");
		int maxValue = sc.nextInt();
		sc.close();
		
		// **** ****
		for (int i = 0; i < loops; i++) {
			
			// **** ****	
			begin 		= System.currentTimeMillis();
			primes		= GeneratePrimes.generatePrimes(maxValue);
			end 		= System.currentTimeMillis();
			duration 	= end - begin;
			System.out.println("main <<< short duration: " + duration + " ms");
			average 	+= duration;
//			GeneratePrimes.show(primes);
			
			// **** ****
			begin 		= System.currentTimeMillis();
			primes 		= PrimeGenerator.generatePrimes(maxValue);
			end 		= System.currentTimeMillis();
			duration	= end - begin;
			System.out.println("main <<<  long duration: " + (end - begin) + " ms");
			average 	+= duration;
//			PrimeGenerator.show(primes);
		}
		
		// **** compute average time ****
		System.out.println("main <<<        average: " + average / (loops * 2) + " ms");
	}
}

Following is the final slightly modified program that generates prime numbers:

package com.john.canessa.primes;

public class PrimeGenerator {
	
	private static boolean[] 	crossedOut 	= null;
	private static int[] 		result		= null;
	
	/*
	 * generate primes
	 */
	public static int[] generatePrimes(int maxValue) {
		
		// **** ****
		if (maxValue < 2) {
			return new int[0];
		}
		
		// **** ****
		uncrossIntegersUpTo(maxValue);
		crossOutMultiples();
		putUncrossedIntegersIntoResult();
		
		// **** ****
		return result;
	}
	
	/*
	 * allocate and uncross integers up to the specified value
	 */
	private static void uncrossIntegersUpTo(int maxValue) {
		crossedOut = new boolean[maxValue + 1];		
	}
	
	/*
	 * 
	 */
	private static void crossOutMultiples() {
		int limit = determineIterationLimit();
		for (int i = 2; i <= limit; i++) {
			if (notCrossed(i)) {
				crossOutMultiplesOf(i);
			}
		}
	}
	
	/*
	 * 
	 */
	private static int determineIterationLimit() {
		double iterationLimit = Math.sqrt(crossedOut.length);
		return (int)iterationLimit;
	}
	
	/*
	 * 
	 */
	private static void crossOutMultiplesOf(int i) {
		for (int multiple = 2 * i; multiple < crossedOut.length; multiple += i) {
			crossedOut[multiple] = true;
		}
	}
	
	/*
	 * 
	 */
	private static boolean notCrossed(int i) {
		return crossedOut[i] == false;
	}
	
	/*
	 * 
	 */
	private static void putUncrossedIntegersIntoResult() {
		result = new int[numberOfUncrossedIntegers()];
		for (int j = 0, i = 2; i < crossedOut.length; i++) {
			if (notCrossed(i)) {
				result[j++] = i;
			}
		}
	}
	
	/*
	 * count the number of uncrossed values
	 */
	private static int numberOfUncrossedIntegers() {
		int count = 0;

		for (int i = 2; i < crossedOut.length; i++) {
			if (notCrossed(i)) {
				count++;
			}
		}
		
		return count;
	}
	
	/*
	 * show primes in array
	 */
	public static void show(int[] primes) {
		for (int i = 0; i < primes.length; i++) {
			System.out.printf("%6d ", primes[i]);
			if ((i != 0) && (((i + 1)% 10) == 0)) {
				System.out.println();
			}
		}
		System.out.println();
	}
}

Following is the test program comparing the initial and final (and more complex) programs to generate the same set of primes (in our case the primes from 2 to 9,999,999):

package com.john.canessa.primes;

public class GeneratePrimes {

	/*
	 * generate prime numbers using a sieve.
	 * 
	 * Sieve: an instrument with a meshed or perforated bottom,
	 * used for separating coarse from fine parts of loose matter,
	 * for straining liquids, etc., especially one with a circular
	 * frame and fine meshes or perforations.
	 */
	public static int[] generatePrimes(int maxValue) {
		
		// **** not a prime ****
		if (maxValue < 2) {
			return new int[0];
		}
		
		// **** declarations ****
		int s 			= maxValue + 1;			// size of array
		boolean[] f 	= new boolean[s];
		int	i			= 0;
		int[] primes 	= null;
		
		// **** initialize array to true ****
		for (i = 2; i < s; i++) {
			f[i] = true;
		}
		
		// **** sieve ****
		int j;
		for (i = 2; i < (Math.sqrt(s) + 1); i++) {
			
			// **** cross off its multiples (as needed) ****
			if (f[i]) {
				for (j = 2 * i; j < s; j += i) {
					
					// **** multiple is not a prime ****
					f[j] = false;
					}
			}
		}
		
		// **** count the number of primes ****
		int count = 0;
		for (i = 0; i < s; i++) {
			if (f[i]) {
				count++;
			}
		}
		
		// **** allocate an array for the prime numbers ****
		primes = new int[count];
		
		// **** set the primes in the array ****
		for (i = 0, j = 0; i < s; i++) {
			if (f[i]) {
				primes[j++] = i;
			}
		}
		
		// **** return list of prime numbers ****
		return primes;
	}
	
	/*
	 * show primes in array
	 */
	public static void show(int[] primes) {
		for (int i = 0; i < primes.length; i++) {
			System.out.printf("%6d ", primes[i]);
			if ((i != 0) && (((i + 1)% 10) == 0)) {
				System.out.println();
			}
		}
		System.out.println();
	}
}

Following is the output from the test program as captured from the console of the Eclipse IDE:

main >>> maxValue: 9999999
main <<< short duration: 234 ms
main <<<  long duration: 246 ms
main <<< short duration: 227 ms
main <<<  long duration: 209 ms
main <<< short duration: 196 ms
main <<<  long duration: 238 ms
main <<< short duration: 214 ms
main <<<  long duration: 195 ms
main <<< short duration: 188 ms
main <<<  long duration: 190 ms
main <<< short duration: 195 ms
main <<<  long duration: 190 ms
main <<< short duration: 195 ms
main <<<  long duration: 201 ms
main <<< short duration: 208 ms
main <<<  long duration: 171 ms
main <<< short duration: 179 ms
main <<<  long duration: 190 ms
main <<< short duration: 186 ms
main <<<  long duration: 195 ms
main <<<        average: 202 ms

As we can see, sometimes the shorter program takes longer than the longer but easier to follow and maintain program. On other occasions the longer program takes more time. In this case it seems that there is no overhead penalty writing easier to maintain programs. Please keep in mind that on some occasions the shorter program may in most cases run faster than the longer one. Always test with real data in order to make performance decisions.

If you have comments or questions regarding this or any other entry in this blog, please send me a message via email. I will not disclose your name unless you explicitly specify so.

John

john.canessa@gmail.com

@john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.