James Pine Has A Blog

Problem 2 from projecteuler requested the sum of all the even Fibonacci numbers below 4 million. I had seen references to “generators” in some of the Python howtos and after further reading, this seemed like a reasonable place to try them out.

def fibGenerator():
 fib0 = 0
 fib1 = 1
 while True:
  yield fib1
  fibNext = fib0 + fib1
  fib0 = fib1
  fib1 = fibNext

Then all I had to do was keep track of a running total of the even numbers which lead to:

def sumEvenFibs():
 fib = fibGenerator()
 sum = 0
 nextFib = fib.next()
 while nextFib < 4000000:
  if nextFib & 1 == 0:
   sum += nextFib
  nextFib = fib.next()
 return sum


iterations = 1000
t = timeit.Timer("sumEvenFibs()","from __main__ import sumEvenFibs")
print "Answer: %d. %d iterations took %.3f seconds" % (sumEvenFibs(), iterations, t.repeat(1,iterations)[0])


Answer: 4613732. 1000 iterations took 0.109 seconds

The while loop in sumEvenFibs didn't seem very Pythonic so I thought about how I could go about removing it. I could change fibGenerator to take a parameter for the maximum Fibonacci number to generate. In addition, the condition that a number be even was conceptually a filter that could easily be captured in a lambda function. I ended up with this:

def fibGenerator(maxFib):
 fib0 = 0
 fib1 = 1
 while fib1 < maxFib:
  yield fib1
  fibNext = fib0 + fib1
  fib0 = fib1
  fib1 = fibNext

def sumEvenFibs():
 fib = fibGenerator(4000000)
 return sum(filter((lambda x: x & 1 == 0),fib))

Which performed about as well, and is much cleaner. Looking through the forums it turns out there is a pattern to the Fibonacci numbers (odd, odd, even...) so it's pretty easy to get rid of the even check as well:

def evenFibGenerator(maxFib):
 fib0 = 1
 fib1 = 2
 while fib1 < maxFib:
  yield fib1
  temp = fib0 + (2 * fib1)
  fib1 = (2 * fib0) + (3 * fib1)
  fib0 = temp

def sumFibs():
 fib = evenFibGenerator()
 return sum([f for f in fib])

Not suprisingly this cuts the runtime by about 50%: Answer: 4613732. 1000 iterations took 0.043 seconds. On to the next problem...