import java.math.*;

// compare iteration to closed form

public class Fib {

  public static void main(String[] args) {

    int n = Integer.parseInt(args[0]);

    long start = System.currentTimeMillis();

    BigInteger fib1 = iteration(n);
    long finish1 = System.currentTimeMillis();

    double fib2 = closedForm(n);
    long finish2 = System.currentTimeMillis();

    BigDecimal fib3 = closedFormBig(n);
    long finish3 = System.currentTimeMillis();

    System.out.println("iteration " + n + " " + (finish1-start) + " " + fib1);

    System.out.println("closedForm " + n + " " + (finish2-finish1) + " " + fib2);

    System.out.println("closedFormBig " + n + " " + (finish3-finish2) + " " + fib3);

  }

  public static BigInteger iteration(int n) {

    if (n == 0) return BigInteger.ZERO;
    if (n == 1) return BigInteger.ONE;

    BigInteger nMinus2 = BigInteger.ZERO;
    BigInteger nMinus1 = BigInteger.ONE;
    BigInteger total = nMinus1.add(nMinus2);

    for (int i = 1; i < n; i++) {
      total = nMinus1.add(nMinus2);
      nMinus2 = nMinus1;
      nMinus1 = total;
    }

    return total;
  }

  public static double closedForm(int n) {

    double sqrt5 = Math.sqrt(5.0);
    double goldenRatio = (1.0 + sqrt5) / 2.0;

    return ( Math.pow(goldenRatio,n) - Math.pow(1.0 - goldenRatio, n)) / sqrt5;

  } 

  public static BigDecimal closedFormBig(int n) {

    BigDecimal sqrt5 = new BigDecimal( Math.sqrt(5.0));
    BigDecimal goldenRatio = BigDecimal.ONE.add(sqrt5).divide(new BigDecimal(2));

    BigDecimal intermediate = BigDecimal.ONE.subtract(goldenRatio);
    intermediate = intermediate.pow(n);
    intermediate = goldenRatio.pow(n).subtract(intermediate);

    return intermediate.divide(sqrt5);
  } 

}