Fibonacci calculation via matrix multiplication in O(log2n).

FastFibonacci.c

#include <stdio.h>
#include <stdlib.h>
 
int basicMat[4] = { 1, 1, 1, 0 };
int calcMat[4];
 
int* mul(int mat1[4], int mat2[4]) {
    int i, newMat[4];
 
    newMat[0] = mat1[0] * mat2[0] + mat1[1] * mat2[2];
    newMat[1] = mat1[0] * mat2[1] + mat1[1] * mat2[3];
    newMat[2] = mat1[2] * mat2[0] + mat1[3] * mat2[2];
    newMat[3] = mat1[2] * mat2[1] + mat1[3] * mat2[3];
 
    for (i = 0; i < 4; ++i) {
        calcMat[i] = newMat[i];
    }
 
    return calcMat;
}
 
int* fib(int n) {
    if (n == 1) {
        return basicMat;
    }
 
    int* mat = fib(n / 2);
    mat = mul(mat, mat);
 
    if (n % 2 == 1) {
        mat = mul(mat, basicMat);
    }
 
    return mat;
}
 
int fibonacci(int n) {
    int* mat = fib(n);
    return mat[1];
}
 
int main () {
    int n;
    scanf("%d", &n);
 
    printf("Fn : %d\n", fibonacci(n));
}