Counting Prime Numbers – Java SE Multi Threaded using BigInteger

Hope everybody enjoyed a good weekend.

So, this weekend I was going through the Programming Praxis website, and this problem caught my eye.

Prime numbers, they are a fascinating subject for mathematicians for several centuries now. Although there are other and faster methods of counting prime numbers up to a range, this method involves some rather unique programming techniques, like using very big numbers, looping through large mathematical range in parallel etc.

I have written this program in Java SE using simple text editor and javac command line tool for compiling, so this is no fancy stuff. But if you’re still interested please read on.

So, here is the problem description as on PP:

Today we look at a rather different method of counting the primes that is due to G. H. Hardy and Edward M. Wright. Their method is based on factorials, and their formula is

for n > 3, where ⌊n⌋ is the greatest integer less than n. The expression inside the big parentheses is 1 when n is prime and 0 when n is composite, by Wilson’s Theorem, which states that an integer n > 1 is prime if and only if (n − 1)! ≡ −1 (mod n); the theorem was first stated by Ibn al-Haytham (c. 1000AD), but is named for John Wilson, who first published it in 1770, and it was first proved by Lagrange in 1771.

Your task is to write a program that counts primes by the Hardy-Wright method.

And, here is how I approached the problem:

Part 1: The Factorials

As we can see the first part of the program is to build a method which takes an integer and returns it’s Factorial. A simple google search returns

Factorials are very simple things. They’re just products, indicated by an exclamation mark. For instance, “four factorial” is written as “4!” and means 1×2×3×4 = 24. In general, n! (“enn factorial“) means the product of all the whole numbers from 1 to n; that is, n! = 1×2×3×…×n.

But as they are products, they can result into very big numbers, and through some very simple testing I found that in Java we can’t go for the standard int or long or even double notations.

So I googled and found out about java.math.BigInteger.

The java.math.BigInteger class provides operations analogues to all of Java’s primitive integer operators and for all relevant methods from java.lang.Math. [Read more]

So, below is what my recursive factorial method looks like.

import java.math.*;

private BigInteger factorial(int n)
{
if(n == 0)
return BigInteger.valueOf(1);
else
return BigInteger.valueOf(n).multiply(factorial(n - 1));
}


Please make a note here that the standard arithmetic operations are method calls for BigInteger.

Part 2: The Sigma

So now we have to calculate this part

which means evaluating the expression inside the big parenthesis for all values of j from 3 up to n and then summing up all those values.

Now, this is fine to do in single for loop when n is relatively smaller, but what happens when n is 5000 or 10000? It will take a large amount of time if we do this in a single loop for large numbers. So we use Java Multi-threading.

The basic idea is to build a method which takes a minimum and maximum integer and returns the sum for the above mentioned expression.

Then we chop up the range [3..n] into number of chunks and then call parallel threads which returns us the sums from all the threads separately.

Then we get those individual sums for each chunk separately and add them all up to get our desired result.

How many threads?

Java has a method availableProcessors() which will tell you the number of processing threads available to your JVM. Using this you won’t have to hard code the number of threads.

I got a Intel® Hyper-threaded 4 core CPU for which I get the number 8 when I run availableProcessors().

private int arraySize = Runtime.getRuntime().availableProcessors();


Now that we got our thread count, we will determine the maximum number of elements  present in each chunk.

private int chunkSize = 0;
private int div = 0;
private int mod = 0;

private void determineChunk()
{
div = (int)Math.floor((tempMax - tempMin + 1) / arraySize);
mod = (tempMax - tempMin + 1) % arraySize;
chunkSize = (mod == 0) ? (div + 1) : (div + 2);
}

After that we write a method to get a two dimensional array of size arraySize, every element of which will hold 2 values, minimum and maximum value of that range.
private void buildChunk()
{
for(int i = 1; i <= arraySize; i++)
{
chunk[i-1][0] = (i * chunkSize) - chunkSize + tempMin;
chunk[i-1][1] = ((i * chunkSize) - 1 + tempMin) > tempMax ? tempMax : ((i * chunkSize) - 1 + tempMin);
}
}

Then we write a thread class whose run method calculates the sum for the above mathematical expression for a supplied range. It also has a method to return the calculated sum.

private BigInteger sum = new BigInteger("0");
private BigInteger fac1 = new BigInteger("0");
private BigInteger fac2 = new BigInteger("0");
public SigmaThread(int min, int max)
{
this.min = min;
this.max = max;
}
public void run()
{
for(int i = min; i <= max; i++)
{
fac1 = factorial(i - 2);
fac2 = BigInteger.valueOf(i).multiply(factorial(i - 2).divide(BigInteger.valueOf(i)).abs());
sum = sum.add(fac1.subtract(fac2));
}
}
public BigInteger getResult()
{
return sum;
}

Then we start required number of threads according to our need.

for(int i = 0; i < arraySize; i++)
{
st[i] = new SigmaThread(chunk[i][0], chunk[i][1]);
t[i] = new Thread(st[i]);
t[i].start();
}


Then we wait until all the threads are done.

while(1 == 1)
{
deadCount = 0;
for ( int i = 0; i < arraySize; i++ )
{
if(!t[i].isAlive())
deadCount++;
}
if(deadCount == arraySize)
{
break;
}
}


When all is done we simply sum up all the sums from all the threads and subtract 1 from it and we get our results.

for ( int i = 0; i < arraySize; i++ )
{
sigma = sigma.add(st[i].getResult());
}
sigma = sigma.subtract(BigInteger.valueOf(1));


Below are some results and benchmark times I got using 8 threads on 2.40GHz i7-4700MQ CPU.

CountPrime 51 = 15
CountPrime 100 = 25
CountPrime 1000 = 168
CountPrime 5000 = 669 (Result in 10 seconds)
CountPrime 10000 = 1229 (Result in 85 seconds)

You can use this site to verify your own results.

The whole compressed source code is available here to download.

Please like and share on social media / linked in if you found this article interesting or helpful. Thank you and have a nice week ahead.