Fibnoci Series Using matrix Exponentiation

fibnoci_matrix_exponentiation.cpp

#include<bits/stdc++.h>

using namespace std;

int** multiply(int** a,int** b){
    int** c=new int*[2];
    for(int i=0;i<2;i++){
        c[i]=new int [2];
        for(int j=0;j<2;j++){
            c[i][j]=0;
            for(int k=0;k<2;k++){
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    return c;
}
int** power(int **m,int n){
    if(n==1){
        return m;
    }
    int** d=power(m,n/2);
    if(n%2==0){
        return multiply(d,d);
    }
    else{
        return multiply(m,multiply(d,d));
    }

}

int main(){
    
    int n;
    int** m=new int*[2];
    m[0]=new int[2];
    m[1]=new int[2];
    m[0][0]=1;
    m[1][0]=1;
    m[0][1]=1;
    int f[2][1]={1,0};
    cout<<"enter the n value";
    cin>>n;
    int** p=power(m,n-2);
    int fib=p[0][0]*f[0][0]+p[0][1]*f[1][0]+p[1][0]*f[0][0]+p[1][1]*f[1][0];
    cout<<fib;



    }