Primality Performance Testing

gistfile1.cs

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;

// Author: Ernst Fluttert
// You can use this without permission
// yet you should mention the author.

namespace ConsoleApplication1
{
	internal class Program
	{
		// returns a naive way to tell if a number is prime
		// complexity per number: 0.5 * N * N = 0.5*N^2 (you need to do 3 .. N modulos)
		public static bool isPrimeNaive(int number)
		{
			// Skip 1, 2, and even numbers
			if (number < 2) { return false; }
			if (number == 2) { return true; }
			if (number % 2 == 0) { return false; }

			// else loop over numbers
			bool isPrime = true;
			for (int i = 3; i < number; i++)
			{
				if (number % i == 0)
				{
					isPrime = false;
					break;
				}
			}
			return isPrime;
		}

		// use an optimized algorithm
		// complexity for primenumbers: 0.5 * 0.5 * sqrt(N) = 0.25 * N^0.5
		public static bool isPrimeOptimized(int number)
		{
			if (number < 2) { return false; } // skip negative, 0 and 1
			
			// isEven? using bitshift is slightly faster then modulo (especially with big numbers)
			if ((number & 1) != 1) {
				// only 2 is a valid prime
				if (number == 2) { return true; }
				return false; 
			}
						
			// else loop over the odd numbers
			bool isPrime = true;
			// only loop over the number up to SQRT (rounded down)
			int ceilSqrt = (int)Math.Sqrt(number) + 1;
			for (int i = 3; i < ceilSqrt; i = i + 2)
			{	// only need to prove that the number is divisable by
				if (number % i == 0)
				{	// oh noes! Number is composite! 
					isPrime = false;
					break;
				}
			}
			// yeah PRIME NUMBER!
			return isPrime;
		}

		/// <summary>
		/// isPrimeFast :: Uses an optimized fast approach to check primality
		/// </summary>
		/// <param name="number">Integer to test</param>
		/// <returns></returns>
		public static bool isPrimeFast(int number)
		{
			if (number < 2) { return false; } // skip negative, 0 and 1

			// isEven? using bitshift is slightly faster then modulo (especially with big numbers)
			if ((number & 1) != 1)
			{
				// only 2 is a valid prime
				if (number == 2) { return true; }
				return false;
			}
			if (number == 3) { return true; }

			// using (6k+i)
			// http://en.wikipedia.org/wiki/Primality_test
			// This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
			// this leaves 6k-1 and 6k+1; yet we must eliminate 2 and 3 (2 already eliminated with bitshift)
			if (number % 3 == 0) {
				return false;
			}

			//int curDivisor = 5;
			int maxDivisor = (int)Math.Ceiling(Math.Sqrt(number));
			for (int curDivisor = 5; curDivisor <= maxDivisor; curDivisor += 6) {
				if (number % curDivisor == 0 || number % (curDivisor + 2) == 0)
				{
					return false;
				}
			}
			return true;
		}

		// ulong - 0 to 18,446,744,073,709,551,615 = Unsigned 64-bit integer
		public static bool isPrimeFast64bit(ulong number)
		{
			if (number < 2) { return false; } // skip negative, 0 and 1

			// isEven? using bitshift is slightly faster then modulo (especially with big numbers)
			if ((number & 1) != 1)
			{
				// only 2 is a valid prime
				if (number == 2) { return true; }
				return false;
			}
			if (number == 3) { return true; }

			// using (6k+i)
			// http://en.wikipedia.org/wiki/Primality_test
			// This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
			// this leaves 6k-1 and 6k+1; yet we must eliminate 2 and 3 (2 already eliminated with bitshift)
			if (number % 3 == 0)
			{
				return false;
			}

			ulong curDivisor = 5;
			ulong maxDivisor = (ulong)Math.Ceiling(Math.Sqrt(number));
			while (curDivisor <= maxDivisor)
			{
				if (number % curDivisor == 0 || number % (curDivisor + 2) == 0)
				{
					return false;
				}
				curDivisor += 6;
			}
			return true;
		}

		// makes a list of squareroots
		private static List<int> SquareRoots(int max) {
			var maxSqrt = (int)Math.Ceiling(Math.Sqrt(max));
			var sqrts = new int[max];
			sqrts[0] = 0;
			// fill the list where the index is the current number and the int-value is the squareroot (ceiling(sqrt(i))
			// [1] = 1; [2] = 2; [3] = 2; [4] = 2; [5] = 3; [6] = 3; [7] = 3; [8] = 3; [9] = 3; [10] = 4; etc
			int curSquare = 0; int upperRange = 0;
			for (int i = 1; i < max; i++)
			{	// loop in through all numbers
				if(i > upperRange)
				{	// set new currentSquare and new upperrange
					curSquare = ++curSquare;
					upperRange = curSquare * curSquare;
				}
				// set the sqrt for this number
				sqrts[i] = curSquare;
			}
			return sqrts.ToList();
		}

		public static List<int> PrimeRange(int inclusiveMin, int exclusiveMax) {
			var primes = new List<int>();
			var sqrts = SquareRoots(exclusiveMax);

			for (int i = inclusiveMin; i < exclusiveMax; i++)
			{
				if (i < 2) { continue; } // skip negative, 0 and 1
				if ((i & 1) != 1)
				{	// only 2 is a valid prime
					if (i == 2) { primes.Add(i); }
					continue;
				}
				int ceilSqrt = sqrts[i] + 1;
				bool isPrime = true;
				for (int j = 3; j < ceilSqrt; j = j + 2)
				{	// only need to prove that the number is divisable by
					if (i % j == 0)
					{	// oh noes! Number is composite! 
						isPrime = false;
						break;
					}
				}
				if (isPrime) { primes.Add(i); }
			}
			return primes;
		}

		private static void Main(string[] args)
		{
			Stopwatch sw = new Stopwatch();
			Console.Out.WriteLine("Testing Prime methods");
			
			// TEST the output
			Console.Out.WriteLine("Test 1 - 200");
			List<int> resNaive = new List<int>();
			List<int> resOptimized = new List<int>();
			List<int> resFast = new List<int>();
			List<int> resFast64 = new List<int>();
			for (int i = 1; i < 200; i++)
			{
				if (isPrimeNaive(i)) { resNaive.Add(i); }
				if (isPrimeOptimized(i)) { resOptimized.Add(i); }
				if (isPrimeFast(i)) { resFast.Add(i); }
				if (isPrimeFast64bit((ulong)i)) { resFast64.Add(i); }
			}
			Console.Out.WriteLine("Result Naive: " + String.Join(", ", resNaive));
			Console.Out.WriteLine("Result Optmz: " + String.Join(", ", resOptimized));
			Console.Out.WriteLine("Result PFast: " + String.Join(", ", resFast));
			Console.Out.WriteLine("Result Fst64: " + String.Join(", ", resFast64));
			Console.Out.WriteLine("Result Range: " + String.Join(", ", PrimeRange(1,200)));

			// Calculate the 50th million prime: 982,451,653 (source: http://primes.utm.edu/lists/small/millions/ )
			Console.Out.WriteLine("\nTesting Naive method with prime 982,451,653");
			sw.Start();
			if (isPrimeNaive(982451653)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);
			sw.Reset();
			Console.Out.WriteLine("Testing optimized method with 982,451,653");
			sw.Start();
			if (isPrimeOptimized(982451653)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);
			sw.Reset();
			Console.Out.WriteLine("Testing fast method with prime 982,451,653");
			sw.Start();
			if (isPrimeFast(982451653)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			// Calculate 2,147,483,647 (source: http://en.wikipedia.org/wiki/2147483647 )
			sw.Reset();
			Console.Out.WriteLine("\nTesting Naive method with prime 2,147,483,647");
			sw.Start();
			if (isPrimeNaive(2147483647)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing optimized method with prime 2,147,483,647");
			sw.Start();
			if (isPrimeOptimized(2147483647)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);
			sw.Reset();

			Console.Out.WriteLine("Testing fast method with prime 2,147,483,647");
			sw.Start();
			if (isPrimeFast(2147483647)) { Console.Out.WriteLine("IS PRIME"); }
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("\nTesting Naive method with 1 - 250 000");
			sw.Start();
			for (int i = 0; i < 250001; i++)
			{
				isPrimeNaive(i);
			}
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing isPrimeOptimized with 1 - 25 000 000");
			sw.Start();
			for (int i = 0; i < 25000001; i++)
			{
				isPrimeOptimized(i);
			}
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing isPrimeFast with 1 - 25 000 000");
			sw.Start();
			for (int i = 0; i < 25000001; i++)
			{
				isPrimeFast(i);
			}
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing isPrimeFast64bit with 1 - 25 000 000");
			sw.Start();
			for (ulong i = 0; i < 25000001; i++)
			{
				isPrimeFast64bit(i);
			}
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing PrimeRange with 1 - 25 000 000");
			sw.Start();
			PrimeRange(0, 25000001);
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing Parallel.For (threaded) isPrimeOptimized with 1 - 25 000 000");
			sw.Start();
			// parallellized the FOR loop, with delegate
			Parallel.For(0, 25000001, i =>
			{
				isPrimeFast(i);
			});
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing Partitioned Parallel.For isPrimeOptimized with 1 - 25 000 000");
			sw.Start();
			var rangePartitioner = Partitioner.Create(0, 25000001);

			Parallel.ForEach(rangePartitioner, (range, loopstate) =>
			{
				for (int i = range.Item1; i < range.Item2; i++)
				{
					isPrimeFast(i);
				}
			});
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			sw.Reset();
			Console.Out.WriteLine("Testing Parallel.For isPrimeOptimized with 1 - 100 000 000");
			sw.Start();
			// parallellized the FOR loop, with delegate
			Parallel.For(0, 100000001, i =>
			{
				isPrimeFast(i);
			});
			sw.Stop();
			Console.WriteLine("Time elapsed: {0}", sw.Elapsed);

			Console.Out.WriteLine("Press any key to close");
			Console.ReadKey();
		}
	}
}