/* Different versions of Fibonacci function, from worst to best

   This program illustrates different algorithmic approaches to the
same problem.  fib1 is called "naive" because it looks mathematically
elegant, but is computationally unacceptable: its time complexity is also
order(fib n), which is roughly O(1.5**n).  fib2 is easy to implement using
a loop, and is clearly O(n).  It's not the best solution.  fib3 implements
a closed formula.  However, upon closer examination we see that this function
calls the exponent (Math.pow) function, which is not O(1).  Also, since
this algorithm uses floating point approximations of irrational numbers, it
is not always accurate for the least significant digits, which are usually
the digits that are used in practical applications (such as cryptography). 
fib4 represents the best solution: it uses matrix multiplication and binary
factorization to calculate an integer representation of the Fibonacci number
in log(n) steps, although theoretically it's still O(n) since technically it
requires O(n) digits to represent Fib(n).  In practice, however, we can
usually restrict the number of digits to a constant (e.g. 'long' type
is 64 bits).

Of the four versions, only fib1 is recursive.  fib2 can be implemented using
recursion in a programming language that optimizes "tail recursion", but
Java is not one of these languages.  On java, implementing fib2 recursively
will overflow the stack if n is too large.  The mpow function that's part
of fib4 is implemented non-recursively here, but can be implemented safely
using recursion even in java, because the depth of recursion is O(log n).
*/

public class Fibonacci
{
    static long fib1(int n)  // "naive fibonacci" implementation
    {
	if (n<3) return 1; else return fib1(n-1) + fib1(n-2);
    }

    static long fib2(int n) // iterative, O(n) steps
    {
	long a = 1, b = 1;
	while (n>2)
	    {   b = a+b;  
		a = b-a;  // a becomes previous b
		n--;
	    }
	return b;
    }

    // floating point approximation (not enough precision)
    static long fib3(int n)
    {
	double s = Math.sqrt(5); // square root of 5
	double m = (Math.pow(s+1,n) - Math.pow(s-1,n)) / (Math.pow(2,n)*s);
	return (long)(m+0.5);
    }//fib 3
        

    // Best version of Fib (without floating point calculations)
    // first, our own version of .pow (to an int power), for illustration:
    static long power(long x, int n) // calcs x**n in log(n) steps
    {
	long ax = 1; // accumulator
	long factor = x;  // x**1
	while (n>0)
	    {
		if (n%2==1) ax *= factor;
		factor *= factor;
		n /=2; // shift right
	    }
	return ax;
    } // integer power by binary factorization of the exponent.

    // represent 2x2 matrix by {a,b,c,d}
    // a b    0 1   
    // c d    2 3   
    static long[] FM = {1,1,1,0};
    static long[] ID = {1,0,0,1}; // Identity matrix, M**0 = ID
    // FM**n gives matrix    fib(n+1)  fib(n)
    //                       fib(n)    fib(n-1)

    // 2x2 matrix multiplication:
    static long[] mmult(long[] A,long []B)
    {
	long a = A[0]*B[0] + A[1]*B[2];
	long b = A[0]*B[1] + A[1]*B[3];
	long c = A[2]*B[0] + A[3]*B[2];
	long d = A[2]*B[1] + A[3]*B[3];
	long[] answer = {a,b,c,d};
	return answer;
    }
    // multiply 2x2 matrix to the nth power in log(n) steps
    static long[] mpow(long[] A, int n)
    {
	long[] ax = ID;
	long[] factor = A;
	while (n>0)
	    {
		if (n%2==1) ax = mmult(ax,factor);
		factor = mmult(factor,factor);
		n = n/2;
	    }
	return ax;
    }
    static long fib4(int n)  // best version of Fibonacci function
    {
	if (n<3) return 1;
	else return mpow(FM,n-1)[0];
    }
    
    public static void main(String[] av)
    {
	int n = 10;
	if (av.length>0) n = Integer.parseInt(av[0]);
	System.out.println( fib4(n) );
    }//main
}//Fibonacci