import java.math.*;

public class Fibotesti {
    public static BigInteger fibo1(int n) {
        if (n == 0) return BigInteger.ZERO;
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
        return b;
    }

    public static BigInteger[][] kerro(BigInteger[][] a, BigInteger[][] b) {
        return new BigInteger[][] {{a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])),
                                    a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
                                   {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])),
                                    a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))}};
    }

    public static BigInteger[][] laske(int n) {
        if (n == 1) return new BigInteger[][] {{BigInteger.ZERO, BigInteger.ONE},
                                               {BigInteger.ONE, BigInteger.ONE}};
        if (n % 2 == 0) {
            BigInteger[][] p = laske(n/2);
            return kerro(p, p);
        } else {
            return kerro(laske(n-1), laske(1));
        }
    }

    public static BigInteger fibo2(int n) {
        if (n == 0) return BigInteger.ZERO;
        BigInteger[][] tulos = laske(n);
        return tulos[0][1];
    }

    public static BigDecimal[] kerro(BigDecimal[] a, BigDecimal[] b) {
        BigDecimal b5 = new BigDecimal(5);
        return new BigDecimal[] {a[0].multiply(b[0]).add(b5.multiply(a[1]).multiply(b[1])),
                                 a[0].multiply(b[1]).add(a[1].multiply(b[0]))};
    }

    public static BigDecimal[] laske(BigDecimal[] a, int n) {
        if (n == 1) return a;
        if (n % 2 == 0) {
            BigDecimal[] p = laske(a, n/2);
            return kerro(p, p);
        } else {
            return kerro(laske(a, n-1), a);
        }
    }

    public static BigInteger fibo3(int n) {
        BigDecimal[] a = {new BigDecimal(0.5), new BigDecimal(0.5)};
        BigDecimal[] b = {new BigDecimal(0.5), new BigDecimal(-0.5)};
        a = laske(a, n);
        b = laske(b, n);
        return a[1].subtract(b[1]).toBigInteger();
    }

    public static void main(String[] args) {
        int koko = 1000000;
        System.out.println("Lasketaan F(" + koko + ")");
        long alku = System.currentTimeMillis();
        fibo1(koko);
        long loppu = System.currentTimeMillis();
        System.out.println("Perusalgoritmi: " + (loppu-alku) + " ms");
        alku = System.currentTimeMillis();
        fibo2(koko);
        loppu = System.currentTimeMillis();
        System.out.println("Matriisialgoritmi: " + (loppu-alku) + " ms");
        alku = System.currentTimeMillis();
        fibo3(koko);
        loppu = System.currentTimeMillis();
        System.out.println("Kaava-algoritmi: " + (loppu-alku) + " ms");
    }
}