Speeding up Mersenne prime generator

Question

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?

• maaartinus: You should look more into existing methods. There's BigInteger.isProbablePrime which is surely faster for big numbers.

Answer 1

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.