Most programmers are familiar with the naïve \(O(2^n)\) and the memoized \(O(n)\) algorithms for computing the n^th Fibonacci number. However, with a bit of math, you can get the time down to \(O(\log_2n)\).

Let’s start with the basics. If we write \(F_n\) for the n^th Fibonnaci number, the values for the entire sequence are: \(F_1 = F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\). In code, we write:

let rec fib_naive n =
  if n < 1
  then failwith "undefined"
  else if n = 1 || n = 2
  then big_int_of_int 1
  else add_big_int (fib_naive (n - 1))
                   (fib_naive (n - 2))
;;

Every non-base call of fib_naive does two more calls to itself. This is \(O(2^n)\). We can do better by memoizing the results or by computing the values iteratively:

let fib_memo =
  let res = Hashtbl.create 16 in
  Hashtbl.add res 1 (big_int_of_int 1);
  Hashtbl.add res 2 (big_int_of_int 1);
  let rec fib n =
    if n < 1 then
      failwith "undefined";
    match Hashtbl.find res n with
    | resx ->
      resx
    | exception _ ->
      let resx =
        add_big_int (fib (n - 1)) (fib (n - 2))
      in
      Hashtbl.add res n resx;
      resx
  in
  fib
;;

let fib_iter n =
  if n < 1 then
    failwith "undefined";
  let one = big_int_of_int 1 in
  if n = 1 || n = 2
  then
    one
  else
    let rec loop a b n =
      if n = 0
      then b
      else loop b (add_big_int a b) (n - 1)
    in
    loop one one (n - 2)
;;

We see that fib_memo is like fib_naive, but the computation for each n is done only once. Similarly, fib_iter is just an iteration up to n, where each step computes the next Fibonacci number. Both functions are \(O(n)\).

Can we do better? Yes, we can. But first, we need to know about the following matrix.

\[ M = \begin{bmatrix} 1 & {\color{blue}1} \\ 1 & 0 \end{bmatrix} \\ M^2 = \begin{bmatrix} 2 & {\color{blue}1} \\ 1 & 1 \end{bmatrix} \quad M^3 = \begin{bmatrix} 3 & {\color{blue}2} \\ 2 & 1 \end{bmatrix} \\ M^4 = \begin{bmatrix} 5 & {\color{blue}3} \\ 3 & 2 \end{bmatrix} \quad M^5 = \begin{bmatrix} 8 & {\color{blue}5} \\ 5 & 3 \end{bmatrix} \]

We notice that all the elements of \(M^n\) are Fibonacci numbers: \(M^n_{0,0} = F_{n+1}\), \(M^n_{1,0} = M^n_{0,1} = F_n\), and \(M^n_{1,1} = F_{n-1}\). We can prove this easily by induction: the base case is obvious, and the induction step boils down to:

\[ \begin{align} M^n \times M &= \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} \times \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \\ &= \begin{bmatrix} F_{n+1} + F_n & F_{n+1} \\ F_n + F_{n-1} & F_n \end{bmatrix} \\ &= \begin{bmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{bmatrix}\\ &= M^{n+1} \end{align} \]

So, in order to find the n^th Fibonacci number, we need to compute \(M^n\) and take the top-right or bottom-left corners. Since matrix multiplication is associative, we can use the usual \(O(\log_2n)\) algorithm to compute \(M^n\):

let rec pow ~mult ~n x =
  if n < 1
  then
    failwith "undefined"
  else if n = 1
  then
    x
  else if n mod 2 = 0
  then
    let y = pow ~mult x ~n:(n / 2) in
    mult y y
  else
    let y = pow ~mult x ~n:(n / 2) in
    mult x (mult y y)
;;

type mat =
  { m00 : big_int; m01 : big_int;
    m10 : big_int; m11 : big_int;
  }

let mat_mult a b =
  let ( * ) = mult_big_int in
  let ( + ) = add_big_int in
  { m00 = a.m00 * b.m00 + a.m01 * b.m10;
    m01 = a.m00 * b.m10 + a.m01 * b.m11;
    m10 = a.m10 * b.m00 + a.m11 * b.m10;
    m11 = a.m10 * b.m10 + a.m11 * b.m11;
  }
;;

let m_fib =
  let big = big_int_of_int in
  { m00 = big 1; m01 = big 1;
    m10 = big 1; m11 = big 0;
  }
;;

let fib_mat n =
  if n < 1 then
    failwith "undefined";
  let m = pow ~mult:mat_mult m_fib ~n in
  m.m01
;;

To summarise, we started off with the naïve exponential algorithm, then brought it down to linear time by memoizing or factoring out repeated computations, and finally rewrote it to work in logarithmic time by applying a bit of matrix math.

---

As an aside, the story behind the name “Fibonacci” is quite amusing. The mathematician’s name is really Leonardo Pisano. However, like most people in the middle ages, he included his father’s name when signing. Fibonacci literally means “son of Bonacci” and it’s the name he came to be know as after scholars misread his signature. Now, if we were to talk about his father, we’d of course talk about “Fibonacci’s father”, which entails a reference to his real name in Latin, followed by a dereference in English. Hilarious.