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...