import java.math.*;

public class Fibotesti2 {
    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 class BigBinary {
        public BigInteger mantissa;
        public int exponent;
        private static BigInteger two = new BigInteger("2");
        
        public BigBinary(BigInteger mantissa, int exponent) {
            if(mantissa.equals(BigInteger.ZERO)) {
                this.mantissa = BigInteger.ZERO;
                this.exponent = 0;
                return;
            }
            
            while(mantissa.and(BigInteger.ONE).equals(BigInteger.ZERO)) {
                mantissa = mantissa.divide(two);
                exponent++;
            }
            
            this.mantissa = mantissa;
            this.exponent = exponent;
        }
        
        public BigBinary multiply(BigBinary other) {
            return new BigBinary(mantissa.multiply(other.mantissa), exponent + other.exponent);
        }
        
        public BigBinary add(BigBinary other) {
            if(exponent > other.exponent) return other.add(this);
            
            return new BigBinary(mantissa.add(other.mantissa.shiftLeft(other.exponent - exponent)), exponent);
        }
        
        public BigBinary subtract(BigBinary other) {
            if(exponent < other.exponent) {
                return new BigBinary(mantissa.subtract(other.mantissa.shiftLeft(other.exponent - exponent)), exponent);
            } else {
                return new BigBinary(mantissa.shiftLeft(exponent - other.exponent).subtract(other.mantissa), other.exponent);
            }
        }
    }

    private static BigBinary b5 = new BigBinary(new BigInteger("5"), 0);
    public static BigBinary[] kerro(BigBinary[] a, BigBinary[] b) {
        return new BigBinary[] {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 BigBinary[] laske(BigBinary[] a, int n) {
        if (n == 1) return a;
        if (n % 2 == 0) {
            BigBinary[] p = laske(a, n/2);
            return kerro(p, p);
        } else {
            return kerro(laske(a, n-1), a);
        }
    }

    public static BigInteger fibo3(int n) {
        BigBinary[] a = {new BigBinary(BigInteger.ONE, -1), new BigBinary(BigInteger.ONE, -1)};
        BigBinary[] b = {new BigBinary(BigInteger.ONE, -1), new BigBinary(BigInteger.ONE.negate(), -1)};
        a = laske(a, n);
        b = laske(b, n);
        return a[1].subtract(b[1]).mantissa;
    }

    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();
        BigInteger res2 = fibo2(koko);
        loppu = System.currentTimeMillis();
        System.out.println("Matriisialgoritmi: " + (loppu-alku) + " ms");
        alku = System.currentTimeMillis();
        BigInteger res3 = fibo3(koko);
        loppu = System.currentTimeMillis();
        System.out.println("Kaava-algoritmi: " + (loppu-alku) + " ms");
        System.out.println("Kaava- ja matriisialgot samaa mieltä: " + res3.equals(res2));
    }
}