Speeding up Mersenne prime generator

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;
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?

• You should look more into existing methods. There's BigInteger.isProbablePrime which is surely faster for big numbers. Commented Sep 13, 2014 at 16:17

Bugs

BigInteger i2 = i;


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.

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

• 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.

   if ((x & 0xfff0000000000000L) == 0L) return (int) StrictMath.sqrt(x);