Finding Nth Fibonacci number in logarithmic time

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