/*
  Fibonacci3 (third version)
  written by Keith Fenske
  Wednesday, 1 May 2002
  Copyright (c) 2002 by Keith Fenske.  All rights reserved.

  This Java program computes the Fibonacci sequence 1, 1, 2, 3, 5, 8, ...
  using the explicit formula on page 99 of "Discrete Mathematical
  Structures".

  This third version uses regular "int" numbers for the parameter to the
  Fibonacci function, but "long" numbers for the result.  The explicit
  formula is calculated with "double" floating-point numbers, which have
  only about 15 digits of accuracy.  The largest 64-bit "long" value that
  can be calculated is f(92).  The computer will report the result as
  7,540,113,804,746,369,024.  Compare this with the correct number which is
  7,540,113,804,746,346,429.  You can see that only the first 14 digits are
  correct.  The last 5 digits are random noise.  This is a common problem
  when working with floating-point numbers: not all the digits in the number
  are meaningful.
*/

import cs1.Keyboard;              // import Lewis/Loftus keyboard class
//                           http://duke.csc.villanova.edu/jss/keyboard.html

public class Fibonacci3
{
  public static void main(String[] args)
  {
    int n;                        // function parameter from user

    System.out.println("\nThis Java program computes the Fibonacci sequence");
    System.out.println("1, 1, 2, 3, 5, 8, 13, 21, ... using the explicit");
    System.out.println("formula on page 99 of the CS 1303 textbook.");

    do
    {
      System.out.print("\nWhat is the parameter n?  (Type 0 to quit.)  ");
      n = Keyboard.readInt();
      if (n > 0)
        System.out.println("f(" + n + ") = " + f(n));
    }
    while (n > 0);
    
  } // end of main()

/*
  f() method

  This method calculates the Fibonacci sequence using the explicit formula.
  The parameter n is a regular "int" number (32 bits).  The function result
  is a "long" integer (64 bits).  All intermediate calculations are done
  with double-precision floating-point numbers.
*/
  static long f(int n)
  {
    long result;                  // the result of this function
    double root;                  // we use sqrt(5) four times
    double x;                     // floating-point version of result

    if (n < 1)
    {
      System.out.println("domain error in f(), n = " + n);
      result = -1;
    }
    else
    {
      root = Math.sqrt(5.0);      // calculate and save this square root
      x = Math.pow((1 + root)/2, (double) n) / root
        - Math.pow((1 - root)/2, (double) n) / root;
      result = Math.round(x);     // round to nearest integer
    }
    return result;

  } // end of f()

} // end of class