BigInteger .isProbablePrime() Part 3 Multithreading Tutorial

In this tutorial I am going to build on concepts from the Part 2 Tutorial. I am going to be using the Thread class in this tutorial to greatly reduce the amount of time it takes to find prime factors of a large composite number.

Consider the number 10,000. It is the product of 100 * 100, or the square root of 10,000 is 100 - pretty simple stuff. Now let's take the composite number 9991 and try to come up with a strategy on how to determine what two prime numbers are the factors of this number. Following the same logic from part2, we simply start dividing 9991 by prime numbers starting with 2,3,5,7, etc. Eventually we will hit 97 and 9991 will divide out evenly with 103. This takes quite a few calculations to find the prime factors.

Almost every modern computer has multiple cores with multiple processing threads. My CPU has 8 cores with 16 processing threads and my program will finish a lot faster if I utilize all those threads. The idea is simple - we need to divide our large composite number by every prime number from 2 to the square root of large prime number. If we take that range numbers and divide them into groups that match the number of processing threads (16 in my case), then we can speed up the program 16x or more. I have not gone over the concurrency classes yet, so I will use the Thread class for multithreading.



Open the command prompt (CMD - see the Getting Started ) and type in the following commands.

C:\Windows\System32>cd \
C:\>md Java
C:\>cd Java
C:\Java>
C:\Java>md PrimeThree
C:\Java>cd PrimeThree
C:\Java\PrimeThree>Notepad PrimeThree.java

Copy and Paste, or type the following code into Notepad and be sure to save the file when you are done.


import java.math.*;
import java.util.*;

class PrimeThree {
    private static final int BIT_LENGTH = 32;
    private static final int THREAD_COUNT = 16;
	
    private static final BigInteger TWO = new BigInteger("2");
		
    public static void main(String args[]) {
		
        int bits1 = new Random().nextInt(BIT_LENGTH-3)+ 2; // create a random int between 2 and BIT_LENGTH-2
        int bits2 = BIT_LENGTH - bits1;
		
        BigInteger p1 = new BigInteger(bits1, 80, new Random());
        BigInteger p2 = new BigInteger(bits2, 80, new Random());
        BigInteger largeComposite = p1.multiply(p2);
		
        //System.out.println(p1 + ", " + bits1 + " bits");
        //System.out.println(p2 + ", " + bits2 + " bits");
        System.out.println("largeComposite= " + largeComposite + ", " + largeComposite.bitLength() + " bits");
        BigInteger square = bigSQRT(largeComposite);
        System.out.println("Square root= " + square );
        System.out.println();
		
        // divide by 2, the only even prime number
        if (largeComposite.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
            System.out.println("First prime factor is 2" );
            System.out.println("Second prime factor is " + largeComposite.divide(TWO));
            return ;
        }
		
        // groupCount will hold the amount of numbers that each Thread will perform calculations on
        BigInteger groupCount = square.divide(new BigInteger(""+THREAD_COUNT)).add(BigInteger.ONE);
        //System.out.println(groupCount);
		
        FoundFactor ff = new FoundFactor();
        BigInteger from = null;
        BigInteger to = null;
		
        for (int i = 0; i < THREAD_COUNT; i++) {
            from = new BigInteger(""+i).multiply(groupCount);
            if (i == 0) {
                from = new BigInteger("3");
            }
            // check to see if from is an even number, if so, subtract 1
            if (from.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
                from = from.subtract(BigInteger.ONE);
            }
            to = new BigInteger(""+(i+1)).multiply(groupCount);
            System.out.println(from + ", "+ to);

            //new FindPrimeFactors(largeComposite, from, to, "thread"+i, ff);
        }
		
    /*
        Thread mainThread = Thread.currentThread(); // main thread
        System.out.println("Active threads for this thread group: " + Thread.activeCount());
        while(Thread.activeCount() > 1) {           
            if (ff.foundIt.equals("FOUND")) {
                //System.out.println("Found the factor!!!!!");
                for (int i = 0; i < THREAD_COUNT; i++) {
                    Thread t = threadRef("thread"+i);
                    if (t != null) {
                        t.interrupt();
                        //System.out.println("----Interupted----");
                    }
                }
            }
            try {
                mainThread.sleep(200);
            } catch (InterruptedException e) {
                System.out.println("Main thread interrupted");
            }
        }
        //System.out.println("Active threads for this thread group: " + Thread.activeCount());
    */
    }
	
	
    static Thread threadRef(String name) {
        Map<Thread, StackTraceElement[]> map = Thread.getAllStackTraces();
        for (Thread temp : map.keySet()) {
            if (temp.getName().equals(name)) {
                return temp;
            }
        }
        return null;
    }
	
    public static BigInteger bigSQRT(BigInteger x) {
        BigInteger two = new BigInteger("2"), y;
        int i = 0;
        for (y = x.divide(two); y.compareTo(x.divide(y)) > 0; y = ((x.divide(y)).add(y)).divide(two), i++);
        if (x.compareTo(y.multiply(y)) == 0) {
            return y;
        } else {
            return y.add(BigInteger.ONE);
        }
    }
}

class FoundFactor {
    public static String foundIt = "";
}

class FindPrimeFactors extends Thread {

    static final BigInteger TWO = new BigInteger("2");

    BigInteger largeComposite, start, end;
    String threadName = "";
    static FoundFactor ff;

    FindPrimeFactors(BigInteger largeComposite, BigInteger start, BigInteger end, String threadName, FoundFactor ff){
        super(threadName);
        this.largeComposite = largeComposite;
        this.start = start;
        this.end = end;
        this.threadName = threadName;
        this.ff = ff; // reference to original object ;)
        start();
    }

    @Override
    public void run() { // this is where the new thread starts
        searchRange();
    }
	
    boolean searchRange() {

        long startTime = System.currentTimeMillis();
        boolean returnVal = false;
        while(true) {
            if (start.isProbablePrime(5)) {
                if (largeComposite.mod(start).bitLength() == 0) {
                    System.out.println("First prime factor is " + start );
                    System.out.println("Second prime factor is " + largeComposite.divide(start) );
                    System.out.println(threadName + " found the factors");
                    System.out.println("Time to find prime factors: " + (System.currentTimeMillis() - startTime) + " milliseconds");
                    ff.foundIt = "FOUND";
                    returnVal = true;
                    break;
                }
                if (start.compareTo(end) == 1) {
                    //System.out.println(threadName + " reached the end");
                    break;
                }
                if (Thread.currentThread().isInterrupted()) {
                    //System.out.println(threadName + " interrupted");
                    break;
                }				
            }
            start = start.add(TWO);			
        }
        return returnVal;

    }

}



Now switch back to the command prompt (CMD) and type in javac PrimeThree.java and press Enter.
Now type in java PrimeThree and press Enter.


C:\Java\PrimeThree>javac PrimeThree.java
C:\Java\PrimeThree>java PrimeThree
See video for results and more...


Final thoughts

See video.


Tutorials