Program for finding Fibonacci primes

Question

I think it could have been designed with more object orientation. I don't like how one of my methods calls another from within the method, but I wasn't sure how to return the result because it is a loop.

Also is it ok to have all methods static, or should I be instantiating the classes?

If there is any other improvements please let me know, but these were my main concerns.

App.java:

public class App {

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();

        Fibonacci.fibonacci();

        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;

        System.out.println("****************************************\n");
        System.out.println("Total Running Time: " + totalTime + "ms");
    }
}

Fibonacci.class:

public class Fibonacci {

    static void fibonacci() {
        long i = 0;
        long j = 1;
        long k = 0;
        while (i < 1E17) {
            k = i + j;
            i = j;
            j = k;
            Prime.prime(k);
        }
    }
}

Primes.java:

public class Prime {

    static void prime(long number) {

        boolean isPrime = false;

        long end = (long) (Math.sqrt(number) + 1);
        for (long i = 2; i <= end; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            } else {
                isPrime = true;
            }
        }
        if (isPrime) {
            System.out.println(number);
        }
    }
}

Answer 1

Object Oriented

I wouldn't call your code object oriented. And yes, using static in too many places can be a hint that you are not using OOP correctly.

But your program is so small and specific that this isn't really a bad thing. If you actually have some extension in mind, a different approach might be better, but right now, I would leave it as it is.

But for example, lets say you plan to write a program in the future which prints every odd Fibonacci number, or every Fibonacci number dividable by 3. With your code, this might be harder to do.

If your approach was like this:

public class Fibonacci {
    static void fibonacci(NumberCheck numberCheck) {
        [...]
        // instead of Prime.prime(k); call:
        if (numberCheck.meetsContition(k)) {print(k)}
    }
}

interface NumberCheck {
    boolean meetsContition(int number);
}

public class Prime implements NumberCheck {
    @Override
    boolean meetsContition(int number) {
        // check if number is prime, return true or false
    }
}

public class Odd implements NumberCheck {
    @Override
    boolean meetsContition(int number) {
        // check if number is odd, return true or false
    }
}

It would be easily extendable. But as I said, if you are not planning on extending your code, you don't really need OOP in this case. I wouldn't even create the Fibonacci and Prime classes, they are more confusing than they are helpful, just put the methods in App.

Naming

prime should better be called isPrime, and I would find it easier to read if it then returned true or false (move the printing to fibonacci).

Other

I would pass an argument to fibonacci for up to which number it should run. Just hardcoding 1E17 is bad style.

Answer 2

The current design is not object-oriented, but why do you want object-orientation? Why would you need it?

Object-orientation is a software design paradigm, that helps people reason about software by applying structures that are familiar to them. This is the basic underlying principle. People often think about the world in terms of "things" that have "properties" or "features", and having these same structures in programs helps to understand them better.

A lot of nice features that goods software should have (like extensibility and maintainability) stem from much more general principles like modularity, loose coupling and single responsibility principle. Object-orientation supports and promotes these principles (like many other programming paradigms) but they're not the defining features of object-orientation.

Looking at your code, I think it is more important to separate the prime-check from the printing of the result (Single Responsibility Principle). This can easily be done by changing the method to boolean isPrime(Number). This method could easily live as a static method in a utility class, since its implementation is not likely going to be changed or extended.

The fact that the fibonacci method calls the prime check directly could also be improved (Tight Coupling). An improved design could see the Fibonacci sequence as an unlimited number generator. You could use the Iterator<Number> in Java (other languages have similar constructs) to model this.

class Fibonacci implements Iterator<Long> {

  private long last = 0, next = 1;
  public Long next() {
    long current = next;
    next += last;
    last = current
    return current;
  }

  public boolean hasNext() {return true;}
}

Now your main method can use the Fibonacci iterator/sequence to continuously generate the next number, use the utility method to check prime-ness and print accordingly. Note that stopping execution after a number of iterations is also the responsibility of the main method.

public class App {
  public static void main(String[] args) { 
    long startTime = System.currentTimeMillis();
    int max = Integer.parseInt(args[0]), i = 0;
    Fibonacci fibonacci = new Fibonacci();
    while (i++ < max) {
      long number = fibonacci.next();
      if (Prime.isPrime(number)) {
        System.out.print(number);
        System.out.print(" ");
      }
    }
    long endTime = System.currentTimeMillis();
    long totalTime = endTime - startTime;
    System.out.println("****************************************\n");
    System.out.println("Total Running Time: " + totalTime + "ms");
  }
}

Answer 3

The big problem I see, is that your classes/methods are single use. Your class Prime can nothing but print. But in any bigger real program, you need the parts to cooperate somehow.

This printing destroy any flexibility. Imagine a tiny change like printing into a file. Impossible. Counting instead of printing. Impossible. Switching between counting and printing. Impossible.

Compare it to what Maarten Winkels wrote. His method boolean Prime.isPrime does exactly the right thing. Nicely reusable.

Sticking with the Single Responsibility Principle would prevent you from testing and printing in the same method. But before your master it, remember: A reusable method computing anything must return some result, or modify some data, or alike. Never print.

Answer 4

An efficiency comment.

The code wastes much time testing a primality of numbers which are known in advance to fail the test: a Fibonacci number with a composite index is composite. A primality test itself is quite suboptimal. These observations suggest a totally different approach:

1. Create a set of primes using any sieve you prefer.
2. Only test Fibonacci numbers with index belonging to that set (in fact, you may get away not even calculating the rest of them)
3. A primality test is just a set lookup.

Answer 5

Keep Concerns Separated

Your code structure conflates several things:

• Generating the Fibonacci sequence
• Checking if a number is prime or not
• Printing the numbers of interest

It's best to use a structure that keeps these concerns separated. You can then arrange them in a multitude of ways to accomplish different tasks.

For example, suppose you want to find the squares of Fibonacci primes, or you want to place the primes you find in a database so you can retrieve them later. Also, others have suggested algorithmic changes. All these changes will be easier to implement if your code is modular. But, more importantly, it allows the different parts to be reused.

A Functional Approach

In this particular case, I think you would benefit from a paradigm shift from object-oriented programming to functional programming. There are varying definitions of functional programming. For our purposes here, we'll simply say that functional programming deals with the abstraction of composing functions (in contrast to the object-oriented approach, which deals with the abstraction of composing objects).

Note that this is purely a shift in our way of thinking about the problem. You can express any "object oriented" program in terms of functions and vice versa -- loosely speaking, objects and functions are isomorphic.

Here's how we can decompose this problem using functional principles:

• Generate an "infinite" stream of Fibonacci numbers
• Filter the stream of Fibonacci numbers to include only primes
• Print numbers from the filtered stream

You could implement all this yourself (c.f., the NumberCheck interface in Tim's answer and Java 8's Predicate interface, used below). However, we don't have to re-invent the wheel. There are multiple libraries for functional programming in Java, and Java 8 has added functional APIs to the standard. Here's one way we to map this to the functional programming abstractions provided in Java 8:

• Implement the Fibonacci sequence as a Stream.
• filter the Fibonacci stream with a prime check Predicate, to generate a new stream with only Fibonacci primes
• Print each number in the stream of Fibonacci primes

Dealing with Large Numbers

The numbers of the Fibonacci sequence grow exponentially. It will not take long before long values are insufficient to compute Fibonacci numbers. To compute larger numbers, you will need to use an arbitrary-precision number type such as BigInteger.

Algorithmic Improvements

There are several ways in which you can perform the computation more efficiently:

• Your prime checker requires \$O(\sqrt{n})\$ time, where \$n\$ is the number being checked. In the overall algorithm, though, \$n\$ grows exponentially. So checking the \$k\$th fibonacci number takes \$O(2^n)\$ time. Using a sieve, as suggested by vnp, will help reduce the constant factor, but will not help with the asymptotic complexity. Ultimately, you will have to resort to a probabilistic prime check as suggested by Danaj.

• As both vnp and Danaj point out, the \$k\$th Fibonacci number cannot be prime if \$k\$ is not also prime (excluding \$k = 4\$). Thus, we can structure our program as follows (modulo the case when \$k = 4\$ -- I leave that as an exercise for the reader):

  • Generate a Stream of natural numbers
  • Filter the natural numbers, producing a Stream of primes
  • map each prime \$k\$ to the \$k\$th Fibonacci number
  • Filter this stream once more for primes, producing a Stream of Fibonacci primes
  • Print the Fibonacci primes

  Note how we only need to change the way we generate Fibonacci numbers to compute the \$k\$th Fibonacci number directly instead of generating a Stream of the Fibonacci sequence. The rest is just making a few tweaks to the way we compose our pipeline of functions. Regardless of paradigm, this is the sort of modularity sought by good engineering principles.

• Since we are now calculating the \$k\$th Fibonacci number directly, we can use an \$O(\log n)\$ algorithm to calculate the Fibonacci numbers. See, e.g., matrix form and SICP Ex. 1.19.

Answer 6

Expanding on vnp's answer:

• Excepting \$k=4\$, all prime \$F_k\$ have a prime \$k\$. If your prime function returned a boolean rather than printing the result, you could use this to quickly skip lots of candidates (testing primality on \$k\$ is cheap, but not so for \$F_k\$).

• There are faster primality tests which you'll probably have to use. Trial division is fast for small values but is exponential time in the size of the input. This isn't going to really work past the 12th Fibonacci prime (\$F_{131}\$ has 28 digits). On the other hand, get it working first is a good idea. You will probably end up with a probable prime test like BPSW or many random-base Miller-Rabin tests.

• Like you, I read vnp's answer (regarding sets) as useful for \$k\$ but not for \$F_k\$.

Once happy with what you have, you may find it entertaining to look at some other solutions, e.g. Haskell, Perl serial / parallel, PARI and Mathematica

Additional info Dec 2016:

Example times for fast implementation in serial, time for first n Fibonacci primes:

• 18.2 seconds for 26 (\$F_{9677}\$)
• 4776 seconds for 32 (\$F_{50833}\$)

In parallel with EC2 c4.8xlarge (36 core):

• 1.8 seconds for 26 (\$F_{9677}\$)
• 323 seconds for 32 (\$F_{50833}\$)
• 12009 seconds for 36 (\$F_{148091}\$)

It's possible to improve on this using gwnum instead of GMP. The former is much faster at compositeness tests for large inputs (over 4000 digits). The downside is that programming correctly using it is much harder than GMP. Typical use in 2016 would be using something like the GMP program to do the selection and sieving to output candidates, then use a script running PFGW to weed out composites using its fast Fermat test, then using GMP again for a good primality test on the results to confirm.