### iamrajiv's blog

By iamrajiv, history, 5 weeks ago,

The Fibonacci numbers occur as the ratio of successive convergents of the continued fraction for $\varphi$, and the matrix formed from successive convergents of any continued fraction has a determinant of $+1$ or $-1$.

$\varphi=1+\cfrac1{1+\cfrac1{1+\cfrac1{1+\cfrac1{1+\ddots}}}}$

The matrix representation gives the following closed-form expression for the Fibonacci numbers i.e.

${\begin{pmatrix}1&1\\\ 1&0\end{pmatrix}}^n=\begin{pmatrix}F_{n+1}&F_n\\\ F_n&F_{n-1}\end{pmatrix}$

The matrix is multiplied $n$ time because then only we can get the $(n+1)^{th}$ Fibonacci number as the element at the row and the column $(0,0)$ in the resultant matrix.

If we apply the above method without using recursive multiplication of matrix, then the Time Complexity: $O(n)$ and Space Complexity: $O(1)$.

But we want Time Complexity: $O(log\ n)$, so we have to optimize the above method, which can be done by recursive multiplication of matrix to get the $n^{th}$ power.

Implementation of the above rule can be found below.

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/*
The function that returns nth Fibonacci number.
*/

int fib(int n) {
int F[2][2] = {{1, 1}, {1, 0}};
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}

/*
Optimized using recursive multiplication.
*/

void power(int F[2][2], int n) {
if ( n == 0 || n == 1)
return;
int M[2][2] = {{1, 1}, {1, 0}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

int main() {
printf("%d\n", fib(15));
/*
15th Fibonacci number is 610.
*/
return 0;
}


• -14

 » 5 weeks ago, # | ← Rev. 2 →   +16 Is this tested? :/  power(F, n / 2); multiply(F, F); I think you're supposed to do multiply(F, F) before power(F, n / 2);.edit: oops my bad
•  » » 5 weeks ago, # ^ |   0 That would be incorrect, like for fib(15) answer should be 160. If I do multiply(F, F) before power(F, n / 2), it will give output 89, which is incorrect.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Just a side note, interchanging the line does not work because the matrix M is hard-coded in the power() function. Otherwise, both ordering would give the correct answer. void power(int F[2][2], int n) { if (n == 0 || n == 1) return; int M[2][2] = {{F[0][0], F[0][1]}, {F[1][0], F[1][1]}}; // modified power(F, n / 2); multiply(F, F); if (n % 2 != 0) multiply(F, M); } Hard-coding values can lead to confusing situations and a pain to debug, hence, should be avoided.
 » 5 weeks ago, # |   +13 I always had trouble understanding where the matrix came from. Till I realized:$\begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \cdot\begin{bmatrix} a_2 & b_2 \\ c_2 & d_2 \end{bmatrix}=\begin{bmatrix} a_1\cdot a_2 + b_1\cdot c_2 & a_1\cdot b_2 + b_1\cdot d_2 \\ c_1\cdot a_2 + d_1\cdot c_2 & c_1\cdot b_2 + d_1\cdot d_2 \end{bmatrix}$Notice that, we need the the first cell to have a+b and any to have whatever but to be able to do the transition. So, if we substituted $a_2=1$, $c_2=1$ then the first cell in the first row and first column would have $a+b$. If we can also make that $b_1$ change to $a$, then we are basically done as this will be the transition. If we set $b_2=1$ and $d_2=0$, this will negate the $b_1$ and add 1 of $a_1$. And we are done! We've done it:$\begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \cdot\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}=\begin{bmatrix} a_1+b_1 & a_1 \\ useless & useless \end{bmatrix}$We basically won't use the other two cells in the transition, but they are essential for making the matrix complete as the first cell and second cell in the first row transition are dependent on it for the complete transition.