# Program for finding Fibonacci primes

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);
}
}
}

-

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) {
[...]
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.

-
Thanks for your useful suggestions. I just want to ask, is the code you suggested the strategy disign pattern? I have just started learning design patterns. – Jonny Shanahan Aug 19 '14 at 17:24
@JonnyShanahan yes, that's the strategy pattern (just without the concrete context class, but that is not necessarily needed) – tim Aug 19 '14 at 21:01

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");
}
}

-

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.

-

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.
-
When it gets to large numbers there will be many many primes less or equal to that number. eg the 12th fibonacci prime is 99,194,853,094,755,497. The number of primes less than this is 2,602,986,161,967,491 so my set would have to be at least this long in order to check whether it is a prime or not. At 8 bytes for each long, the set would be (99194853094755497*8)/(1024^3) = 739059247GB in size. Is this right? – Jonny Shanahan Aug 19 '14 at 16:17

• 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 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

-