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;
}
Tags fibonacci sequence, logarithmic, mathematics, number theory

History

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