Computing Fibonacci Sequence with Matrix Multiplication

Fibonacci Sequence as Recursive Formula 

$F_0 = 0$

$F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, \quad ^\forall n \ge 2$

 

Fibonacci Sequence as Matrix Multiplication Form

$\begin{vmatrix} F_n \\ F_{ n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{n-1} \cdot  \begin{vmatrix} F_1 \\ F_0 \end{vmatrix}, \quad ^\forall n\ge 1$

 

Fast Recursive Powering for elements of Monoid

Suppose we are calculating $X^n$ for $X \in \mathcal{M}, n \in \mathbb{N}$

if $n=1$, $X$ is the result

if $n$ is even, calculate $X^{\frac{n}{2}}$ first and square it.

if $n$ is odd, calculate $X^{\frac{n-1}{2}}$ first and square it. then multiply $X$ to it.

We can cleary see this method needs $\lfloor \log_{2} n \rfloor$ monoid operations because each recursive function call, n becomes half of it.

 

Check this for the iterative Algorithm

Fast Iterative Powering for elements of Monoid

Suppose we are calculating $X^n$ for $X \in \mathcal{M}, n \in \mathbb{N}$

let $I$ the identity element of $\mathcal{M}$

First start by expressing $n$ with binary number. 

We can calculate all $X^k$ for $k \in \mathbb{N}, k \le \lfloor \log_{2} n \rfloor$ in $\lfloor \log_{2} n \rfloor$ monoid operations by keep squaring the element starting from $X$

starting from Initial result $I$,  if the $k$th bit of $n$ is $1$, we multiply $X^k$ to the result.

By this procedure, we can calculate $X^n$ in $\lfloor \log_{2} n \rfloor$ monoid operations.

 

Since Matrix and it's multiplication operation is a Monoid,

we can apply Fast Iterative Powering to calculate the $n$th Fibonacci Number.

 

Number of bits in $F_n$

Let's consider $n \ge 2$. Since $F_n = F_{n-1} + F_{n-2}  \ge 2\times F_{n-2}$, we can easily show $F_n \ge 2^{n-2}, $ by induction.

Similary, we can show $F_n < 2^{n-1}$.

In conclusion, $2^{n-2} \le F_{n} < 2^{n-1}$ and the number of bits in $F_n$ is  $\Theta\left(n\right)$

 

Matrix Multiplication

Naive Matrix Multiplication between $n \times n$ matrixs requires $O\left(n^3 \right)$ Integer multiplications and additions. The fastest algorithm current is Willams' Algorithm due to wikipedia. To find advanced informations, check out this document. However, we are only treating $n=2$ in this problem, so 8 multiplications and 4 additions are enough for us. 

 

Integer multiplication in ${\textbf O\left(n \log n \right)}$ time
Pages 563-617 from Volume 193 (2021), Issue 2 by David Harvey, Joris van der Hoeven

https://hal.archives-ouvertes.fr/hal-02070778v2/document

reduce the integer multiplication problem to a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two.

 

This Algorithm uses fast fourier transform to compute integer multiplication

 

Analysis of bit operations in Computing Fibonacci Sequence with Matrix Multiplication

let $T\left(n\right)$ the number of bit operations to calculate $\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^n$

Brielfy, let's think $\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^n$ contains $n$ bit elements.

Then, $T\left(n\right) = T\left(\frac{n}{2}\right) + O\left(n \log n \right) = O\left(n \log ^2 n \right)$

What will be the tight $T\left(n\right)$? Since we can't apply master theorem to compute it, we need an another method.