Calculate fibonacci in O(log n) This program calculates the \$n\$th fibonacci number, in \$O(\log n)\$ time. I'm looking for code review, optimizations, and best practices.

public final class Fibo {

    private Fibo() { }

    public static int getNthfibo(int n) {
        if (n &lt; 0) {
            throw new IllegalArgumentException("The fibo value cannot be negative");
        }

        if (n &lt;= 1) return n;

        int[][] result = {{1, 0}, {0, 1}}; // identity matrix.
        int[][] fiboM = {{1, 1}, {1, 0}};

        while (n &gt; 0) {
            if (n%2 == 1) {
                multMatrix(result, fiboM);
            }
            n = n / 2;
            multMatrix(fiboM, fiboM);
        }

        return result[1][0];
    }

    private static void multMatrix(int[][] m, int [][] n) {
        int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];
        int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];
        int c = m[1][0] * n[0][0] +  m[1][1] * n[0][1];
        int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];

        m[0][0] = a;
        m[0][1] = b;
        m[1][0] = c;
        m[1][1] = d;
    }


    public static void main(String[] args) {
        for (int i = 0; i &lt; 10; i++) {
            System.out.println(getNthfibo(i));
        }
    }
}
Your code seems to be working properly so there is not much to say on this.

The only changes I would perform would be to make things easier to understand through different little steps.


Multiplication could return a result

At the moment, your multiplication procedure stores the result in the first argument. First issue is that it cannot be generalised to product of non-square matrices. The second issue is that it can make things a bit hard to understand when looking at the code using your function (getNthfibo in your case). It is a fairly easy change to perform :

private static int[][] multMatrix(int[][] m, int [][] n) {
    int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];
    int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];
    int c = m[1][0] * n[0][0] +  m[1][1] * n[0][1];
    int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];
    int[][] ret = {
        {a, b},
        {c, d}};
    return ret;
}


and in your main function:

result = multMatrix(result, fiboM);` and `fiboM = multMatrix(fiboM, fiboM);

The signature of the multMatrix method lets us think that is works for any matrices.

Actually, it only works for 2*2 matrices. This should be documented and checked at runtime (because it doesn't seem to be possible to do so at compilation time).
Making Mathematics a bit more obvious

Values can be reformatted in such a way that the mathematics behind are easier to understand. Also, a little bit of comment can help.

    int[][] result = {
        {1, 0},
        {0, 1}};

    /*         n
     * [ 1 1 ]     [ F(n+1) F(n)   ]
     * [ 1 0 ]   = [ F(n)   F(n-1) ]
     */
    int[][] fiboM = {
        {1, 1},
        {1, 0}};