CODEWITHSUNDEEP
javawhile-loopfibonacci
Bluefire
Bluefire

Reputation: 14109

Sum of all even Fibonacci numbers code never stops - Java

This is from project Euler, problem 2. I wrote the following seemingly innocent code:

public class FibonacciEven {
    public static void main(String[] stuff) {
        long sum = 0;
        int i = 0;
        while(fib(i) <= 40) {
            boolean even = fib(i) % 2 == 0;
            if(even) {
                sum += fib(i);
            }
            else {
                continue;
            }
            i++;
        }
        System.out.println(sum);
    }
    public static long fib(int n) {
        long prev1 = 0;
        long prev2 = 1;
        for(int i = 0; i < n; i++) {
            long savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1 + prev2;
        }
        return prev1;
    }
}

I did read about how the Java method for working out Fibonacci numbers is quite memory hungry, but, as you can see, I scaled my limit down to 40, and it still doesn't get to the end, so I assume that I have gotten some syntax horribly wrong. What bit of the code is making it run forever? And if all of this really is due to the fact that the method takes so much time to run, can anyone suggest a better way?

EDIT: ok, now my code looks like this:

public class FibonacciEven {
    public static void main(String[] stuff) {
        long sum = 0;
        int i = 0;
        while(fib(i) <= 40) {
            boolean even = fib(i) % 2 == 0;
            if(even) {
                sum += fib(i);
            }
            i++;
        }
        System.out.println(sum);
    }
    public static long fib(int n) {
        long prev1 = 0;
        long prev2 = 1;
        for(int i = 0; i < n; i++) {
            long savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1 + prev2;
        }
        return prev1;
    }
}

This time it ignores the 2 (index 3) in the Fibonacci sequence.

Upvotes: 0

Views: 2218

Answers (4)

chaosguru
chaosguru

Reputation: 1983

I think the problem is initially for i=0 case it boolean returns false and it is executing the
else part , try incrementing the i value in both if or else.

if(even) {
            sum += fib(i);
i++;
        }
        else {
      continue;
  i++;
      }

Upvotes: -3

duffymo
duffymo

Reputation: 308763

You're also redoing a lot of work every time. I'd recommend memoizing the previously calculated values as you have them. That and recursion are your friends here.

enter image description here

I'd say this would be far more efficient than looping every time.

Upvotes: 2

Adam Sznajder
Adam Sznajder

Reputation: 9206

You can always try to compute numbers in much more efficient way. Here is a quite good description how to do this in O(nlogn): http://blog.codility.com/2012/03/omicron-2012-codility-programming.html

(Problem in this link is much more complicated but the method of computing Fibbonacci numbers is the same)

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500485

If even is false, you end up continuin without updating i - so it'll loop round again and do exactly the same work again, so even will be false again, etc...

I suspect you just want to take out the else block.

Upvotes: 5

Related Questions