11
\$\begingroup\$

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?
\$\endgroup\$
  • 1
    \$\begingroup\$ Using the golden ratio to calculate Fibonacci numbers. Slick. +1 \$\endgroup\$ – RubberDuck Dec 23 '14 at 2:58
  • 1
    \$\begingroup\$ result = (int) Math.round(Math.pow(PHI, i += 3) - Math.pow(_PHI, i)). Do you know if java specifies an evaluation order for the increment? I'm not sure which value of i is passed to the second Math.pow \$\endgroup\$ – FDinoff Dec 23 '14 at 3:29
  • \$\begingroup\$ @FDinoff It does. Otherwise, my answer will be incorrect (which it isn't). \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 3:30
  • 3
    \$\begingroup\$ @MannyMeng If it works but it isn't clear what's happening, it's often a sign you need to refactor something. Clarity is generally a good thing. \$\endgroup\$ – Holloway Dec 23 '14 at 11:26
  • \$\begingroup\$ When going for really big Fibonnaci numbers it's possible to use the fact that fsquared can be calculated. You would have to prepare the calculation so you end up at the exact fib you want, but it can massively reduce the number of calculations necessary. \$\endgroup\$ – MrFox Dec 23 '14 at 11:30
20
\$\begingroup\$

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).

\$\endgroup\$
  • 6
    \$\begingroup\$ Agreed; the explicit mathematical formula is more elegant, but for a computer, it's more difficult to calculate. \$\endgroup\$ – gengkev Dec 23 '14 at 6:22
  • 5
    \$\begingroup\$ Wow. I'm a little surprised at the dramatic difference. Goes to show that what's easier for a person isn't always easier for a machine. \$\endgroup\$ – RubberDuck Dec 23 '14 at 12:25
  • 4
    \$\begingroup\$ It should be pointed out that the timing mechanism used for measuring this performance is essentially useless... micro-benchmarking on code that has not 'warmed up' leads to misleading diagnostics \$\endgroup\$ – rolfl Dec 23 '14 at 13:14
  • 2
    \$\begingroup\$ @rolfl Is it the timing mechanism itself or would he want move his code to a method, call the method a few times to "warm-up" then start the timer and use that result? Is this because of memory caching or is there more to it? \$\endgroup\$ – DoubleDouble Dec 23 '14 at 15:55
  • 1
    \$\begingroup\$ @DoubleDouble a combination of both. It's very hard to benchmark effectively as the JVM has a habit of loading classes and JITing things as it goes. Even with warmup, there is no guarantee that the JVM won't decide to load/compile a whole host of seemingly unrelated stuff randomly. A benchmarking tool like caliper will actually monitor the activity of the underlying JVM to deal with these issues. \$\endgroup\$ – Boris the Spider Dec 23 '14 at 18:02
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Interesting way to look at my code. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 2:50
4
\$\begingroup\$

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));
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Hi. Welcome to Code Review! It looks like you left an extra i += 3 in your code. Presumably you meant the one with PHI to be just i. \$\endgroup\$ – Brythan Dec 23 '14 at 7:23
  • 1
    \$\begingroup\$ At first glance, I thought the same thing about _PHI, but once you understand that it's the negative inverse of Phi, I think it makes just as much sense as PHI_NEGATIVE_INVERSE or NEGATIVE_INVERSE_PHI. \$\endgroup\$ – RubberDuck Dec 23 '14 at 12:22
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ If MAX_NUM is less than 4, the solution is 0, in which is supposed to be: 0, 1, 1, 2, 3, 5... Can you see any even numbers before the fourth number? \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 3:41
  • \$\begingroup\$ What abt <=4? Could you check that once. The output should be 2. \$\endgroup\$ – thepace Dec 23 '14 at 7:13
  • \$\begingroup\$ 4 will result in 2. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 17:10
  • \$\begingroup\$ I must have missed something. Will take that point out. :) \$\endgroup\$ – thepace Dec 23 '14 at 17:57
2
\$\begingroup\$
  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.

\$\endgroup\$
  • \$\begingroup\$ Comment to #2: That is exactly what I did. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 17:09
  • \$\begingroup\$ @MannyMeng Yes, I was only questioning the rounding. \$\endgroup\$ – Florian F Dec 23 '14 at 23:49

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.