//

// Small Java program to demonstrate computation of Fibbonacci numbers using

// the binary exponentiation algorithm

//

// Written by Alfredo De la Fuente and Samuel Vidal 2012

//



package projects;

import javax.swing.JOptionPane;



public class FibonacciRecursion

{

public static void main(String [] args)

{

int n = Integer.parseInt(JOptionPane.showInputDialog("The n Fibonacci term is: "));


System.out.println("Fibonacci number "+n);


long start = System.nanoTime();


int fib = DummyFib(n);


long end = System.nanoTime();


System.out.print(fib+"\n"+(end-start)+" Nanoseconds"+"\n"+"---------"+"\n");


start = System.nanoTime();


fib = SmartFib(n);


end = System.nanoTime();


System.out.print(fib+"\n"+(end-start)+" Nanoseconds"+"\n"+"---------"+"\n");

}


private static int DummyFib (int n)

{

if (n < 2) return 1 ;

return DummyFib(n-1) + DummyFib(n-2) ;

}


private static int [][] MatrixMult (int a[][], int b[][])

{

int [][] product = new int [a[0].length][b.length] ;


for (int i = 0 ; i < a.length ; i++)

{

for (int j=0;j<b[0].length ; j++)

{

product[i][j]=0;


for (int k = 0 ; k < b[0].length ; k++)

{

product[i][j] += a[i][k] * b[k][j];

}

}

}


return product;

}



private static  int SmartFib(int n)

{

if (n < 2) return 1;

//Initial values of recursion

// Companinon matrix

int [][] b = new int[2][2];

b[0][0]=1;

b[0][1]=1;

b[1][0]=1;

b[1][1]=0;


// Identity matrix

int [][] c = new int[2][2];

c[0][0]=1;

c[0][1]=0;

c[1][0]=0;

c[1][1]=1;

while(n > 0)

{

if (n % 2 == 1) c = MatrixMult(c,b);


b = MatrixMult(b,b);

n /= 2;

}


return c[0][0];

}

}