by Paaras, Varalu, and Tanay

Algorithm 1: Matrix Exponentiation (Optimized)

public class FiboMatrix extends Fibo {

    public FiboMatrix() {
        super();
    }

    public FiboMatrix(int nth) {
        super(nth);
    }

    @Override
    protected void init() {
        super.name = "FiboMatrix extends Fibo";

        long[][] resultMatrix = matrixPower(baseMatrix, super.size - 1);

        for (int i = 0; i < super.size; i++) {
            super.setData(resultMatrix[0][1]);
            resultMatrix = matrixMultiply(baseMatrix, resultMatrix);
        }
    }

    private long[][] matrixPower(long[][] matrix, int exponent) {
        if (exponent == 1) return matrix;
        if (exponent % 2 == 0) {
            long[][] halfPower = matrixPower(matrix, exponent / 2);
            return matrixMultiply(halfPower, halfPower);
        } else {
            long[][] halfPower = matrixPower(matrix, (exponent - 1) / 2);
            return matrixMultiply(matrixMultiply(halfPower, halfPower), matrix);
        }
    }

    private long[][] matrixMultiply(long[][] a, long[][] b) {
        int rowsA = a.length;
        int colsA = a[0].length;
        int colsB = b[0].length;

        long[][] result = new long[rowsA][colsB];

        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsB; j++) {
                for (int k = 0; k < colsA; k++) {
                    result[i][j] += a[i][k] * b[k][j];
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        FiboMatrix fib = new FiboMatrix(7);
        fib.print();
    }
}

Algorithm 2: Dynamic Programming (Bottom-up)

public class FiboDynamic extends Fibo {

    public FiboDynamic() {
        super();
    }

    public FiboDynamic(int nth) {
        super(nth);
    }

    @Override
    protected void init() {
        super.name = "FiboDynamic extends Fibo";

        long[] dp = new long[super.size + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= super.size; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            super.setData(dp[i]);
        }
    }

    public static void main(String[] args) {
        FiboDynamic fib = new FiboDynamic(7);
        fib.print();
    }
}