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\$
  • \$\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\$ – Apprentice Queue Apr 3 '12 at 7:14
  • \$\begingroup\$ @ApprenticeQueue docs.oracle.com/javase/1.4.2/docs/api/java/lang/… \$\endgroup\$ – Peđa Terzić Apr 3 '12 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\$ – Apprentice Queue Apr 3 '12 at 7:22
  • \$\begingroup\$ Have you looked at Pepin's test for testing primality? \$\endgroup\$ – Apprentice Queue Apr 3 '12 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\$ – Peđa Terzić Apr 3 '12 at 7:35
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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Would it be better to use s.multiply(s) instead of s.pow(2) ? \$\endgroup\$ – Peđa Terzić Apr 3 '12 at 6:39
  • \$\begingroup\$ Tried that one, it's actually making things worse - at least on my JDK7 -server. \$\endgroup\$ – Petr Janeček Apr 3 '12 at 6:51
  • 1
    \$\begingroup\$ BigInteger temp = s.modPow(2,F); may help a little bit, too. \$\endgroup\$ – Landei Apr 3 '12 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\$ – Petr Janeček Apr 3 '12 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\$ – Peđa Terzić Apr 4 '12 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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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