current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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;
          W = BigDecimal.valueOf(2).pow(n).add(BigDecimal.ONE).divide(BigDecimal.valueOf(3));

          int k = (n-1)/2;


           for (int i = 1; i <= k; i ++)
    {
   s = s.pow(4).multiply(BigDecimal.valueOf(8)).subtract(s.pow(2).multiply(BigDecimal.valueOf(8))).add(BigDecimal.ONE).remainder(W).setScale(1, BigDecimal.ROUND_UP);


     }


     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"]];
share|improve this question
1  
Please use consistent indentation –  user Mar 28 '12 at 17:17

2 Answers 2

up vote 3 down vote accepted

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;

        BigInteger W = _2.pow(n).add(_1).divide(_(3));

        int k = (n - 1) / 2;

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

        System.out.println(s.equals(r) ? "prime" : "composite");
    }
}
share|improve this answer
    
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 . –  pedja Mar 28 '12 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) –  Landei Mar 28 '12 at 10:59
    
Java does not know how optimyse ?: intricated if, so try to replace it with a traditionnal if{.. ;} else {.. ;} model. –  cl-r Dec 3 '12 at 13:33
up vote 1 down vote

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 BigInteger w = BigInteger.ONE.add(_2.pow(n)).divide(_(3));

        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);
            s = s4.subtract(s2.multiply(_4)).add(_2).mod(w);
        }

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

That's next to nothing, though. But a nice gain in readability.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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