Thursday, September 26, 2013

The Sum of Even Fibonacci Numbers

A co-worker showed me the following problem last night:

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.
If you jump too fast to your early CS101 knowledge you might bang out a recursive fibonacci function to get yourself started (using Ruby as an example):

def fib(n)
  return 0 if n==1
  return 1 if n==2
  return fib(n-1)+fib(n-2)

But that's not terribly efficient in this problem, where you'll end up calculating and recalculating the fibs all the way up to 4 million.

If you spot that the recursion will just do an absolute number on your stack management and want to get it out of there you can write the function without it:

def fib(n)

  prev = 0
  curr = 1
  (n - 1).times do
    curr, prev = prev+curr, curr

But you're still going to calculate too many numbers and end up with a solution that is O(N^2) because every time you move to position N your function is going to recalculate everything from 1 to N-1.

Instead, don't abstract the function.  Treat it like the formula that it is, and write it in a single loop.  You are going to be calculating your variable N using the N(x) = N(x-1)+N(x-2) formula, until N>4000000.  Along the way, if N is even, add it to your growing sum:

first = 0
second = 1
sum = 0
while (second < 4000000) do
  sum += second if second.even?
  temp = second
  second = first + second
  first = temp
puts sum

Did you get 4613732?  You could clean up that code a bit and there's tricks to avoid that temp variable but I want to get to a better solution.  The one above calculates all the Fibonacci numbers less than 4 million, which means it goes through the loop 33 times.

We can do better.  If you look closely at the fibonacci sequence you may spot a pattern in the even numbers.  Did you notice that every 3rd number is the even one?  Which makes sense because once you bring even a single odd number into the pattern it's going to go the same way -- even plus odd equals odd, odd plus odd equals even.  So the Fibonacci sequence goes odd even odd odd even odd odd even odd where each even number is wrapped with odd numbers.

How can we use this?  Well this means if we know that fib(N) is even, we want to jump to fib(N+3) without worrying about the two in the middle.  So instead of looping over them why not just calculate them while we're here?  I'm going to use the sequence 5,8,13,21,34 as an example.  If I'm on 8, I want to calculate 34:

Given fib(x)=8
Given fib(x-1)=5
Calculate fib(x+1) = (8+5)
Calculate fib(x+2) = fib(x+1)+fib(x) = (8+5)+8  = (8*2 + 5) = fib(x)*2 + fib(x-1)
Calculate fib(x+3) = fib(x+2)+fib(x+1) = ((8+5)+8)+(8+5) = (3*8 + 2*5) = fib(x)*3 + fib(x-1)*2

Still with me?  So as long as I have fib(x) and fib(x-1) I can jump to fib(x+3) with some multiplication.

So now I can go through the loop like this:

x1 = 1

x  = 2
sum = 0
while (x < 4000000) do
      sum += x
      n = 3*x+2*x1
      x1 = 2*x+x1
      x = n
print "Your total is #{sum}"

Same result, only this time we bounced up to 4 million in just 10 hops.

Again, we could probably make it even more efficient than that by considering the actual cost of each math operation - I added some multiplications but now I'm also no longer testing for even numbers, so maybe it's a wash. I was mostly interested in showing that whole "even numbers every third so only jump by 3s and don't test for even" pattern.

I wanted to document this approach since I haven't seen it yet as one of the standard answers.  Enjoy.

No comments: