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

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) ){
}
}

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

• Profile it and look where you spent most of the time. I would expect the modpow function., which is not that easy to further optimize.
– tb-
Apr 2 '13 at 13:16
• perhaps if (a < n) { continue;} is better no jump to end of if statement before going to loop, but it would depends on compiler clerverness
– cl-r
Sep 24 '13 at 6:28
• Is c % 2 == 1 in Java guaranteed to optimize down to the same as c & 1 == 0? The reason I ask is because the type of c is long, which is signed, so this might force the JVM to use an actual divide-by-2-and-get-remainder operation rather than simply a boolean 'and' operation to extract the least-significant bit. If so, the speed difference is likely to be very minimal, but it still might be worth profiling things to check. Also, c /= 2 could be written as c >>>= 1. Jul 29 '14 at 3:42
• By the way, since this is a code review question, I would suggest a comment pointing the reader to en.wikipedia.org/wiki/Miller_rabin or some such page explaining where the list { 2, 7, 61 } comes from, and what the limitations are on your input. Jul 29 '14 at 3:56
• @ToddLehman I'm sure Java optimizes the division by 2 even for signed operands, but it's slower. Together with the zero test it could be optimized without the adjustment, but I don't know i it happens. May 14 '15 at 0:27

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.

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
• It's provably 100% accurate for numbers below 4,759,123,141. But sadly (as nobody noticed) it's totally broken for big numbers due to overflow. May 14 '15 at 0:17

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.

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.

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.

• 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
• "if i<2 (one test <) is better than is if i<=1 (= test and < test)" AFAIK this is completely false. <= does not need to perform two comparisons, it will simply call a different conditional jump instruction at the machine level, which uses a slightly different circuit which takes exactly the same time to perform the comparison(keep in mind that if the difference in timing is too small then it's like if it were 0 since pipelines compute in steps of clock_time/pipeline_steps seconds. Sep 24 '13 at 13:28
• @Bakuriu ok! (I've not look how my Java's compiler do with <=) I was told about this optimization with Sybase requester.
– cl-r
Sep 24 '13 at 13:40
• Forget about points 1 and 3. These are valid just for dumb compilers, Java can optimize such low level stuff itself. May 14 '15 at 0:22