// Fib.java
/******************* Recursive Fibonacci Numbers     *******/
/******************* Use the C.P.U. Timer in Java    *******/
/******************* Use of global variables in Java *******/
/******************* Roger Wainwright 3/26/98        *******/
/******************* Revised for Java2 8/15/00       *******/
import java.lang.*; // contains currentTimeMillis() (page 717)

public class Fib
{  public static int count;  // Global variable

   public static void main(String[] args)
   {
   long start, finish;
   double cputime;
   String word;
   int n;
   double result;
   ConsoleReader console = new ConsoleReader(System.in);

   while (true)  
     { System.out.print("Enter n to calculate fib(n)");
       System.out.println("  or Enter zero or less to quit");
       n = console.readInt();
       if(n<=0) break;
       System.out.println("enter r-recursive, i-iterative, b-both");
       word = console.readLine(); // inputs "r", "i" or "b" as a string

       // Reminder: Do not use == to compare strings as in the following.
       // The following fails.  Instead we must use .equals
       // if (word=="i" || word=="b")

       /** invoke iterative fib function **/
       if ((word.equals("i")) || (word.equals("b")))
	 { start = System.currentTimeMillis(); // get the current time
           result = itfib(n);
	   finish = System.currentTimeMillis(); // get the current time
           System.out.print("ITERATIVE: result = " + result);
           // calculate runing time in seconds
           // Substract start from finish
	   // Note I did not allow for the day boundary.  The time
	   // will not be correct if execution occurs over the midnight
	   // boundary.
           cputime = (finish - start) / 1000.0;
	   System.out.println("   CPU TIME in Seconds = " + cputime);
         }

       /** invoke recursive fib function **/
       if ((word.equals("r")) || (word.equals("b")))
         { count = 0;
	   start = System.currentTimeMillis(); // get the current time
           result = fib(n);
	   finish = System.currentTimeMillis(); // get the current time
           System.out.print("RECURSIVE: result = " + result);
           // calculate runing time in seconds
           // Substract start from finish
	   // Note I did not allow for the day boundary.  The time
	   // will not be correct if execution occurs over the midnight
	   // boundary.
           cputime = (finish - start) / 1000.0;
           System.out.println("   CPU TIME in Seconds = " + cputime);
           System.out.println("count = " + count);
           System.out.println();
         }
     }// end while
   }// end main
/**************************************************************/
public static double fib(int n)
   {
   count++; // Global variable.  Count records the number of recursive
	    // calls that were made to fib.
   if (n==1) return 0;
   if (n==2) return 1;
   return( fib(n-1) + fib(n-2) );
   }
/**************************************************************/
public static double itfib(int n)
   {
   double i,j,k,m;
   if (n==1) return 0;
   if (n==2) return 1;
   i = 0; j = 1; k=0;  // set k to zero because the compiler requested it
   for (m = 3; m<=n; m++)
     { k = i + j;
       i = j; j = k;
     }
   return k;
   }
/**************************************************************/
}// end class