Attempting to solve the fibonacci series using matrix multiplication applying divide and conquer to reduce the complexity to O(logN)
package com.biplav.algorithms;
public class FibonacciSeries {
//2*2 matrix
static int[][] multiply(int[][] X, int[][] Y) {
int[][] response = new int[2][2];
response[0][0] = X[0][0]*Y[0][0] + X[0][1]*Y[1][0];
response[0][1] = X[0][0]*Y[0][1] + X[0][1]*Y[1][1];
response[1][0] = X[1][0]*Y[0][0] + X[1][1]*Y[1][0];
response[1][1] = X[1][0]*Y[0][1] + X[1][1]*Y[1][1];
return response;}
static int[][] power(int[][] X, int N) {
if(N == 1) {
return X;} else {
int[][] X2 = power(X,N/2);
return multiply(X2,X2);
}
}
public static int get(int n) {int[][] X = new int[][] {{1,1},{1,0}};
return power(X,n)[0][0];
}
public static void main(String[] args) {
System.out.println(get(4));
}
}