1

I tried two algorithms for Fibonacci series and compare the speed.

The first one is by powers of matrices through Numpy (I also wrote my own function but seems numpy is faster).

import numpy as np
import time

def fibonacci_power(n):
    F=np.matrix('1,1;1,0')
    Fn=F**(n-1)
    return Fn[0,0]

The second is dynamic programming with a shortened memory.

def fibonacci_mem(n):
    f=[0, 1]
    if n<=1:
        return f[n]
    for i in range(2, n+1):
        temp=f[1]
        f[1]=f[1]+f[0]
        f[0]=temp
    return f[1]

The time complexity of the first one is O(log n) and the second is O(n). So for larger n, the first one should be faster.

I compare their speed in the following:

def main():
    n=90

    start=time.time()
    f1=fibonacci_power(n)
    f1_time=time.time()-start
    print('Power/Numpy result: '+str(f1)+' time: '+str(f1_time))

    start=time.time()
    f3=fibonacci_mem(n)
    f3_time=time.time()-start
    print('Memory result: '+str(f3)+' time: '+str(f3_time))

The result is:

Power/Numpy result: 2880067194370816120 time: 0.00021696090698242188
Memory result: 2880067194370816120 time: 4.410743713378906e-05

Am I comparing their speed in the right way? If yes, can anyone explain why the second is faster? Thanks.

Shangru Li
  • 11
  • 1
  • Why don't you use [`timeit`](https://stackoverflow.com/questions/8220801/how-to-use-timeit-module) to benchmark the two functions? – Cory Kramer Jun 10 '18 at 12:41
  • 2
    90 is a pretty tiny number. Algorithmic complexity is only a good mesure of how fast an approach is going to be for large inputs. Try your test with `n=1000000` and look at the results. – Patrick Haugh Jun 10 '18 at 12:55
  • if you don't specify a dtype to your matrix, the results become wrong fast (n=100). with good dtype and good n (>10000) numpy wins – bobrobbob Jun 10 '18 at 13:03
  • 1
    @bobrobbob Hi, that is why I set it 90. the dtype is int 64 now. How can I set the dtype? Thanks. – Shangru Li Jun 10 '18 at 13:20
  • @PatrickHaugh Thanks. I did try for larger but there is integer overflow for Numpy. In much larger case, Numpy is faster. – Shangru Li Jun 10 '18 at 13:21
  • @ShangruLi i can't make numpy use python's `int` so i tried `F=np.matrix('1,1;1,0', dtype=np.float128)`. surely someone knows – bobrobbob Jun 10 '18 at 13:34

1 Answers1

0

Use cProfile, it'll display everything your function is doing(calling, etc). And, compare this:

import cProfile
cProfile.run('fibonacci_power(150)')
#compare it to
cProfile.run('fibonacci_mem(150)')

To this:

import cProfile
cProfile.run('fibonacci_power(15000)')
#compare it to
cProfile.run('fibonacci_mem(15000)')

As you can see, NumPy uses so many things to do task because matrix method is more complex. Your code is simpler, it just use few built-in things. NumPy is used to do more complex things, and it would be slower compared to little function that you wrote if 'n' is small number. Just see cProfile explanation, it will be clearer. Of course, for big numbers and long run, NumPy is faster.

DecaK
  • 286
  • 2
  • 13