6
\$\begingroup\$

Here is a simple working Java implementation of primality test for Fermat numbers. Is there something that I could change in code to achieve a better running time?

import java.math.BigInteger;

public class FPT 
{
    public static void main(String[] args)
    {
        double n;
        n = Double.parseDouble(args[0]);

        int e = (int)n;

        if (e > 1)
        {
            double m = Math.pow(2,n);
            int k = (int)m;
            BigInteger F;
            F = BigInteger.valueOf(2).pow(k).add(BigInteger.ONE);
            BigInteger s = new BigInteger ("8");
            double o = 1;
            double a = n - o ;
            double b = Math.pow(2,a) - o;
            int c = (int)b;

            for (int i = 1; i <= c; i ++)
            {
                 s=s.pow(4).subtract(BigInteger.valueOf(4).multiply(s.pow(2))).add(BigInteger.valueOf(2)).mod(F);
            }

            if (s.equals(BigInteger.ZERO))
            {
                System.out.println("prime");
            }
            else
            {
                System.out.println("composite");
            }
        }
        else
        {
            System.out.println("exponent must be greater than one");
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ I don't understand why you are using double when you are working with integers. You do realize doubles aren't infinite precision. \$\endgroup\$ Commented Apr 3, 2012 at 7:14
  • \$\begingroup\$ @ApprenticeQueue docs.oracle.com/javase/1.4.2/docs/api/java/lang/… \$\endgroup\$
    – Pedja
    Commented Apr 3, 2012 at 7:19
  • \$\begingroup\$ That link doesn't say anything. double only supports up to around 18 digits. You should be using BigInteger throughout. Also o is a terrible variable to use because it looks like zero. If you mean a constant 1, just use 1 instead of a variable. \$\endgroup\$ Commented Apr 3, 2012 at 7:22
  • \$\begingroup\$ Have you looked at Pepin's test for testing primality? \$\endgroup\$ Commented Apr 3, 2012 at 7:31
  • \$\begingroup\$ @ApprenticeQueue I know that such test exists but I am interested in Java implementation of this LLT-like primality test for Fermat numbers... \$\endgroup\$
    – Pedja
    Commented Apr 3, 2012 at 7:35

2 Answers 2

4
\$\begingroup\$

I still can't quite figure out the way to this algorithm =/. But, from the Java point of view, you can gain 9-10% by changing your loop to:

for (int i = 1; i <= c; i ++) {
    BigInteger temp = s.pow(2);
    s = temp.pow(2).subtract(BigInteger.valueOf(4).multiply(temp)).add(BigInteger.valueOf(2)).mod(F);
}

...because the cached value can be used twice there.

Otherwise, the code is hard to read. It's not self explanatory nor commented and could be written in a better way - for a human to read, at least. But none of those changes would affect performance in any way.

EDIT: Additional 17% thanks to @Landei in comments.

for (int i = 1; i <= c; i ++) {
    BigInteger temp = s.modPow(BigInteger.valueOf(2), F);
    s = temp.pow(2).subtract(BigInteger.valueOf(4).multiply(temp)).add(BigInteger.valueOf(2));
}
s = s.mod(F);

That takes advantage of modPow() method which can do pow().mod() in one step without much additional overhead. Since the mod is not necessary to have every time, it is enough to do it in temp (that actually propagates twice into the resulting expression) and enjoy the substantial speedup. You need to add one proper mod after the loop is done, though.

\$\endgroup\$
10
  • \$\begingroup\$ Would it be better to use s.multiply(s) instead of s.pow(2) ? \$\endgroup\$
    – Pedja
    Commented Apr 3, 2012 at 6:39
  • \$\begingroup\$ Tried that one, it's actually making things worse - at least on my JDK7 -server. \$\endgroup\$ Commented Apr 3, 2012 at 6:51
  • 1
    \$\begingroup\$ BigInteger temp = s.modPow(2,F); may help a little bit, too. \$\endgroup\$
    – Landei
    Commented Apr 3, 2012 at 11:32
  • \$\begingroup\$ That was, actually, a very good idea! Gonna edit it into answer - if you would like to make your own, feel free to do so :) \$\endgroup\$ Commented Apr 3, 2012 at 13:18
  • 1
    \$\begingroup\$ @Slanec Those numbers are composite for sure...the smallest Fermat number with unknown primality status is a F(33)...by the way see this question... \$\endgroup\$
    – Pedja
    Commented Apr 4, 2012 at 11:17
0
\$\begingroup\$

Some basic optimalizations:

The reverse for: for (int i = c - 1; i >= 0; c--) should be a little faster. Java has a special instruction for comparing with zero. No need to compare two local variables.

Another thing is that every method call is slow. Better to put every constant BigInteger.valueOf(4) to a local variable first: BigInteger four = BigInteger.valueOf(4);

I don't guarantee a faster code - with modern Java optimalizations and JIT it's possible that these optimalizations are done automatically by compiler.

\$\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.