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$$$.

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

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