Nᵗʰ Fibonacci Number - Matrices Multiplication

We can find the nᵗʰ Fibonacci number by multiplying matrices. Here is a good explanation of it - Nth Fibonacci Number - multiplying matrices. Let matrix A = [ [ 1 1 ] [ 1 0 ] ]. In order to find the nᵗʰ Fibonacci number all you need is finding the nᵗʰ power of the matrix A.

public class FibonacciMatrixMultiplication {

    static int fibonacciNumber(int n) {
        int A[][] = { { 1, 1 }, { 1, 0 } };
        if (n == 0)
            return 0;
        power(A, n - 1);
        return A[0][0];
    }

    /*
     * Helper function that multiplies 2 matrices X and Y of size 2x2, and puts
     * the multiplication result back in X[][]
     */
    static void multiply(int X[][], int Y[][]) {
        int x = X[0][0] * Y[0][0] + X[0][1] * Y[1][0];
        int y = X[0][0] * Y[0][1] + X[0][1] * Y[1][1];
        int z = X[1][0] * Y[0][0] + X[1][1] * Y[1][0];
        int w = X[1][0] * Y[0][1] + X[1][1] * Y[1][1];
        X[0][0] = x;
        X[0][1] = y;
        X[1][0] = z;
        X[1][1] = w;
    }

    /*
     * Helper function that calculates X[][] raise to the power n and puts the
     * result in X[][]
     */
    static void power(int X[][], int n) {
        int i;
        int A[][] = { { 1, 1 }, { 1, 0 } };
        // n - 1 times multiply the matrix to {{1,0},{0,1}}
        for (i = 2; i <= n; i++) {
            multiply(X, A);
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number no." + n + " is "
                         + fibonacciNumber(n));
    }

}

For more Fibonacci number problems you can visit "Fibonacci numbers - 4 solutions"