## 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)) ```

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