Miller-Rabin Prime test (Speed is the main goal)

Question

The code below is for testing Primes.

testPrime(100000);
testPrime(1000000);
testPrime(10000000);
testPrime(100000000);

Now my goal is to make the code super fast at finding prime number, min-max, close prime. Are there any improvements that can be done to the code below to improve the speed for IsPrime?

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


class Primes {


    private static long[] as = {2, 7, 61};

    private static long modpow(long x, long c, long m) {
        long result = 1;
        long aktpot = x;
        while (c > 0) {
            if (c % 2 == 1) {
                result = (result * aktpot) % m;
            }
            aktpot = (aktpot * aktpot) % m; 
            c /= 2;
        }
        return result;
    }

    private static boolean millerRabin(long n) {
        outer:
        for (long a : as) {
            if (a < n) {
                long s = 0;
                long d = n - 1;
                while (d % 2 == 0) {
                    s++;
                    d /= 2;
                }

                long x = modpow(a, d, n);
                if (x != 1 && x != n - 1) {
                    for (long r = 1; r < s; r++) {
                        x = (x * x) % n;
                        if (x == 1) {
                            return false;
                        }
                        if (x == n - 1) {
                            continue outer;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }


    public static boolean IsPrime(long num) {
        if (num <= 1) {
            return false;
        } else if (num <= 3) {
            return true;
        } else if (num % 2 == 0) {
            return false;
        } else {
            return millerRabin(num);
        }
    }
    public static int[] primes(int min, int max) {
           ArrayList<Integer> primesList = new ArrayList<Integer>();

           for( int i=min; i<max; i++ ){
                if( IsPrime(i) ){
                   primesList.add(i);
                }
           }

           int[] primesArray = new int[primesList.size()];
           for(int i=0; i<primesArray.length; i++){
               primesArray[i] = (int) primesList.get(i);
           }

           return primesArray;
        }


    public static String tostring (int [] arr){
        String ans="";
        for (int i=0; i<arr.length;i++){
            ans= ans+arr[i]+ " ";
        }
        return ans;
    }
     public static int closestPrime(int num) {
            int count=1;    
            for (int i=num;;i++){

                int plus=num+count, minus=num-count;
                if (IsPrime(minus)){

                    return minus;

                }

                if (IsPrime(plus)) {
                    return plus;

                }
                count=count+1;
            }
        }


    }   

//end class

Answer 1

You could use the Sieve of Eratosthenes for numbers less than 10 million (you are only going up to 100 million).

I think that checking the low bit (num & 1) == 0 is quicker than checking the remainder num % 2 == 0. Similarly, bit shifting is quicker for division or multiplication by 2: d /= 2 could be d >> 1.

You might experiment with doing an initial check for division by a few low primes (3, 5, 7, 11) in your IsPrime method and see if that makes a difference.

Finally, for your "random" numbers, you might want to choose products of primes, e.g. 3*5*7*11*13..., or maybe that plus 1. Maybe that's crazy. But some "random" numbers might provide richer test cases than others, and cause a faster elimination of non-primes.

Answer 2

Java already has BigInteger.isProbablePrime(int certainty) and BigInteger.nextProbablePrime(). (There is no method to get the previous probable prime, though, so you'll need to get creative.)

That said, your Miller-Rabin implementation works remarkably quickly and accurately. Testing numbers up to 100 million, I found that it is 100% accurate in that range. To achieve 100% accuracy in that range with BigInteger.isProbablePrime(), you would need a certainty parameter of at least 9.

To obtain a list of primes within a range, you would be better off with the Sieve of Eratosthenes. For comparison, I tried generating a list of primes up to 100 million with three methods:

• Sieve of Eratosthenes (using @JavaDeveloper's implementation with bugfixes): 3 seconds
• Your primes() function: 37 seconds
• Testing BigInteger.valueOf(i).isProbablePrime(9) for i up to 100 million: ≈ 4 minutes

Answer 3

In your millerRabin() function, the calculation of s and d can be factored out of the loop, as they only depend on n, not a.

Answer 4

Several improvements: Consider that the test "if (p % 3 == 0)..." will identify 33.3% of all numbers as composite. If Miller-Rabin takes longer than three times to test whether p % 3 == 0, adding that test makes the code run faster on average. Same obviously with p % 5 == 0 and so on. You should probably check directly at least up to 100 or so.

For a 32 bit number, you'll do about 32 squaring operations modulo p. However, you can probably do at least four by just accessing a table. For example, when a = 2 any power up to 31 can be taken from a table. That saves probably 10% or more of the work.

Answer 5

Sadly nobody noticed that the whole computation is broken for big numbers due to overflow in

private static long modpow(long x, long c, long m) {
    ...
    result = (result * aktpot) % m;
    ...
}

and

private static boolean millerRabin(long n) {
    ...
    x = (x * x) % n;
    ...
}

I'd suggest changing the signature of

public static boolean IsPrime(long num)

to accept int only. And obviously changing the name to isPrime.

Answer 6

• if i<2 (one test <) is better than is if i<=1 (= test and < test)
• change String ans=""; in StringBuilder ans=new StringBuilder();
• change for (int i=0; i<arr.length;i++){ in for (int i=0,n=arr.length;i<n;i++){
• read Joshua Blosh "Effective Java" book