Go with the flow

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:

fib1 = 1, fib2 = 1, fibn = fibn-1 + fibn-2

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

fib0 = 0, fib1 = 1, fibn = fibn-1 + fibn-2

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

fibn = fibn-1 + fibn-2

…and…

fibn – fibn-1 = fibn-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
fibn 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 nth 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:

fib0 = 0
fib3 = 2
fib6 = 8
fib9 = 34
fib12 = 144

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

fibn+2 = b + a
fibn+3 = fibn+2 + fibn+1 = (b + a) + b = 2 × b + a
fibn+4 = fibn+3 + fibn+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 fibn+3 and fibn+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.

Advertisements
Trackbacks are closed, but you can post a comment.

Comments

  • Channing Walton  On 2008-04-17 at 08:20

    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.

  • joelneely  On 2008-04-17 at 21:00

    @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.

  • Channing Walton  On 2008-04-18 at 01:57

    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.

  • joelneely  On 2008-04-18 at 05:27

    @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!

  • Channing Walton  On 2008-04-18 at 13:49

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

    Channing

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: