Friday, October 10, 2014

Fibonacci Series With Matrix Multiplication in Java with recursion.

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