Time for action – computing Fibonacci numbers

A matrix can represent the Fibonacci recurrence relation. We can express the calculation of Fibonacci numbers as a 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 8th 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 as follows:

    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 first eight Fibonacci numbers are as follows:

    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):

from __future__ import print_function
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 and time it. Create a universal Fibonacci function with frompyfunc() and time that too.

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

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