Time for action – computing Fibonacci numbers

The Fibonacci recurrence relation can be represented by a matrix. Calculation of Fibonacci numbers can be expressed as repeated matrix multiplication:

  1. Create the Fibonacci matrix as follows:
    F = np.matrix([[1, 1], [1, 0]])
print "F", F

    The Fibonacci matrix appears as follows:

    F [[1 1]
  [1 0]]
  2. Calculate the eighth Fibonacci number (ignoring 0), by subtracting 1 from 8 and taking the power of the matrix. The Fibonacci number then appears on the diagonal:
    print "8th Fibonacci", (F ** 7)[0, 0]

    The Fibonacci number is:

    8th Fibonacci 21
  3. The golden ratio formula, better known as Binet's formula, allows us to calculate Fibonacci numbers with a rounding step at the end. Calculate the first eight Fibonacci numbers:
    n = np.arange(1, 9)
sqrt5 = np.sqrt(5)
phi = (1 + sqrt5)/2
fibonacci = np.rint((phi**n - (-1/phi)**n)/sqrt5)print "Fibonacci", fibonacci

    The Fibonacci numbers are: 

    Fibonacci [  1.   1.   2.   3.   5.   8.  13.  21.]

What just happened?

We computed Fibonacci numbers in two ways. In the process, we learned about the matrix function that creates matrices. We also learned about the rint function that rounds numbers to the closest integer but does not change the type to integer (see fibonacci.py):

import numpy as np

F = np.matrix([[1, 1], [1, 0]])
print "F", F
print "8th Fibonacci", (F ** 7)[0, 0]
n = np.arange(1, 9)

sqrt5 = np.sqrt(5)
phi = (1 + sqrt5)/2
fibonacci = np.rint((phi**n - (-1/phi)**n)/sqrt5)
print "Fibonacci", fibonacci

Have a go hero – timing the calculations

You are probably wondering which approach is faster; so go ahead time it. Create a universal Fibonacci function with frompyfunc and time it too.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.138.110.119