Problem: 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, and 89. By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution: Notice that every third term is even. We can use this to our advantage. I’ll give three solutions: Sage, Python, and Cython.

Sage Solution

This can be done with a single line in Sage.

sage: sum([i for i in fibonacci_xrange(4000000) if is_even(i)])
4613732

But, how fast is it? Let’s try it one million times and time it in Sage.

import time
 
start = time.time()
for j in range(1000000):
    a = sum([i for i in fibonacci_xrange(4000000) if is_even(i)])
elapsed = (time.time() - start)
 
print "result %s returned after %s seconds (1 million iterations)." % (a, elapsed)

When we execute this, we wait and wait and wait. While I’m waiting for the result, I’ll explain what is taking so long. The function fibonacci_xrange() in Sage is not computing the Fibonacci numbers recursively, but calculating each one from scratch. That’s bad… really bad. I think I’ll go make some coffee while I wait for this to finish, and perhaps submit a bug patch. It finally finishes, roughly 15 minutes later.

result 4613732 returned after 887.411308289 seconds (1 million iterations).

Python Solution

Instead of using the PARI C library to compute the Fibonacci sequence non-recursively, we now construct the sequence explicitly in Python, and we can use the fact that every third number will be even to construct our sum. First, I’ll use a bit of slightly more elegant code.

import time
 
def fib_sum(n):
    fib = [1,2]
    n1,n2 = 1,2
    while n1+n2 < n:
        fib.append(n1+n2)
        n1,n2 = n2,n1+n2
    return sum(fib[1::3])
 
start = time.time()
for i in range(1000000): fibsum = fib_sum(4000000)
elapsed = (time.time() - start)
 
print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

This runs much more quickly than the Sage code.

result 4613732 returned after 16.3734951019 seconds (1 million iterations).

But, we can do better by avoiding the Python list slicing.

import time
 
def fibonacci_even_sum(n):
    if n == 0: return 0
    if n == 1: return 0
    if n == 2: return 2
 
    # n is greater than 2 (no error checking done)
 
    # set the initial sum to zero
    sum = 2
 
    # set the initial fibonacci values
    fib0 = 0 
    fib1 = 1
    fib2 = 2
 
    # set an iterator variable to only sum every third entry
    iter = 0
 
    while( fib2 <= n ):
        if( iter == 3 ):
            sum = sum + fib2
 
            # print fib2
            iter = 0
        fib0 = fib1
        fib1 = fib2
        fib2 = fib0 + fib1
        iter = iter + 1
 
    return sum
 
start = time.time()
for i in range(1000000): fibsum = fibonacci_even_sum(4000000)
elapsed = (time.time() - start)
 
print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

And when we run this, we get the following output.

result 4613732 returned after 11.8605749607 seconds (1 million iterations).

This is roughly 74.82 times faster than the Sage implementation.

Cython Solution

We modify our Python code slightly to produce Cython.

%cython
 
import time
 
cdef fibonacci_even_sum(unsigned long long int n):
    cdef unsigned long long int sum = 2
    cdef unsigned int iter = 0
    cdef unsigned long long int fib0 = 0
    cdef unsigned long long int fib1 = 1
    cdef unsigned long long int fib2 = 2
    if n == 0: return 0
    if n == 1: return 0
    if n == 2: return 2
 
    while( fib2 <= n ):
        if( iter == 3 ):
            sum = sum + fib2
 
            # print fib2
            iter = 0
        fib0 = fib1
        fib1 = fib2
        fib2 = fib0 + fib1
        iter = iter + 1
 
    return sum
 
start = time.time()
for i in range(1000000): fibsum = fibonacci_even_sum(4000000)
elapsed = (time.time() - start)
print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

When executed, we get the following.

result 4613732 returned after 0.363753080368 seconds (1 million iterations).

This is roughly 32.61 times faster than our fastest Python code, and about 2439.60 times faster than our Sage code.


Comments are closed