#### Monday, July 6th, 2009...20:51

## Project Euler Problem #2

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

## Comments are closed.