Second project Euler solution

Question

The things I'm interested the most from the review are:

• The performance of the code
• Overall review of the code structure, styling rules and naming conventions.

Problem: 2

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

import math
import itertools
#----------------------------------------------------------------------------------
def calc_fibonacci_num(n):
    """Calculates the fibonacci number at the given index.

    Arguments:
        type:<int> - Index value of the fibonacci sequence
    Return:
        type:<int> - Fibonacci number at the given index.
    """
    return int(((1 + math.sqrt(5))**n -(1 - math.sqrt(5))**n)/(2**n*math.sqrt(5)))

#----------------------------------------------------------------------------------
def calc_fibonacci_seq(n):
    """Generates the fibonacci sequence with the highest
    value equal to or less then the number provided by the user.

    Arguments:
        type:<int> - Thrshold value for the fibonacci sequence.
    Return:
        type:<arr> - An array holding the fibonacci sequence.
    """
    return [calc_fibonacci_num(x) for x in itertools.takewhile(lambda x: calc_fibonacci_num(x) <= n, itertools.count())]

#----------------------------------------------------------------------------------
def calc_fibonacci_sum(n, d = 0):
    """Calculates the sum of the numbers in fibonacci sequence.
    Filtering of the numbers to be added is controled with the module operator.

    Arguments:
        type:<int> - Thrshold value for the fibonacci sequence.
        type:<int> - Division value for module operation.
    Return:
        type:<int> - The sum of the numbers in the fibonacci sequence.
    """
    if d > 1 :
        return sum(x for x in calc_fibonacci_seq(n) if x % d == 0)      
    return sum(x for x in calc_fibonacci_seq(n))

#----------------------------------------------------------------------------------
def main():

    print(' Fibonacci-seq : {}'.format(calc_fibonacci_seq(4000000)))
    print(' Fibonacci-sum : {}'.format(calc_fibonacci_sum(4000000, 2)))

#----------------------------------------------------------------------------------
if __name__ == "__main__":
    main()

Answer 1

Your code looks good and is well documented. I have a few suggestions anyway.

Naming

calc_fibonacci_num is a long name for such a function. The calc_ prefix is probably not useful and neither is the _num.

The expression fibonacci(5) is probably explicit enough without additional information.

The same kind of comment applies to the other function names.

Domain definition (and default value)

It seems a bit "un-natural" to handle d=0 as a special case for calc_fibonacci_sum. It may be clearer to explain that d is expected to be a strictly positive integer.

Then you'd just need to give d the default value 1 and everything would work just fine.

Function called twice

In return [calc_fibonacci_num(x) for x in itertools.takewhile(lambda x: calc_fibonacci_num(x) <= n, itertools.count())], you call the same function with the same argument twice. You can easily check this by adding a print(n) at the beginning of calc_fibonacci_num.

A solution to this issue is to rewrite the function:

def calc_fibonacci_seq(n):
    return itertools.takewhile(lambda x: x <= n, (calc_fibonacci_num(x) for x in itertools.count()))

This fixes another issue you had which is the fact you were building an actual list in memory when you just need a generator to go through the different lists.

An easier way to generate successive fibonacci numbers

The formula you've used is fairly efficient to generate the n-th fibonacci number without generating all the numbers before. However, in our case, we do need to compute them anyway. Thus, a naive solution would probably be faster. I'd suggest the following generator:

def fibo(f=1, g=1):
    """Yields Fibonacci numbers."""
    while True:
        yield f
        f, g = g, f + g

Answer 2

Correctness

calc_fibonacci_num doesn't say anything about range of accepted inputs

>>> calc_fibonacci_num(100)
354224848179263111168L

according to wolframalpha, it should be 354224848179261915075

Floating-point arithmetic is not precise enough to handle this

Answer 3

As Josay already talked extensively about the code itself, let me throw in my two cents regarding the performance.

Some of the Euler questions are for both - beginners and experienced programmers and the question number two is one of those. The beginner tackles the problem like you did and implements the solution word by word as asked. The more experienced programmer remembers vaguely something about geometric series and implements the solution by first searching for the Fibonacci index n generating a value lower than the limit M:

n = floor(log(M*sqrt(5))/ log((1+sqrt(5)) / 2 ))

(beware: this gives F(n) <= M !) It is good enough for M <= 2^64 with the default double precision.

The sum of the even Fibonacci indices up to and including n is F(2n + 1) -1 (Proofs by telescoping the series and induction at https://math.stackexchange.com/questions/1159572/prove-the-sum-of-the-even-fibonacci-numbers)

This method reduces the number of computations of F(n) to one (or two if the limit is given as F(n) < M) and although a much larger one (Python has a build-in bigint library which gets used automatically since version >2.5) is needed for the final result it is still faster iff you implement the evaluation of F(n) as matrix exponentiation.

Answer 4

Performance.

Let's compare performance of your method to a more straightforward solution:

def sum_even_fibs(fib_cutoff=4e6):
    """Sums even Fibonacci numbers strictly less than fib_cutoff
    """
    even_sum = 0
    a, b = 0, 1 # initialize Fibonacci
    while a < fib_cutoff:
        if a % 2 == 0: # a is even
            even_sum += a
        a, b = b, a+b # increment Fibonacci sequence
    return even_sum

They both give the same result with a Fibonacci cutoff of four million. Let's use three trials each with 100,000 runs of both programs using timeit.repeat

In [1]: import timeit

In [2]: timeit.repeat(stmt='calc_fibonacci_sum(4000000, 2)', setup='''
import math
import itertools
def calc_fibonacci_num(n):
    return int(((1 + math.sqrt(5))**n -(1 - math.sqrt(5))**n)/(2**n*math.sqrt(5)))

def calc_fibonacci_seq(n):
    return [calc_fibonacci_num(x) for x in itertools.takewhile(lambda x: calc_fibonacci_num(x) <= n, itertools.count())]

def calc_fibonacci_sum(n, d = 0):
    if d > 1 :
        return sum(x for x in calc_fibonacci_seq(n) if x % d == 0)
    return sum(x for x in calc_fibonacci_seq(n))''', number=100000)
Out[2]: [12.910888805025024, 13.122391237993725, 13.271997723000823]

In [3]: timeit.repeat(stmt='sum_even_fibs(4000000)', setup='''
def sum_even_fibs(fib_cutoff=4e6):
        even_sum = 0
        a, b = 0, 1 # initialize Fibonacci
        while a < fib_cutoff:
            if a % 2 == 0: # a is even
                even_sum += a
            a, b = b, a+b # increment Fibonacci sequence
        return even_sum                                   
''', number=100000)
Out[3]: [0.5254897740087472, 0.44452247698791325, 0.4534486950142309]

In [4]: sum(Out[2])/sum(Out[3])
Out[4]: 27.612473581497778

So, your method is about 27.6 times slower. If you did Josay's improvement definition of calc_fibonacci_seq (to avoid double calculating each fibonacci number), then you would still be 17 times slower.

In [5]: timeit.repeat(stmt='calc_fibonacci_sum(4000000, 2)', setup='''
import math
import itertools
def calc_fibonacci_num(n):
    return int(((1 + math.sqrt(5))**n -(1 - math.sqrt(5))**n)/(2**n*math.sqrt(5)))

def calc_fibonacci_seq(n):
    return itertools.takewhile(lambda x: x<= n, (calc_fibonacci_num(x) for x in itertools.count()))

def calc_fibonacci_sum(n, d = 0):
    if d > 1 :
        return sum(x for x in calc_fibonacci_seq(n) if x % d == 0)      
    return sum(x for x in calc_fibonacci_seq(n))''', number=100000)
Out[5]: [8.157165662007174, 7.9410463359963614, 8.012410539988196]

In [6]: sum(Out[5])/sum(Out[3])
Out[6]: 16.865776528460998

Also as pointed out by RiaD your slow method for calculating Fibonacci numbers is only accurate up to F(70) due to floating point errors while the faster definition using integer addition continues to calculate large Fibonacci numbers correctly.

Answer 5

I'm not a fan of one-line functions in general, and here you're not only splitting each line into a function, but generalizing them to accept arbitrary inputs, which then leads to special handling of edge cases. When your comments are added in, you spend several dozen lines on a program that could theoretically be put in a single line. While there are faster implementations, the following is about as simple as it gets, conceptually.

last_fib_num=1
cur_fib_num=1
fib_total = 0
fib_limit = 4*10**6
while not (cur_fib_num > fib_limit):
   if ((cur_fib_num % 2)==0):
       fib_total += cur_fib_num
   last_fib_num, cur_fib_num = cur_fib_num, last_fib_num+cur_fib_num
print(fib_total)

This can be reduced even further at the cost of readibility, e.g.

a,b,t=1,1,0
while not (b > 4*10**6):
   a,b,t = b, a+b,t+(b)*(1-b%2)
print(t)