/******************************************************************************
 *  Compilation:  javac Fibonacci2.java
 *  Execution:    java Fibonacci2 n
 *
 *  Computes and prints the first n Fibonacci numbers using the
 *  following recurrence:
 *
 *         f(1) = f(2) = 1
 *         f(n) = f((n+1)/2)^2 + f((n-1)/2)^2   if n is odd
 *         f(n) = f(n/2 + 1)^2 - f(n/2 - 1)^2   if n is even
 *
 *   % java Fibonacci2 7
 *   0
 *   1
 *   1
 *   2
 *   3
 *   5
 *   8
 *   13
 *
 *   Remarks
 *   -------
 *    - The 93rd Fibonacci number would overflow a long
 *
 ******************************************************************************/

public class Fibonacci2 {

    public static long fib2(int n) {
        int f = 0, g = 1;
        for (int i = 1; i <= n; i++) {
            f = f + g;
            g = f - g;
         }
         return f;
    }

    public static long fib(int n) {
        // base case
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n >= 93) throw new RuntimeException("Input out of bounds");

        // n is odd
        if (n % 2 != 0) {
            long a = fib((n+1)/2);
            long b = fib((n-1)/2);
            return a*a + b*b;
        }

        // n is even
        long a = fib(n/2 + 1);
        long b = fib(n/2 - 1);
        return a*a - b*b;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        for (int i = 0; i <= n; i++) {
            StdOut.println(i + ": " + fib(i) + " " + fib2(i));
        }
    }

}