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.



In [1]:

    
n = 4000000



In [2]:

    
def foo(n):
    a = 0
    b = 1
    total = 0
    while True:
        c = a + b
        a = b
        b = c
        # print b
        if b > n:
            break
        if b % 2 == 0:
            total += b
    return total



In [3]:

    
%timeit foo(n)
correct_answer = foo(n)
correct_answer









    



100000 loops, best of 3: 9.17 µs per loop






    Out[3]:





4613732



In [4]:

    
def fib(last):
    a = 0
    b = 1
    while True:
        c = a + b
        a = b
        b = c
        if b > last:
            break
        yield b

def foo(n):
    return sum([f for f in fib(n) if f % 2 == 0])



In [5]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 13.2 µs per loop



In [6]:

    
def even_fibonacci(last):
    a = 0
    b = 1
    while True:
        c = a + b
        a = b
        b = c
        if b > last:
            break
        if b % 2 == 0:
            yield b

def foo(n):
    return sum([f for f in even_fibonacci(n)])



In [7]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 11.9 µs per loop



In [8]:

    
def unrolled_even_fibonacci(last):
    a = 0
    b = 1
    while True:
        c = a + b
        a = b
        b = c
        c = a + b
        a = b
        b = c
        if b > last:
            break
        yield b
        c = a + b
        a = b
        b = c

def foo(n):
    return sum([f for f in unrolled_even_fibonacci(n)])



In [9]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 7.44 µs per loop



In [10]:

    
def unrolled_even_fibonacci(last):
    a = 0
    b = 1
    while True:
        c = a + b
        d = b + c
        if d > last:
            break
        yield d
        e = c + d
        a = d
        b = e

def foo(n):
    return sum([f for f in unrolled_even_fibonacci(n)])



In [11]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 6.37 µs per loop



In [12]:

    
def unrolled_even_fibonacci(last):
    '''
    The body of the loop reminds me of a musical round.
    I like how there are no wasted assignments.
    '''
    a = 0
    b = 1
    while True:
        c = a + b  # Frère Jacques, frère Jacques,
        a = b + c  # Dormez-vous? Dormez-vous?
        if a > last:
            break
        yield a
        b = c + a  # Sonnez les matines! Sonnez les matines!

def foo(n):
    return sum([f for f in unrolled_even_fibonacci(n)])



In [13]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 5.8 µs per loop



In [14]:

    
def unrolled_even_fibonacci(last):
    '''
    The body of the loop reminds me of a musical round.
    I like how there are no wasted assignments.
    '''
    a = 0
    b = 1
    while True:
        c = a + b  # Frère Jacques, frère Jacques,
        a = b + c  # Dormez-vous? Dormez-vous?
        if a > last:
            break
        yield a
        b = c + a  # Sonnez les matines! Sonnez les matines!

def foo(n):
    return sum(unrolled_even_fibonacci(n))



In [15]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 4.24 µs per loop



In [16]:

    
def sum_even_fibonacci(last):
    '''
    The body of the loop reminds me of a musical round.
    I like how there are no wasted assignments.
    '''
    total = 0
    a = 0
    b = 1
    while True:
        c = a + b
        a = b + c
        if a > last:
            return total
        total += a
        b = c + a

def foo(n):
    return sum_even_fibonacci(n)



In [17]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 3.92 µs per loop



In [18]:

    
def sum_even_fibonacci(last):
    '''
    The body of the loop reminds me of a musical round.
    I like how there are no wasted assignments.

    Aligned test with beginning of loop, hoping for small speed increase,
    albeit at cost of ugly duplicated code before loop.
    Loop code itself got easier to read.'''

    total = 0
    a = 0
    b = 1
    c = a + b
    a = b + c
    while a <= last:
        total += a
        b = c + a
        c = a + b
        a = b + c
    return total

def foo(n):
    return sum_even_fibonacci(n)



In [19]:

    
%timeit foo(n)
assert foo(n) == correct_answer









    



100000 loops, best of 3: 3.9 µs per loop