class f1a {
// This program calculates the nth fibonacci number
// using alrogirhtm 1A: naive binary recursion
//
// compiled: javac f1a.java
// executed: java f1a n
// 

 // Naive binary recursion: F(n) = F(n-1) + F(n-2) */
 private static long fib(long n) {
       return n<2 ? n : fib(n-2)+fib(n-1);
 }

 // Method f1a.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static long f(long n) {
    if(n<0)
       return (n%2==0) ? -fib(-n) : fib(-n);
    else
       return fib(n);
 }

 // Method f1a.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f1a.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f1a ");
  System.exit(1);
 }
}

import java.math.BigInteger;
import java.util.HashMap;
class f1b {
// This program calculates the nth fibonacci number
// using alrogirhtm 1B: cached binary recursion / memoization
//
// compiled: javac f1b.java
// executed: java -Xss1047M f1b n
//

 // method f1b.fib(n,m) first checks if the result for 'n' has already
 // been caclculated. If so, the result is returned. Otherwise,
 // binary recursion F(n) = F(n-1) + F(n-2) is performed, its result
 // saved and returned.
 private static BigInteger fib(int n, HashMap<Integer, BigInteger> m) {
    if(m.containsKey(n)) return m.get(n);
    BigInteger result = n<=0 ? BigInteger.ZERO
                      : n==1 ? BigInteger.ONE
                      : fib(n-2, m).add(fib(n-1, m));
    m.put(n, result);
    return result;
 }

 // Method f1b.fib.n) creates the memoization container and calls f1b.fib(n,m)
 private static BigInteger fib(int n) {
     HashMap<Integer, BigInteger> memo = new HashMap<Integer, BigInteger>(n); 
     return fib(n, memo);
 }

 // Method f1b.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f1b.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f1b.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f1b <n>");
  System.exit(1);
 }
}

import java.math.BigInteger;
import java.util.LinkedList;
class f2a {
// This program calculates the nth fibonacci number
// using alrogirhtm 2A: cached linear recursion / random-access container
//
// compiled: javac f2a.java
// executed: java -Xss1047M f2a n
//

// method f2a.fib(l,n) adds the first two elements of the list, prepends the
// result to the list, decrements the counter, and returns the last value of
// the first element when the counter reaches zero.
 private static BigInteger fib(LinkedList<BigInteger> l, int n) {
    l.addFirst(l.peek().add(l.get(1)));
    return n<1 ? l.peek() : fib(l, n-1);
 }

// Initializes the list with (0,1) and calls the recursive function
 private static BigInteger fib(int n) {
     LinkedList<BigInteger> list = new LinkedList<BigInteger>(); 
     list.addFirst(BigInteger.ZERO);
     list.addFirst(BigInteger.ONE);
     return n<2 ? list.get(1-n) : fib(list, n-2);
 }

 // Method f2a.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f2a.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f2a.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f2a <n>");
  System.exit(1);
 }
}

import java.math.BigInteger;
class f2b {
// This program calculates the nth fibonacci number
// using algorithm 2B: linear recursion with accumulator
//
// compiled: javac f2b.java
// executed: java -Xss1047M f2b n
//

 // starting with x1=0 and x2=1, n times do the following:
 // calculate the sm of x1 and x2, place it in x2, place the old x2 in x1
 private static BigInteger fib(BigInteger x1, BigInteger x2, long n) {
     return n<1 ? x1 : fib(x1.add(x2), x1, n-1);
 }
 private static BigInteger fib(long n) {
     return fib(BigInteger.ZERO, BigInteger.ONE, n);
 }

 // Method f2b.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(long n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f2b.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f2b.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f2b <n>");
  System.exit(1);
 }
}

import java.math.BigInteger;
class f2c {
// This program calculates the nth fibonacci number
// using alrogirhtm 2C: imperative loop with mutable variables
//
// compiled: javac f2c.java
// executed: java f2c n
//

 // starting with x1=0 and x2=1, n times do the following:
 // calculate the sm of x1 and x2, place it in x2, place the old x2 in x1
 private static BigInteger fib(long n) {
  BigInteger x1 = BigInteger.ZERO;
  BigInteger x2 = BigInteger.ONE;
  BigInteger tmp;
  for(long i=1;i<=n;i++) {
     x1=x1.add(x2);
     tmp=x2; x2=x1; x1=tmp;
  }
  return x1;
 }

 // Method f2c.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(long n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f2c.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f2c.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f2c <n>");
  System.exit(1);
 }
}

import java.math.BigInteger;
class f3a {
// This program calculates the nth fibonacci number
// using alrogirhtm 3A: matrix multiplication
//
// compiled: javac f3a.java
// executed: java f3a n


 // simple matrix multiplication, nothing fancy since I couldn't find a
 // proper Java way to do matrix multiplication
 private static BigInteger[][] mm(BigInteger[][] m1, BigInteger[][] m2) {
    int m1rows = m1.length;
    int m1cols = m1[0].length;
    int m2cols = m2[0].length;
    BigInteger[][] result = new BigInteger[m1rows][m2cols];
    for (int i=0; i<m1rows; i++)
        for (int j=0; j<m2cols; j++) {
            result[i][j] = BigInteger.ZERO;
            for (int k=0; k<m1cols; k++)
                result[i][j] = result[i][j].add(m1[i][k].multiply(m2[k][j]));
        }
    return result;
 }

 // exponentiation by repeated squaring,
 private static BigInteger[][] mpow(BigInteger[][] m, int n) {
     if(n<=0) {
         BigInteger[][] unity = {{BigInteger.ONE ,BigInteger.ZERO},
                                 {BigInteger.ZERO,BigInteger.ONE}};
         return unity;
     }
     BigInteger[][] b = mpow(mm(m,m), n>>1);
     return n%2==1 ? mm(m, b) : b;
 }

 // method f3a.fib raises the matrix (1,1)(1,0) to n-1st power and
 // returns the top left element.
 private static BigInteger fib(int n) {
     if(n==0) return BigInteger.ZERO;
     BigInteger[][] fm = {{BigInteger.ONE,BigInteger.ONE},
                          {BigInteger.ONE,BigInteger.ZERO}};
     fm = mpow(fm, n-1);
     return fm[0][0];
 }

 // Method f3a.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f3a.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f3a.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f3a <n>");
  System.exit(1);
 }
}

import java.math.BigInteger;
class f3b {
// This program calculates the nth fibonacci number
// using alrogirhtm 3B: fast recursion
//
// compiled: javac f3b.java
// executed: java f3b n

 // calculate a pair of fibonacci numbers according to
 // the recurrent relationship: 
 // F(2n-1) = F(n-1)^2 + F(n)^2
 // F(2n) = (2F(n-1) + F(n))F(n)
 //
 // in this function, f1 = F(n-1), f2 = F(n), f3 = F(n+1)
 private static BigInteger[] fib_rec(int n) {
     BigInteger[] r = new BigInteger[2];
     if(n<=0) {r[0]=BigInteger.ZERO; r[1]=BigInteger.ZERO; return r;}
     if(n==1) {r[0]=BigInteger.ZERO; r[1]=BigInteger.ONE;  return r;}
     BigInteger[] k = fib_rec(n/2);
     BigInteger f1 = k[0];
     BigInteger f2 = k[1];
     BigInteger f3 = f1.add(f2);
     if (n%2==1) {
         r[0]=f1.add(f3).multiply(f2);
         r[1]=f3.multiply(f3).add(f2.multiply(f2));
     } else {
         r[0]=f1.multiply(f1).add(f2.multiply(f2));
         r[1]=f1.add(f3).multiply(f2);
     }
     return r;
 }

 // method f3b.fib calls the recursive method fib_rec and returns
 // the second of the two numbers returned
 private static BigInteger fib(int n) {
     return fib_rec(n)[1];
 }

 // Method f3b.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f3b.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f3b.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f3b <n>");
  System.exit(1);
 }
}

import java.lang.Math;
import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
class f3c {
// This program calculates the nth fibonacci number
// using alrogirhtm 3C: Binet's formula with rounding
//
// compiled: javac f3c.java
// executed: java f3c n
//

  // Method f3c.isqrt(n) finds the inverse root of n using the following
  // recurrent equation: y(n+1) = 0.5*y(n)*[3 - x*y(n)^2]
  // It is faster than typical Newton-Raphson square root finding because
  // it does not use division.
  // Funny how Java implemented exponentiation by repeated squaring
  // for BigDecimals, but did not implement any sort of square root.
 private static BigDecimal isqrt(BigDecimal x, MathContext mc) {
     BigDecimal guess = new BigDecimal(1/Math.sqrt(x.doubleValue()));
     BigDecimal three = new BigDecimal(3);
     BigDecimal half = new BigDecimal(0.5);
     BigDecimal oldguess;
     do{ oldguess = guess;
         guess = half.multiply(guess.multiply(
                   three.subtract(x.multiply(guess.pow(2)))), mc);
     } while (oldguess.compareTo(guess) != 0);
     
     return guess;
 }

 // method f3c.fib(n) calculates the nth fibonacci number
 // as floor( phi^n/sqrt(5) + 1/2), where phi = (1+sqrt(5.0))/2;
 private static BigInteger fib(int n) {
    MathContext mc = new MathContext(n/2, RoundingMode.HALF_DOWN);
    BigDecimal is5 = isqrt(new BigDecimal("5"), mc);
    BigDecimal one = BigDecimal.ONE;
    BigDecimal half = new BigDecimal(0.5);
    BigDecimal phi = half.multiply(one.add(one.divide(is5, mc)));
    return phi.pow(n, mc).multiply(is5).toBigInteger();
 }

 // Method f3c.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f3c.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f3c.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f3c <n>");
  System.exit(1);
 }
}