• Home
  • Q&A
  • Python program to find fibonacci series. More Pythonic way
 
19
0
0

Python program to find fibonacci series. More Pythonic way

Lakshman PrasadviaStackOverflow
February 23, 2009
6 score
7 answers

There is another thread to discuss Fibo series in Python. This is to tweak code into more pythonic. How to write the Fibonacci Sequence in Python

I am in love with this program I wrote to solve Project Euler Q2. I am newly coding in Python and rejoice each time I do it The Pythonic way! Can you suggest a better Pythonic way to do this?

Project Euler Q2. Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

fib=[]
def fibo(a=-1,b=1,upto=4000000):
    if a+b>=upto:
        return
    else:
        a,b=b,a+b
        fib.append(b)
        fibo(a,b)

fibo()
even=[i for i in fib if not i%2]
print sum(even)

Answers

12 score

First I'd do fibo() as a generator:

def fibo(a=-1,b=1,upto=4000000):
    while a+b<upto:
        a,b = b,a+b
        yield b

Then I'd also select for evenness as a generator rather than a list comprehension.

print sum(i for i in fibo() if not i%2)
answered February 23, 2009
15 score

Using generators is a Pythonic way to generate long sequences while preserving memory:

def fibonacci():
  a, b = 0, 1
  while True:
    yield a
    a, b = b, a + b

import itertools
upto_4000000 = itertools.takewhile(lambda x: x <= 4000000, fibonacci())
print(sum(x for x in upto_4000000 if x % 2 == 0))
answered February 23, 2009
3 score

For one thing, I would suggest summing up the terms as you calculate them rather than storing them in an array and summing the array afterwards, since you don't need to do anything with the individual terms other than adding them up. (That's just good computational sense in any language)

answered February 23, 2009
2 score

Here's an alternate direct method It relies on a few properties:

  1. Each Fibonacci number can be calculated directly as floor( pow( phi, n ) + 0.5 ) (See Computation by Rounding in http://en.wikipedia.org/wiki/Fibonacci_number ). Conversely the index of the biggest Fibonacci number less than i is given by floor( log(i*sqrt(5)) / log(phi) )
  2. The sum of the first N Fibonacci numbers is the N+2th fibonacci number minus 1 (See Second Identity on the same wikipedia page)
  3. The even Fibonacci numbers are are every third number. ( Look at the sequence mod 2 and the result is trivial )
  4. The sum of the even Fibonacci numbers is half the sum of the odd Fibonacci numbers upto the same point in the sequence.

Point 4 can be seen from this:

Sum of first 3N fibonacci numbers
   =(F(1) + F(2))+ F(3) +(F(4) + F(5))+ F(6) + ... +(F(3N-2) + F(3N-1))+ F(3N) 
   =     F(3)    + F(3) +     F(6)    + F(6) + ... +       F(3N)       + F(3N)
   = 2( F(3) + F(6) + ... + F(3N) )
   = 2 ( Sum of odd fibonacci numbers up to F(3N) )

So convert our maximum value of 4000000 calculate the index of the highest Fibonacci number less than it.

int n = floor(log(4000000*sqrt(5))/log(phi));  // ( = 33) 

33 is divisible by 3 so it is an even Fibonacci number, if it wasn't we'd need to adjust n like this.

n = (n/3)*3;

The sum of all Fibonacci numbers up to this point if given by

sum = floor( pow( phi, n+2 ) + 0.5 ) - 1; // ( = 9227464 )

The sum of all even numbers is half of this:

sum_even = sum/2; // ( = 4613732 )

Nice thing about this is that its an O(1) (or O(log(N)) if you include the cost of pow/log) algorithm, and works on doubles.. so we can calculate the sum for very large values.

NOTE: I edited and moved this answer from a closed duplicate of this question. http://stackoverflow.com/questions/3270863

answered July 19, 2010
2 score

I'd use the fibonacci generator as in @constantin' answer but generator expressions could be replaced by a plain for loop:

def fibonacci(a=0, b=1):
    while True:
        yield a
        a, b = b, a + b

sum_ = 0
for f in fibonacci():
    if f > 4000000:
       break
    if f % 2 == 0:
       sum_ += f

print sum_
answered February 23, 2009
2 score

I would make the following changes:

  • Use iteration instead of recursion
  • Just keep a running total instead of keeping a list of all Fibonacci numbers and then finding the sum of the even ones a posterior

Other than that, it's reasonably Pythonic.

def even_fib_sum(limit):
    a,b,sum = 0,1,0
    while a <= limit:
        if a%2 == 0:
            sum += a
        a,b = b,a+b
    return sum

print(even_fib_sum(4000000))
answered February 23, 2009
0 score

In Python 3 at least if you give a generator to the sum function it will lazily evaluate it so there is no need to reinvent the wheel.

This is what @Constantin did and is correct.

Tested by comparing the memory usage of using generators:

sum(range(9999999))

compared with not doing so:

sum(list(range(9999999)))

The one with the generator does not cause memory exceptions with higher numbers either.

answered October 25, 2011
Discussion

-