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, int M);

void power(int F, int n);

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

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

/*
Optimized using recursive multiplication.
*/

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

void multiply(int F, int M) {
int x = F * M + F * M;
int y = F * M + F * M;
int z = F * M + F * M;
int w = F * M + F * M;
F = x;
F = y;
F = z;
F = 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)