/*
 *    Compute Fibonacci number using Dijkstra's recurrence:
 *
 *    F(2N-1)  = F(N-1)^2 + F(N)^2
 *    F(2N)    = (2 F(N-1) + F(N)) F(N)
 *   
 *    Use the following BigInteger implementation for maximum performance:
 *    https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigInteger.java
 *
 */
import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    private static Map<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>();
    static {
            cache.put(BigInteger.ONE,  BigInteger.ONE);
            cache.put(BigInteger.ZERO, BigInteger.ZERO);
    }

    public static BigInteger fibonacci(BigInteger n) {

        if (cache.containsKey(n)) return cache.get(n);
        // odd
        if (n.testBit(0)) {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.add(1);
            BigInteger result = fibonacci(n2).multiply(fibonacci(n2)).add(fibonacci(n3).multiply(fibonacci(n3)));
            cache.put(n, result);
            return result;
        }
        // even
        else {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.add(-1);
            BigInteger result = fibonacci(n2).multiply(fibonacci(n2).add(fibonacci(n3).add(fibonacci(n3))));
            cache.put(n, result);
            return result;
        }
    }

    private static void printResult(BigInteger num){
        System.out.printf("  Number of bits:  %d%n", num.bitLength());
        byte[] numHex = num.toByteArray();
        System.out.print("  First 10 bytes: ");
        for (int i = 0; i < (numHex.length < 10 ? numHex.length : 10); i++) {
            System.out.printf(" %02x", numHex[i]);
        }
        System.out.println();
        if (numHex.length > 20){
            System.out.print("  Last 10 bytes : ");
            for (int i = numHex.length - 10; i < numHex.length; i++) {
                System.out.printf(" %02x", numHex[i]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) { 
        long time = System.currentTimeMillis();
        BigInteger N = new BigInteger(args[0]);
        System.out.printf("Searching for Fibonacci(%,d)%n", Integer.parseInt(args[0]));
        BigInteger res = fibonacci(N);
        printResult(res);
        System.out.printf("  Time to calculate %d ms%n%n", System.currentTimeMillis() - time); 
    }
}