The second problem from Project Euler asks for the sum of the even Fibonacci numbers which are at most 4,000,000.

#### An aside on the numbers

The problem’s description of the Fibonacci sequence is flawed (or at least non-standard); the problem statement begins the sequence with 1 and 2, showing the first 10 terms as:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89

It is common to see the definition given as:

fib

_{1}= 1, fib_{2}= 1, fib_{n}= fib_{n-1}+ fib_{n-2}

I’m persuaded by Dijkstra’s line of reasoning, and prefer to use the definition…

fib

_{0}= 0, fib_{1}= 1, fib_{n}= fib_{n-1}+ fib_{n-2}

…not only for the benefit of a zero origin, but also because it invites the mind to consider completing the story. The equations…

fib

_{n}= fib_{n-1}+ fib_{n-2}

…and…

fib

_{n}– fib_{n-1}= fib_{n-2}

…are clearly equivalent, but the second one may help us realize that we can extend the conventional list to be infinite in *both* directions…

n | … | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

fib_{n} |
… | 13 | -8 | 5 | -3 | 2 | -1 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | … |

…making fib a total function over the integers. I’ll put off discussing that interesting option until another time, and for the rest of this post use only natural numbers.

#### Basic solutions

The naive recursive function for the n^{th} Fibonacci number…

def fibR(n: Int): Int = { if (n == 0) 0 else if (n == 1) 1 else fibR(n - 1) + fibR(n - 2) }

…requires O(exp n) time to evaluate. We could go for a tail-recursive (iterative) version…

def fibI(n: Int): Int = { def fib0(i: Int, a: Int, b: Int): Int = if (i == n) a else fib0(i + 1, b, a + b) fib0(0, 0, 1) }

…which executes in O(n) time. That’s an improvement, but still leaves us dealing with the Fibonacci sequence one number at a time.

#### Gently down the stream

The problem calls for a sum across multiple values from the Fibonacci sequence, and both of the above functions calculate “upwards” to reach the specified value. There’s no point in going through the sequence more than once (regardless of how efficiently we can do that), so let’s think of the sequence as a `Stream[Int]`

.

Element-wise addition of streams can be done as:

def add(s1: Stream[Int], s2: Stream[Int]): Stream[Int] = Stream.cons(s1.head + s2.head, plus(s1.tail, s2.tail))

A stream of the Fibonacci numbers is then:

val fibS: Stream[Int] = Stream.cons(0, Stream.cons(1, add(fibS, fibS tail)))

And now we’re back to familiar territory from the first problem. We simply filter for the even values, apply the limit, and sum the results:

scala> fibS.filter(_ % 2 == 0).takeWhile(_ <= 4000000).foldLeft(0)(_ + _) res17: Int = 4613732

We could stop with that solution, but there are a couple of additional techniques worth a mention.

#### “Go back, Jack, and do it again”

First, we could replace the stream with a simple `Iterator[Int]`

that holds a pair of consecutive Fibonacci numbers:

class Fibs extends Iterator[Int] { var state = (0, 1) def hasNext = true def next = { val (a, b) = state state = (b, a + b) a } }

Thanks to the `Iterator`

trait, when we implement `hasNext`

(is there another value?) and `next`

(return the next value), we get everything needed to complete the solution:

scala> new Fibs().filter(_ % 2 == 0).takeWhile(_ <= 4000000).foldLeft(0)(_ + _) res20: Int = 4613732

However, this still generates three times as many values as needed, because only every third Fibonacci number is even:

0,1,1,2,3,5,8,13,21,34,55,89,144…

How could we generate only the **even** Fibonacci numbers? Notice this progression in the numbers above:

fib

_{0}= 0

fib_{3}= 2

fib_{6}= 8

fib_{9}= 34

fib_{12}= 144

…

So we’re interested in producing the sequence fib_{3n} rather than fib_{n} if we want to obtain the even values. In our Fib class above, a and b are consecutive values, fib_{n} and fib_{n+1}. From the original definition, we can apply just a little algebra:

fib

_{n+2}= b + a

fib_{n+3}= fib_{n+2}+ fib_{n+1}= (b + a) + b = 2 × b + a

fib_{n+4}= fib_{n+3}+ fib_{n+2}= (2 × b + a) + (b + a) = 3 × b + 2 × a

If n is a multiple of 3, then (n + 3) is the next multiple of 3. So the above formulas for fib_{n+3} and fib_{n+4} give us a way to write an iterator that produces only **even** Fibonacci numbers:

class EvenFibs extends Iterator[Int] { var state = (0, 1) def hasNext = true def next = { val (a, b) = state state = (2 * b + a, 3 * b + 2 * a) a } }

This new iterator eliminates the need for the filter, reducing the solution to:

scala> new EvenFibs().takeWhile(_ <= 4000000).foldLeft(0)(_ + _) res30: Int = 4613732

This calculates exactly the values of interest, then uses standard methods to provide the sum. These last three versions retain the ability to re-use the parts that generate the Fibonacci numbers (or even Fibonacci numbers) for purposes other than the sum.

For sake of completeness, here’s the completely optimized version…

def sumEvenFibs(n: Int) = { def iter(a: Int, b: Int, s: Int): Int = if (a > n) s else iter(2 * b + a, 3 * b + 2 * a, a + s) iter(0, 1, 0) }

…which buys performance by giving up that reusability.

## Comments

Hi,

I was wondering what you thought of the following solution:

def solveFunctionally(limit: int) = {

fib(limit).filter(i => i % 2 == 0).foldLeft(0) {_ + _}

}

def fib(limit: int):List[int] = {

def fibh(c:List[int]):List[int] = c match {

case List() => fibh(1::0::Nil)

case a :: b :: rest if (a + b >= limit) => c

case a :: b :: rest if (a + b fibh(a + b :: a :: b :: rest)

}

fibh(List())

}

(I hope that formatted ok).

fib generates the fibonacci sequence as list, which at first sight is a problem because of space, but for this problem, its size ends up at 34 which is very small. Of course, a+b is repeated 3 times which I guess isn’t good.

@Channing: I think WordPress ate part of the code. The third case is invalid syntax, but I attempted to restore what got eaten between < and > and reformatted the resulting code as follows:

def fib(limit: int):List[int] = {

def fibh(c:List[int]):List[int] = c match {

case List() => fibh(1::0::Nil)

case a :: b :: rest if (a + b >= limit) => c

case a :: b :: rest if (a + b < limit) => fibh(a + b :: a :: b :: rest)

}

fibh(List())

}

def solveFunctionally(limit: int) = {

fib(limit).filter(i => i % 2 == 0).foldLeft(0) {_ + _}

}

(And I hope you’ll correct me if I made a wrong assumption.)

As you pointed out, the redundant

`a + b`

would be something to avoid. So is the repeated “unpacking” of`c`

into`a :: b :: rest`

and the repacking of that same expression in the recursive call of the third case. I’d suggest refactoring to tighten up those areas.Yes, you are right, there is a lot that could be cleaned up.

I was also wondering if the pattern matching is really a good thing or not.

@Channing: That’s a good question. In general, I believe that pattern matching is a powerful tool that can provide a great deal of clarity and economy of expression. But repeatedly matching the same pattern is another violation of DRY which can add visual clutter and add to run time.

In the example you posted, the first case (the empty list) is only matched on the first call to

`fibh`

but is tested on every subsequent call. The second and third cases do exactly the same “unapply” to the`c`

, and only differ in their guard expressions (which actually check the same condition—one positively and the other negatively). So there’s a fair bit of repeated effort.I’d suggest (1) taking

`a`

and`b`

out of the list, (2) only consing a value onto the list when it is within limit, and (3) moving the intialization of`a`

and`b`

into the first call to`fibh`

(because it is a nested function, there’s no leakage of implementation details). Doing those things gives something like this…def fib2(limit: int):List[int] = {

def fibh(b: Int, a: Int, c:List[int]):List[int] =

if (a >= limit) c else fibh(a + b, b, a :: c)

fibh(1, 0, List())

}

…which is about three times as fast as the original

`fib`

(∼ 1.9μs for`fib2`

vs ∼ 5.6μs for`fib`

on my little laptop).Thanks for helping me think through this a little further!

Thanks for that. I am new to scala and functional programming so this has been very helpful.

Channing