0
\$\begingroup\$

I am writing a program to calculate Mersenne primes. This code works, but it is so slow:

import java.math.BigInteger;
import java.util.Scanner;
class calculate{
    private static Scanner scanner;
    public static  boolean MPtest(int x) {
         if (x < 2) throw new IllegalArgumentException("x must be greater then 2.");
         BigInteger lucas = new BigInteger("4");    
         BigInteger two = new BigInteger("2");    
         BigInteger one = new BigInteger("1");    
         BigInteger zero = new BigInteger("0");    
         BigInteger mprime = new BigInteger("1");    
         boolean test;
         mprime= mprime.shiftLeft(x).subtract(one);
         for(int i = 1; i <= x-2; i++) {
         lucas=lucas.multiply(lucas).subtract(two).mod(mprime);
         }
         test= (lucas.compareTo(zero) == 0);
         return (boolean) test;
    };
    public static final int floorSqrt(final int x) {  
        return (int) StrictMath.sqrt(x & 0xffffffffL);  
    }   
    public static final int floorSqrt(final long x) {  
        if ((x & 0xfff0000000000000L) == 0L) return (int) StrictMath.sqrt(x);  
        final long result = (long) StrictMath.sqrt(2.0d*(x >>> 1));  
        return result*result - x > 0L ? (int) result - 1 : (int) result;  
    }  
    public static final BigInteger floorSqrt(final BigInteger x) {  
        if (x == null) return null;  
        {    
          final int zeroCompare = x.compareTo(BigInteger.ZERO);    
          if (zeroCompare <  0) return null;    
          if (zeroCompare == 0) return BigInteger.ZERO;    
        }    

        int bit = Math.max(0, (x.bitLength() - 63) & 0xfffffffe); // last even numbered bit in first 64 bits  
        BigInteger result = BigInteger.valueOf(floorSqrt(x.shiftRight(bit).longValue()) & 0xffffffffL);  
        bit >>>= 1;  
        result = result.shiftLeft(bit);  
        while (bit != 0) {  
          bit--;  
          final BigInteger resultHigh = result.setBit(bit);  
          if (resultHigh.multiply(resultHigh).compareTo(x) <= 0) result = resultHigh;  
        }  

        return result;  
    };
    private static boolean isPrime(int n){
        if (n % 2 == 0)
            return (n==2);
        if (n % 3 == 0)
            return (n==3);
        int m = (int) Math.floor(Math.sqrt(n));
        for (int i = 5; i <= m; i += 6) {
            if (n % i == 0)
                return false;
            if (n % (i + 2) == 0)
                return false;
        };
        return true;
    };
    private static boolean isBigPrime(BigInteger n){
        BigInteger two = BigInteger.valueOf(2);
        BigInteger three = BigInteger.valueOf(3);

        BigInteger nc = n;
        if (nc.mod(two) == BigInteger.ZERO)
            return (n.equals(2));
        nc = n;
        if (nc.mod(three) == BigInteger.ZERO)
            return (n.equals(3));
        BigInteger m = floorSqrt(n); //Math.floor(Math.sqrt(n));
        BigInteger six = new BigInteger("6");
                                                 /*i <= m*/
        for (BigInteger i = new BigInteger("5"); m.compareTo(i) > -1; i.add(six)) {
            nc = n;
            if (nc.mod(i) == BigInteger.ZERO)
                return false;
            nc = n;
            BigInteger i2 = i;
            i2.add(two);
            if (nc.mod(i2) == BigInteger.ZERO)
                return false;
        };
        return true;
    };
    public static void main(String args[]){
        System.out.print("Number of primes:");
        scanner = new Scanner(System.in);
        int counter = scanner.nextInt();
        long start = System.currentTimeMillis();
        for(int y = 3; y < counter; y+=2){
            if(isPrime(y)){
                BigInteger mprime = new BigInteger("1");
                mprime = mprime.shiftLeft(y).subtract(new BigInteger("1"));
                if(isBigPrime(mprime))
                    System.out.println("2^" + y + " - 1 = " + mprime);
            };
        };
        System.out.println(System.currentTimeMillis() - start + "ms");
    };
};

What would be the best way to improve this?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ You should look more into existing methods. There's BigInteger.isProbablePrime which is surely faster for big numbers. \$\endgroup\$
    – maaartinus
    Commented Sep 13, 2014 at 16:17

1 Answer 1

2
\$\begingroup\$

Bugs

BigInteger i2 = i;
i2.add(two);

This isn't right. If BigInteger were mutable, you would still change i as well. But since it isn't, you are changing neither. It should be:

BigInteger i2 = i.add(two);

The same problem here:

for (BigInteger i = five; m.compareTo(i) > -1; i.add(six)) {

For me, your program never terminates, and this is the reason why. See here for how to use BigInteger and loops. It should be:

for (BigInteger i = five; m.compareTo(i) > -1; i = i.add(six)) {

Other Improvements

What would be the best way to improve this?

Right now, I would focus on readability, and after that is taken care of, look at the performance.

Contradicting Exception Message

if (x < 2) throw new IllegalArgumentException("x must be greater then 2.");

The check and the message of this exception to not match. It should actually say that x must be greater than 1.

Static BigInteger

There is no need to create a new object every time you call a method. It makes the code slower and harder to read. Just declare all the constant BigInteger you need once:

private static BigInteger two = new BigInteger("2");
private static BigInteger three = new BigInteger("3");
private static BigInteger five = new BigInteger("5");
private static BigInteger six = new BigInteger("6");

BigInteger zero and one

BigInteger actually has a constant for zero, no need to create an object for it:

test = (lucas.compareTo(BigDecimal.ZERO) == 0);

It also has a constant for one, so you should also get rid of all the new BigInteger("1") (again, for readability and performance).

General Style

It will make your code a lot more readable if you follow general style guidelines:

  • capitalize class names (calculate -> Calculate)
  • function names should start with a lower case letter (MPtest -> mpTest, or better yet: mersennePrimeTest or isMersennePrime)
  • before and after operations and assignments should be a space (for example test= -> test =, x-2 -> x - 2, lucas=lucas -> lucas = lucas, etc)
  • no semicolon after curly brackets (}; -> }

Variable Naming

  • what's a lucas? lucas lehmer residue? In that case I would actually name it lucasLehmerResidue. It's a bit longer, but also clearer
  • if you rename your function to isMersennePrime, mprime would be fine, but it could also be mersennePrime
  • argument names: is there a reason that sometimes the argument is named n and sometimes x? If you cannot think of more expressive names, I would at least use the same
  • short variable names: nc, i2, and m don't really express what they do
  • loop variables: if there is no good reason for it, I wouldn't use y, but i

Unused functions

Why do you have MPtest when you never use it?

Unnecessary Variables

I don't see why you need nc. I would just remove it.

Unnecessary Brackets

In your return statements, you don't really need brackets. Instead of return (n==2); just write return n==2;.

Curly Brackets

Always use curly brackets, even for one-line statements, it makes code easier to read and avoids bugs.

Comments

You need more comments. Your class should have one saying what algorithm you use, as should your functions.

In my opinion, code like this:

   if ((x & 0xfff0000000000000L) == 0L) return (int) StrictMath.sqrt(x);
   final long result = (long) StrictMath.sqrt(2.0d*(x >>> 1));
   return result*result - x > 0L ? (int) result - 1 : (int) result;

would also deserve a comment or two.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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