Find the Fibonacci number using matrix exponentiation:

We start with the matrix F =  [[1,1], [1,0]] and compute the matrix exponentiation Math.pow(F, n)  as

    public static int[][] identity(int size) { 

           int[][] I = new int[size][size]; 

           for (int i = 0; i < size; i++) { 

               I[i][i] = 1; 

           } 

           return I; 

    } 

    public static int[][] matrixMultiplication(int[][] A, int[][] B, int modulo) { 

        int[][] C = new int[A.length][A.length]; 

        for (int i = 0; i < A.length; i++) { 

            for (int j = 0; j < A.length; j++) { 

                int value = 0; 

                for (int k = 0; k < A.length; k++) { 

                    value = (value + (A[i][k] % modulo) * (B[k][j] % modulo)) % modulo; 

                } 

                C[i][j] = value; 

            } 

        } 

        return C; 

    } 

    public static int[][] matrixExponentiation(int[][] A, int row, int modulo ) { 

        int [][] B = identity(A.length); 

        while (row > 0) { 

            if ((row & 1) == 1) { 

                B = matrixMultiplication(A, B, modulo); 

            } 

            A = matrixMultiplication(A, A, modulo); 

            row >>= 1; 

        } 

        return B; 

    } 

 

Int [][] result = matrixExponentiation(F, n, 1000007);

Nth Fibonacci number is result[0][0];

N = 4, result = [[5, 3], [3, 2]], N’th Fibonacci number = 5