# How can I make this primality test algorithm faster?

Is it possible to make this algorithm faster ? Algorithm represents primality test for Wagstaff numbers .

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;

public class WPT
{
public static void main(String[] args)
{
int n;
n = Integer.parseInt(args[0]);

BigInteger m;
m = BigInteger.valueOf(n);

BigDecimal a = new BigDecimal("1.5");
BigDecimal b = new BigDecimal("5.5");
BigDecimal c = new BigDecimal("13.5");
BigDecimal d = new BigDecimal("16.5");

BigDecimal s;
BigDecimal r;

if (m.mod(BigInteger.valueOf(4)).equals(BigInteger.ONE))
{
s = a;
r = a;

} else {
if (m.mod(BigInteger.valueOf(6)).equals(BigInteger.ONE))
{
s = b;
r = b;

} else {
if (m.mod(BigInteger.valueOf(12)).equals(BigInteger.valueOf(11)) &&
(m.mod(BigInteger.valueOf(10)).equals(BigInteger.valueOf(1))) ||
m.mod(BigInteger.valueOf(10)).equals(BigInteger.valueOf(9)))
{
s = c;
r = c;

} else {
s = d;
r = d;

}
}
}

BigDecimal W;

int k = (n-1)/2;

for (int i = 1; i <= k; i ++)
{

}

if (s.equals(r))

{
System.out.println("prime");

} else {

System.out.println("composite");

}
}
}


very fast corresponding Mathematica code :

p = 269987;
W = (2^(p) + 1)/3;
If[Mod[p, 4] == 1, a = 3/2, If[Mod[p, 6] == 1, a = 11/2,
If[Mod[p, 10] == 3 || Mod[p, 10] == 7, a = 33/2, a = 27/2]]];
For[i = 1; s = a, i <= (p - 1)/2, i++,
s = Mod[ChebyshevT[4, s], W]];
If[s == a, Print["prime"], Print["composite"]];

– user
Commented Mar 28, 2012 at 17:17

Avoid dealing with BigDecimals at all costs - they are slow. I changed the formula to work with "twice the number", so my s is actually 2*s. Further keep the numbers in the loop small by "modding" the intermediate results, too. Finally I tried to simplify the syntax and the initial conditions for s a little bit.

import java.math.BigInteger;

public class WPT {

private final static BigInteger _1 = BigInteger.ONE;
private final static BigInteger _2 = _(2);
private final static BigInteger _4 = _(4);

public static BigInteger _(long n) {
return BigInteger.valueOf(n);
}

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);

BigInteger m = _(n);

BigInteger s =
(m.mod(_(4)).equals(_1)) ? _(3) :
(m.mod(_(6)).equals(_1)) ? _(11) :
(m.mod(_(12)).equals(_(11)) &&
(m.mod(_(10)).equals(_1)) ||
m.mod(_(10)).equals(_(9))) ? _(27) : _(33);
BigInteger r = s;

int k = (n - 1) / 2;

for (int i = 0; i < k; i++) {
BigInteger s2 = s.modPow(_2, W);
BigInteger s4 = s2.modPow(_2, W);
}

System.out.println(s.equals(r) ? "prime" : "composite");
}
}

• Thanks , your code is faster than my own but it is significantly slower than corresponding Mathematica code . I am a bit surprised with this fact . Commented Mar 28, 2012 at 10:22
• Mathematica has probably more efficient algorithms, and BigInteger is immutable, so you have some object creation overhead for intermediate results. You can try out other integer implementations (e.g. Xint from github.com/PeterLuschny/Fast-Factorial-Functions , but I don't know if it has all needed operations) Commented Mar 28, 2012 at 10:59
• Java does not know how optimyse ?: intricated if, so try to replace it with a traditionnal if{.. ;} else {.. ;} model.
– cl-r
Commented Dec 3, 2012 at 13:33

Starting from Landei's solution, you can start without using BigInteger if n is a positive int. The only operation used is modulo, so it should pay off to stay with the primitive data types as long as possible.

import java.math.BigInteger;

public class WPT {

private final static BigInteger _2 = _(2);
private final static BigInteger _4 = _(4);

public static BigInteger _(long n) {
return BigInteger.valueOf(n);
}

public static void main(String[] args) {
final int n = Integer.parseInt(args[0]);

final BigInteger r = _(
n % 4 == 1
? 3
: n % 6 == 1
? 11
: n % 12 == 11 && (n % 10 == 9 || n % 10 == 1)
? 27
: 33
);

final int k = (n - 1) / 2;
BigInteger s = r;
for (int i = 0; i < k; i++) {
BigInteger s2 = s.modPow(_2, w);
BigInteger s4 = s2.modPow(_2, w);

I wonder if you compare the time by executing the code in Mathematica vs starting the java program. That would be rather unfair, as Java always has to start up the virtual machine and load all the classes needed for the runtime. For a fair comparison, you should time the execution inside the main method. I this will become a server, you should run it a few times before you time it - the code gets optimized after some runs and the execution becomes even faster. It also depends on the version of Java. A 64 bit JVM is often faster, newer versions may also improve the execution speed.