Code works extremely slowly and does not print output

Question

I'm working on Project Euler problem #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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My code:

public class Two {

public static void main(String[] args) {
    Two obj = new Two();
    int sum = 0, i = 1;

    while (obj.fibonacci(i) < 4000001) {

        if (obj.fibonacci(i) % 2 == 0) {
            sum += obj.fibonacci(i);
            i++;
        }

    }
    System.out.println(sum);

}

public int fibonacci(int n) {
    if (n == 0) {
        return -1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 3;
    } else {
        return fibonacci(n-1)+fibonacci(n-2);

    }
}
}

Please help me that what is wrong with this code that when I run it. It doesn't show the output on the console and the total time will be over than 5 minutes

Thanks

Answer 1

You're stuck in an infinite loop there as you're only increasing i when its mod 2 is equal to 0. You need to move your i++ lower.

 while (obj.fibonacci(i) <= 4000000) {

        if (obj.fibonacci(i) % 2 == 0) {
            sum += obj.fibonacci(i);
        }   
        i++;
    }

As other comments have metioned, this isn't the best way to solve the fibonacci problem, but it solves your error/problem. You should walk this through a debugger if you don't see why and you'll notice you use a lot of recursive calls which have already been solved. Since you're calling it numerous times in the code, (in the while statement and in the if statement) you've increased your processing time.

Here is a sample of your fibonacci calls, notice how you call the fibonacci method on the same number multiple times:

1
2
3
2
1
4
3
2
1
2
5

Answer 2

hm, i think the question in already ambiguus. the sum of all even valued should be below 4 million, or should the biggest even valued number be below 4 million?

Answer 3

One of your problems is that you're excessively using recursion. You should try to store results to avoid to recalculate everything every time.

Answer 4

Although you solution might work, it is quite expensive as it recalculates results already obtained.

Using recursion in this case, to have the value of fibonacci(4), you recursively add the values of fibonacci(3) and fibonacci(2), which you already calculated previously.

Try with storing your values in a list instead of recomputing all the time:

List<Long> fibonacci = new ArrayList<Long>();

// First terms
fibonacci.add(-1L); // 0 is dummy, sequence starts at 1
fibonacci.add(1L);
fibonacci.add(2L);

for (int i = 3; fibonacci.get(i - 1) + fibonacci.get(i - 2) < 4000001; i++) {
    long u = fibonacci.get(i - 1) + fibonacci.get(i - 2);
    fibonacci.add(i, u);
}

Using this technique, you can compute the Fibonacci sequence up to 4000000 in less than 2 seconds (as I tried on my computer).

Then, just add some code to compute the sum inside the loop :-)

Answer 5

As mentioned, the i++ needs to be moved outside the check for eveness or you'll be stuck in a loop.

But you have a slightly bigger problem. The fibonacci sequence starts with

...1, 2, 3, ...

where instead you have ...1, 3, ... which means you get incorrect results. You should have:

// ...
if (n == 2) {
    return 2;
// ...

Answer 6

I think you can improve fibonacci next way:

def fib(x)
        if(x==0 or x==1) then
                return x;
        end
        a,b = 0,1
        (x-1).times{ a,b = b,a+b; }
        return b;
end

In other words convert recursion to iteration.

Answer 7

There's no reason to store the whole sequence of Fibonacci numbers in this case. You can simply "walk" along the sequence with a few local variables, summing as you go.

int fib2 = 0, fib1 = 1, fib0 = fib1 + fib2;
int sum = 0;

while (fib0 <= N)
{
    if (fib0 % 2 == 0) sum += fib0;
    fib2 = fib1;
    fib1 = fib0;
    fib0 = fib1 + fib2;
}

Answer 8

An improvement on @Blastfurnace's solution is to note that every third value is even.

public static void main(String[] args) {
    long sum = 0;
    int runs = 30000;
    for (int i=0;i< runs;i++) {
        sum = sumEvenFib();
    }
    long start = System.nanoTime();
    for (int i=0;i< runs;i++) {
        sum = sumEvenFib();
    }
    long time = System.nanoTime() - start;
    System.out.println(sum+" took "+time/runs+" ns avg");
}

private static long sumEvenFib() {
    int sum = 0;
    for(int f1 = 1, f2 = 2;f2 < 4000001;) {
        sum += f2;
        int f3 = f1 + f2;
        f1 = f3 + f2;
        f2 = f1 + f3;
    }
    return sum;
}

On my old labtop this takes about 40 ns. or 0.000000040 seconds.