More efficient solution: Project Euler #2: Even Fibonacci Numbers

Question

Problem:

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.

My code: (which works fine)

public static void main(String[] agrs){
    int prevFirst=0;
    int prevSecond=1;
    int bound=4_000_000;
    int evenSum=0;

    boolean exceed=false; //when fib numbers > bound
    while(!exceed){
        int newFib=prevFirst + prevSecond;
        prevFirst = prevSecond;
        prevSecond = newFib;

        if(newFib > bound){
            exceed=true;
            break;
        }

        if(newFib % 2 == 0){
            evenSum += newFib;
        }
    }

    System.out.println(evenSum);

}

I'm looking for a more efficient algorithm to do this question. Any hints?

Answer 1

When taking the following rules into account:

even + even = even

even + odd = odd

odd + even = odd

odd + odd = even

The parity of the first Fibonacci numbers is:

o o e o o e o o e ...

Thus basically, you simply need to do steps of three. Which is:

(1,1,2)
(3,5,8)
(13,21,34)

Given (a,b,c) this is (b+c,b+2*c,2*b+3*c).

This means we only need to store the two last numbers, and calculate given (a,b), (a+2*b,2*a+3*b).

Thus (1,2) -> (5,8) -> (21,34) -> ... and always return the last one.

This will work faster than a "filter"-approach because that uses the if-statement which reduces pipelining.

---

The resulting code is:

int b = 1;
int c = 2, d;
long sum = 0;
while(c < 4000000) {
    sum += c;
    d = b+(c<<0x01);
    c = d+b+c;
    b = d;
}
System.out.println(sum);

Or the jdoodle (with benchmarking, takes 5 microseconds with cold start, and on average 50 nanoseconds, based on the average of 1M times). Of course the number of instructions in the loop is larger. But the loop is repeated one third of the times.