Skip to content

Fibonacci Series

Qiang Zhu edited this page Sep 25, 2018 · 6 revisions

a function to compute Fibonacci series from QZ

def Fibonacci(N):
    '''
    This program is to calculate Fibonacci number`
    Input: N (must be a positive integer number) `
    output: the Fibonacci series`
    '''

    Fib_series = []
    
    for i in range(1,N+1):
        if len(Fib_series)<=1:
            Fib_series.append(1)
        else:
            Fib_series.append(Fib_series[-1] + Fib_series[-2])
    return Fib_series

print(Fibonacci(-1))
print(Fibonacci(1))
print(Fibonacci(2))
print(Fibonacci(3))
print(Fibonacci(4))
print(Fibonacci(1000))

Speed up the calculation

Suppose if we just want to calculate the Fibonacci number for a given index, the above program can be written as follows:

def Fibonacci(N):
    '''
    This program is to calculate fibonacci number using return
    Input: N (must be a positive integer number) 
    output: the Fibonacci series
    '''

    Fib_series = []
    for i in range(1,N+1):
        if len(Fib_series)<=1:
            return 1
        else:
            Fib_series.append(b)
            a, b = b, a + b
    return Fib_series[-1]

%timeit(Fibonacci(10000))

You can simply evaluate the time cost by using the timeit function

530 ns ± 35.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

However, the time cost can be reduced to half by simply replacing return with yield function:

def Fibonacci2(N):
    '''
    This program is to calculate fibonacci number using yield
    Input: N (must be a positive integer number) 
    output: the Fibonacci series
    '''

    Fib_series = []
    a = b = 1
    for i in range(1,N+1):
        if len(Fib_series)<=1:
            yield 1
        else:
            yield a
            a, b = b, a + b

%timeit(Fibonacci2(10000))
225 ns ± 5.18 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

The yield statement suspends function’s execution and sends a value back to caller, but retains enough state to enable function to resume where it is left off. When resumed, the function continues execution immediately after the last yield run. This allows its code to produce a series of values over time, rather them computing them at once and sending them back like a list.

Clone this wiki locally