3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – tb- Apr 2 '13 at 13:16
  • \$\begingroup\$ 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 \$\endgroup\$ – cl-r Sep 24 '13 at 6:28
  • \$\begingroup\$ 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. \$\endgroup\$ – Todd Lehman Jul 29 '14 at 3:42
  • \$\begingroup\$ 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. \$\endgroup\$ – Todd Lehman Jul 29 '14 at 3:56
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – maaartinus May 14 '15 at 0:27
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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:

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – maaartinus May 14 '15 at 0:17
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$
  • 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
\$\endgroup\$
  • 2
    \$\begingroup\$ "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. \$\endgroup\$ – Bakuriu Sep 24 '13 at 13:28
  • \$\begingroup\$ @Bakuriu ok! (I've not look how my Java's compiler do with <=) I was told about this optimization with Sybase requester. \$\endgroup\$ – cl-r Sep 24 '13 at 13:40
  • \$\begingroup\$ Forget about points 1 and 3. These are valid just for dumb compilers, Java can optimize such low level stuff itself. \$\endgroup\$ – maaartinus May 14 '15 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.