Finding Nth Fibonacci number in logarithmic time

Revision en1, by iamrajiv, 2021-05-09 20:41:34

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;
}

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 iamrajiv 2021-05-09 20:41:34 2016 Initial revision (published)