With another school semester on the horizon, I’ve been reviewing old course material to refresh my memory. Since a lot of this material is useful when devising algorithms, I’m going to spend the next few weeks revisiting some of the more interesting concepts. First up is the Fibonacci sequence. This is the sequence F(n) = F(n-2) + F(n-1) where F(0) = 0 and F(1) = 1.

If we wish to determine a given Fibonacci number n, there are several approaches we can take. The approaches I’ll cover here involve recursion, iteration, Binet’s formula, and matrix form. Each of the following examples assumes that the algorithm is handling a positive integer, and all were validated with Ruby 1.8.7.

Recursion

def F(n)
  return n if n == 0 or n == 1
  return F(n - 2) + F(n - 1)
end

This naive solution uses recursion to calculate the value of a Fibonacci number and runs in exponential time. While the solution is viable for small values of n, the algorithm’s lack of memory will cause the execution to take significantly longer for larger values.

Example: Find the fifth Fibonacci number.

As you can see, there is a lot of redundancy in this algorithm because we do not store each Fibonacci number as it is calculated. This deficiency can be alleviated by using an iterative approach to hold the value of each Fibonacci number as long as it is needed by a subsequent calculation.

Iteration

def F(n)
  return n if n == 0 or n == 1
  f = Array[0, 1]
  (n - 1).times { f[0], f[1] = f[1], f[0] + f[1] }
  return f[1]
end

As mentioned before, this approach will only store a Fibonacci number for as long as it is required by a subsequent calculation. Since a Fibonacci number is the sum of the two Fibonacci numbers before it, these are the only two values that we need to remember. Using this approach allows us to efficiently determine a Fibonacci number in linear time while optimizing memory usage.

Example: Find the fifth Fibonacci number.

Binet’s Formula

PHI = (1 + Math.sqrt(5)) / 2

def F(n)
  return ((PHI ** n - (-1 / PHI) ** n) / Math.sqrt(5)).to_i
end

Depending on the desired accuracy level, a Fibonacci number can be approximated in constant time using Binet’s formula. The formula provides exact values of F(n) for “reasonable” values of n, but the tests I conducted using my Ruby scripts for Binet’s formula and iteration show a deviation at n = 72. Since a linear algorithm executing to n = 72 in linear time will execute in approximately the same time as an algorithm in constant time on modern hardware, there’s little benefit to using Binet’s formula for solving this problem.

Matrix

require 'matrix'

M = Matrix[[0, 1], [1, 1]]

def F(n)
  return n if n == 0 or n == 1
  lower_right(M ** (n - 1))
end

def lower_right(matrix)
  return matrix[matrix.row_size - 1, matrix.column_size - 1]
end

Update: After reading a few of the comments on Reddit, I decided to add the matrix form solution to the list of approaches for this problem. The Wikipedia article contains a better explanation of the theory than I could ever provide, so I’ll just explain how the above algorithm works.

To perform exponentiation of a matrix, we can continuously multiply the matrix by itself. This is accomplished by using the following formula:

Using this formula with the original matrix M = [[0,1], [1,1]], we can calculate the matrix for F(5) where the lower right value is the Fibonacci number.

This algorithm will execute in logarithmic time linear time, providing us with an efficient and accurate method for calculating Fibonacci numbers.

I hope my tutorial for finding any number of the Fibonacci sequence has been helpful! I’m looking forward to diving into more topics in the coming weeks, so stay tuned for more algorithmic goodness!