Why am I not getting the right output for this implementation of nth Fibo Number?

Question

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
void mul ( long long f[2][2], long long m[2][2] );

void power (long long f[2][2], long long int n );
int fibo (long long int n);
int main (void)
{
    int c;
    cin>>c;
    while (c!= 0)
    {
        int n,val;

        cin>>n;
        val = fibo(n);
        cout<<val<<"\n";
        c--;
    }
    return 0;
} 

int fibo (long long int n)
{
    long long f[2][2] = {{1,1},{1,0}};
    if ( n == 0 )
        return 0;
    else
        power(f,n-1);
    return f[0][0];            
}


void power (long long f[2][2], long long int n )
{
    if ( n == 0 )
        return;
    long long m[2][2] = {{1,1},{1,0}};
    if ( n % 2 == 0 )
    {
        mul(f,f);
        power(f,n/2);
    }
    else
    {
        mul(f,f);
        mul(f,m);
        power(f,(n-1)/2);
    }
}

void mul ( long long f[2][2], long long m[2][2] )  
{ 
    long long x = f[0][0]*m[0][0] + f[0][1]*m[1][0];
    long long y = f[0][0]*m[0][1] + f[0][1]*m[1][1];
    long long z = f[1][0]*m[0][0] + f[1][1]*m[1][0];
    long long 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;
}

I made this code using the matrix exponentiation by squaring method. However, I am not getting the right answer. Why is that? Why am I not getting the correct output for the Fibo number for this? I am getting the output as

3rd Term: 8
4th Term: 21
5th Term: 55
6th Term: 377

Why is this happeining? I tried using the debugger but I am not able to spot the error.

Answer 1

The power(...) function looks buggy. How about this:

void power (long long f[2][2], long long int n )
{
    if ( n == 1 || n == 0 )  // if n == 1, the matrix f^1 should be kept untouched.
        return;              // if n == 0, f should be an identity. it is
                             // a special case here because of your divide-and-
                             // conquer logic.
    long long m[2][2] = {{1,1},{1,0}};
    if ( n % 2 == 0 )
    {
        power(f,n/2);        // given f = m^(n/2) is ready
        mul(f,f);            // m^n = m^(n/2) x m^(n/2)
    }
    else
    {
        power(f,(n-1)/2);    // given f = m^((n-1)/2) is ready
        mul(f,f);            // m^(n-1) = m^((n-1)/2) x m^((n-1)/2)
        mul(f,m);            // m^n = m^(n-1) x m
    }
}