// testing the speeds of recursive and non-recursive Fibs
// Barry Cornelius, 22nd November 1999
public class RunFib
{
   public static void main(final String[] pArgs)
   {
      final int tLastTargetValue = 100;
      long iStartTime = 0;
      int iResult = 0;
      long iFinishTime = 0;
      long iTimeTaken = 0;
      for (int tTargetValue = 2; tTargetValue<=tLastTargetValue;
				 tTargetValue++)
      {
         System.out.print(tTargetValue);
         System.out.flush();
	 iStartTime = System.currentTimeMillis();
         iResult = iNRFib(tTargetValue);
	 iFinishTime = System.currentTimeMillis();
	 iTimeTaken = iFinishTime - iStartTime;
         System.out.print(" " + iResult + " " + iTimeTaken);
         System.out.flush();
	 iStartTime = System.currentTimeMillis();
         iResult = iRFib(tTargetValue);
	 iFinishTime = System.currentTimeMillis();
	 iTimeTaken = iFinishTime - iStartTime;
         System.out.println(" " + iResult + " " + iTimeTaken);
      }
   }
   private static int iRFib(final int n)
   {
      if (n<=1)
      {
	 return n;
      }
      else
      {
	 return iRFib(n - 1) + iRFib(n - 2);
      }
   }
   private static int iNRFib(final int n)
   {
      if (n<=1)
      {
	 return n;
      }
      else
      {
	 int tLastTerm = 0;
	 int tNewTerm = 1;
	 for (int tTermNumber = 2; tTermNumber<=n; tTermNumber++)
	 {
	    final int tLastButOneTerm = tLastTerm;
	    tLastTerm = tNewTerm;
	    tNewTerm = tLastButOneTerm + tLastTerm;
         }
	 return tNewTerm;
      }
   }
}