//

// 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];

}

}