Project Euler #2 (Fibonacci Sequence)

Challenge: 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.


Consider a Fibonacci sequence whose values do not exceed four million,
find the sum of the even-valued terms.

My solution:

import java.util.ArrayList;

public class Euler2 {
    public static void main(String[] args) {
        final long START = System.nanoTime(),
            MAX_NUM = 4000000L;
        Long result = 0L;

        ArrayList sequence = new ArrayList() {
            { add(1L); add(2L); }
        };

        int i = 0;
        Long nextTerm = sequence.get(i++) + sequence.get(i);
        while (nextTerm <= MAX_NUM) {
            sequence.add(nextTerm);
            nextTerm = sequence.get(i++) + sequence.get(i);
        }

        /* Leveraging the absence of consecutive even numbers
        and the fact that Odd + Even is Odd, and Odd + Odd is even,
        retrieve every third term after an even term until no longer possible
        */
        int j = 1;
        while (j <= i) {
            result += sequence.get(j);
            j += 3;
        }

        System.out.print("Result: " + result +
            ".\nTime used for calculation in nanoseconds: " +
            (System.nanoTime() - START) + "."
        );
    }
}

Sample output:


Result: 4613732.
Time used for calculation in nanoseconds: 1651793

• Without the cost of readability is there an adjustment that would improve performance?

• I considered doing this with Streams but decided it wasn't necessary. Was I correct or would its use offer notable enhancement?

My Assumptions about your requirements

Here are a few points, assuming that you want performance and maintainability.

Assumption: Since you did not put the generation of the sequence and the sum of the evens in separate methods, I assume that a separate generation of the sequence is explicitly not a requirement and therefore it's okay if all functionality goes into one single method.

Runtime Comparison of solutions

Runtime comparison on my machine:

• Your solution: ~950000ns

• My simple solution (no loop unrolling, same structure as your code, except for the points mentioned below): ~3300ns

• Best solution known to me: ~1700ns

Key points to improve performance of your code

without trading in maintainability.

-
The ArrayList is slowing the code down somewhat. As long as the code is interpreted, it is quite slow because interpreted method calls are slow. Once it is JIT-compiled the method calls no longer matter. Still, using ArrayList is unnecessary, as we will see below.

-
Your usage of Long for result involves unnecessary boxing / unboxing in the line result += .... Use long instead, result doesn't need to be Long. This speeds up your program by 1%.

-
You're concatenating Strings while time is still running. That tampers your time calculation. Call System.nanoTime() right after the algorithm, not later.
Also, you might want to perform the runs to your algorithm multiple times in order to rule out effects of things like the OS scheduler or the code not being JIT-compiled when you measure performance.

Details about the even check

Given the requirements, you could check the numbers to sum up right away. Why do you check the numbers later?

I believe you fell into a premature optimization pit without considering the odds of your trade. You've traded the cheap operation "n is even", which is if ((n & 1) == 0), for a very expensive one - calling virtual method add() and calling virtual method get() inside the loops.

Your observation about every third number in the Fibonacci sequence being even is correct, the conclusion for the performance optimization is wrong.

!Spoiler Alert!

Fibonacci solutions below.

The typical Fibonacci loop

The typical Fibonacci loop looks like this:

long prevprev, prev = 1, current = 1;
while (current <= MAX_NUM) {
    prevprev = prev;
    prev = current;
    current = prev + prevprev;
}

Because we shall start with 1, 2 instead of 1, 1, which produces the same sequence except that it's missing the first member, we would use current = 2 instead.

So here's how to calculate the result:

long result = 0;
long prevprev, prev = 1, current = 2;

while (current <= MAX_NUM) {
    if ((current & 1) == 0) // if (isEven(current))
       result += current;
    prevprev = prev;
    prev = current;
    current = prev + prevprev;
}

loop unrolling to skip 2/3rd of the checks.

You can still use your smartness about the even/odd/odd pattern of the Fibonacci sequence.

There is a way in which you can ensure that you only sum up the evens without using a condition. We can use loop unrolling for that. Please note that as such, loop unrolling in Java is absolutely pointless. It only helps in this case because it enables us to get rid of 2 even checks for every 3 Fibonacci numbers.
The result is not maintainable, and because of the JIT compiler being smarter than all humans except its creators and those that studied it extremely well (I haven't), we usually would never even think of loop unrolling in Java.

Here's a code fragment which demonstrates the unrolled loop:

public static long sumOfEvenFibonacciNumbersUntilMaxNum() {
    long result = 0;

    long prevprev, prev = 1, current = 2;

    // Use the fact that every third is even: 1, 1, 2, 3, 5, 8.
    // We start with 2, so the first one in three is even.
    // Sum overflow over MAX_NUM inside the loop irrelevant:
    // The values of current which are too big are not used for result.
    while (current <= MAX_NUM) {
        result += current;// even
        prevprev = prev;
        prev = current;
        current = prev + prevprev;
        prevprev = prev;
        prev = current;
        current = prev + prevprev;
        prevprev = prev;
        prev = current;
        current = prev + prevprev;
    }   
    return result;
}

This trades 6 additional assignments and 3 additional additions in the last loop for avoiding n checks of (current & 1) == 0 and reduces the number of current



• Is lsl Rn

On CPUs like ARM, on which add Rn <- Rx + Ry is available, the Add solution is fastest.
On CPUs like 80x86 or 680x0 / CPU32, on which add can only modify an existing register but not store the result in a new register, additional move instructions would be inserted for each add instruction which does not use a source register also as destination register. So the Multiply solution is faster on 80x86 and 680x0 / CPU32.

EDIT Note: The original answer contained statements abou

StackExchange Code Review Q#77124, answer score: 16