Project Euler #2 in Java

Question

Project Euler #2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here is my solution:

public class EvenFibonacciFinder {

    private static final double PHI = 1.618033989;
    private static final double _PHI = -(PHI - 1);
    private static final double SQRT_5 = Math.sqrt(5);
    private static final int MAX_NUM = 4_000_000;

    public static void main(String[] args) {
        long time = System.nanoTime();
        double max = MAX_NUM * SQRT_5;
        long sum = 0;
        for (int i = 3, result = (int) Math.round(2 * SQRT_5); result < max; result = (int) Math.round(Math.pow(PHI, i += 3) - Math.pow(_PHI, i))) {
            sum += result;
        }
        sum = Math.round(sum / SQRT_5);
        System.out.println("Result: " + sum + "\nTime used for calculation in nanoseconds: " + (System.nanoTime() - time));
    }

}

Output:

Result: 4613732
Time used for calculation in nanoseconds: 60243

Questions:

• Is this the most efficient way of doing it?
• Is there any "bad code" in the short solution?

Answer 1

Is this the most efficient way of doing it?

Sometimes the simplest solution is also the most efficient solution. I'm not sure why you decided to use Math.pow and PHI to compute something that can be easily (and more quickly) be computed with simple addition:

public class EvenFibonacciFinder {
    private static final int MAX_NUM = 4_000_000;

    public static void main(String[] args)
    {
        long time = System.nanoTime();
        int  f1   = 1;
        int  f2   = 2;
        long sum  = 0;

        while (f2 <= MAX_NUM) {
            int f3;
            sum += f2;
            // This skips three ahead in the sequence.
            f3 = f1 + f2;
            f1 = f2 + f3;
            f2 = f1 + f3;
        }
        long end = System.nanoTime();
        System.out.println("Result: " + sum +
                "\nTime used for calculation in nanoseconds: " +
                (end - time));
    }
}

Output:

Original code using pow:
Result: 4613732
Time used for calculation in nanoseconds: 9952

Using addition instead of pow:
Result: 4613732
Time used for calculation in nanoseconds: 934

(Note: both programs were modified to measure the end time before the println(), otherwise some of the string concatentation time was being counted).

Answer 2

With the amount of comments in there, it's really hard to understand. Even for the mathematically superior folk (which I am not), you need to supply more information about what your constants are, why they are needed, and how the function works.

Given the constants you have, and the way it is hard-coded, I would almost go so far as to say your code could be improved by simply:

System.out.println("Result: 4613732\nTime used for calculation in nanoseconds: 0");

;-0

It makes just as much sense as your complicated formula, and.... it produces the right result, faster.

Answer 3

There are a few minor issues with this code. Firstly, the name of the constant double _PHI is unclear; it is not obvious that this means -(PHI - 1).

Also, the for loop includes a lot of code in the parentheses. While this is valid code, it is nonstandard and hard to read. Also, you need to scroll to the right to see all of it.

Furthermore, the i += 3 buried in the for loop is hard to notice, and in general assigning variables in the middle of a method invocation is not a good idea.

This might be refactored into:

int i = 3;
int result = (int) Math.round(2 * SQRT_5);
while (result < max) {
     sum += result;
     i += 3;
     result = (int) Math.round(Math.pow(PHI, i) - Math.pow(_PHI, i));
}

Answer 4

Kudos to writing this program. The only thing that I see can be optimised is:

    Math.pow(PHI, i += 3) - Math.pow(_PHI, i)
    // PHI^(i+3) - PHI^i = PHI^i*(PHI^3-1) = PHI^i * PHI_CUBE_LESS_1 (Constant). Add comment if used.

• Wouldn't int suffice rather than using long?

Just add the wiki link in the comment for others to check the mathematical formula :)
Great work!!!

Answer 5

1. If you need to compute all Fibonacci numbers anyway, it is certainly faster to do it with a few additions than with computing powers, multiplication AND an addition.

2. The exact formula to compute fibo(i) is (phi^i - (-1/psi)^i)/sqrt(5). You can sum the (phi^i - (-1/psi)^i) and divide by sqrt(5) at the end. But it is not obvious that you can round each (phi^i - (-1/psi)^i) and later divide by sqrt(5) and round again. I think it works because of the properties of sqrt(5) and the fact that the rounding alternates between rounding up and rounding down.

3. You can replace (int)Math.round(...) by (int)(0.5+ ... ). It is much faster (by a factor 20) on my computer, I think the loop fits in the cpu cache.

4. The term (-1/psi)^i becomes very small very fast and can be ignored.