Project Euler #2 (Fibonacci Sequence)

Question

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<Long> sequence = new ArrayList<Long>() {
            { 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

1. Without the cost of readability is there an adjustment that would improve performance?
2. I considered doing this with Streams but decided it wasn't necessary. Was I correct or would its use offer notable enhancement?

Answer 1

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 <= MAX_NUM checks by 3.

If you think that this unrolled loop looks like it can be optimized further, you're right, we can actually optimize the loop logic, see next step.

Further algorithmic analysis

The Fibonacci calculation is a window of three numbers over the Fibonacci sequence with the current number F(n) and two precursors F(n-1) and F(n-2) for remembering the intermediate results in order to perform the production of F(n) := F(n-1) + F(n-2).

You noticed correctly, that every third member of the Fibonacci sequence is even.

This happens to be the same size as the window that we need to move in order to perform the calculation. We can utilize this. As always, good naming helps. Therefore, let's change the names of the variables as well.

public static long sumOfEvenFibonacciNumbersUntilMaxNum() {
    long sumOfEvens = 0;
    long odd1, odd2 = 1, even = 2;

    while (even <= MAX_NUM) {
        sumOfEvens += even;
        odd1 = even + odd2;
        odd2 = odd1 + even;
        even = odd2 + odd1;
    }   
    return sumOfEvens;
}   

Given the self-explanatory variable names and the comment, I claim this still is perfectly well maintainable code. The only drawback is that it cannot generate the Fibonacci sequence separately. Hence my initial assumption about the requirements.

P.S.: Of course we'd make MAX_NUM a parameter, I just didn't discuss this because I think it's completely irrelevant for the problem and obvious to the typical audience of this class of problem.

Comparison of the add solution with the multiply solution.

There also exists a solution which uses the fact that you can generate the sequence of evens without the intermediate odds.

Let's compare them.

// Add alternative
public static long sumOfEvenFibonacciNumbersUntilMaxNum() {
    long sumOfEvens = 0;
    long odd1, odd2 = 1, even = 2;

    while (even <= MAX_NUM) {
        sumOfEvens += even;
        odd1 = even + odd2;
        odd2 = odd1 + even;
        even = odd2 + odd1;
    }
    return sumOfEvens;
}


// Multiply alternative
public static long sumOfEvenFibonacciNumbersUntilMaxNum() {
    long sumOfEvens = 0;
    long prevPrevEven, prevEven = 0, even = 2;

    while (even <= MAX_NUM) {
        sumOfEvens += even;
        prevPrevEven = prevEven;
        prevEven = even;
        // << 2 instead of * 4 matters here to reuse value 2 in the byte code.
        even = (prevEven << 2) + prevPrevEven;
    }
    return sumOfEvens;
}

Now we really have to go down to machine code in order to understand what's going on. This of course has limited value in Java, as there are too many unknowns like if it is JIT compiled, how the JIT works, and how fast the CPU is.

The byte code of the multiply solution is 3 instructions shorter, which happen to be in the loop. If the byte code is interpreted only, the multiply solution wins.

If the code is compiled, we need to think of what machine instructions are going on inside the loop.

Add loop:

; R0: result = 0
; R1: odd1
; R2: odd2 = 1
; R3: even = 2
; R4: MAX_VALUE
.label
    cmp R3, R4
    bgt .done
    add R0 <- R0 + R3
    ; begin difference
    add R1 <- R3 + R2
    add R2 <- R1 + R3
    add R3 <- R2 + R1
    ; end difference
    bra .label
.done

Multiply loop:

; R0: result = 0
; R1: prevPrevEven
; R2: prevEven = 0
; R3: even = 2
; R4: MAX_VALUE
.label
    cmp R3, R4
    bgt .done
    add R0 <- R0 + R3
    ; begin difference
    mov R1 <- R2
    mov R2 <- R3
    lsl R3 <- R3 << 2
    add R3 <- R3 + R1
    ; end difference
    bra .label
.done

Whether the multiply solution is faster or the add solution is faster depends on how this pseudo assembly translates into the real machine code. The key questions are:

• Is add Rn <- Rx + Ry available? If not, i.e. only add Rn <- Rn + Rx is available, each add Rn <- Rx + Ry with n != x and n != y requires an additional mov instruction.
• Is lsl Rn <- Rn << 2 available? If not, we need one more register. And if so, are enough registers available?

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 about method calls being expensive, which is wrong, and a description of loop unrolling which was partially wrong and thus misleading. The credit for fixing these bugs in the answer goes to jrolfl, who pointed this out and patiently discussed this with me in chat. Thank you!

Answer 2

The first trick of this exercise is recognizing you don't need to calculate the odd fibonacci numbers.

The series of only the even numbers is :

0, 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578, ...

So starting with 0 and 2 the next element is always 4 times the preceding one plus the one before that :

34 = 8*4 +2
144 = 34*4 + 8
...

Now the exercise is simply caluclating this series and keeping a running total, until you hit 4_000_000. If you do that using primitive long the performance is a lot better than what you have so far.

Output on my PC :

Yours     : Result: 4613732. Time used for calculation in nanoseconds: 530009.
Suggested : Result: 4613732. Time used for calculation in nanoseconds: 3603.

Edit : when I replaced 4*b + a by b + b + b + b + a performance got even better :

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

Answer 3

    ArrayList<Long> sequence = new ArrayList<Long>() {

As a general rule, you want to put the interface on the left side, not the implementation. This makes it easier to change the code later with a different implementation of the same interface.

    public static List<Long> sequence = new ArrayList<>();

Also, newer versions of Java do not require you to specify the type in the <> on the right side. The compiler is smart enough to figure it out.

I would also have made sequence a class variable. In fact, it might make sense to have a FibonacciSequence class that is separate from the Euler project altogether. That would allow you to create a more general implementation that you can reuse for other problems. This would also simplify main which has more of the programming logic than necessary.

public static void main(String[] args) {
    final long START = System.nanoTime();

    System.out.print("Result: " + sumStoredSequence(4000000L, 1, 3) 
        + ".\nTime used for calculation in nanoseconds: " 
        + (System.nanoTime() - START) + "."
    );
}

This puts all the problem logic in the function, leaving just display and timing logic in main. All main knows is that the maximum value is four million, the starting index is 1, and the update interval is 3.

Note: I'm not arguing against the optimizations in other answers. My point is that there are improvements that can be made in the current implementation, aside from the algorithmic ones.