Computing even huger Fibonacci numbers in Java

Question

See the next iteration.

I have that method for computing Fibonacci numbers \$F_n\$ (\$n = 0, 1, 2, \dots)\$, that relies on computing

$$ A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n. $$

The solution is then read from \$A_{1,2}\$. Now I can easily compute, for instance, \$F_{100000}\$.

However, in this code snippet, I need not just large integer additions, but multiplications as well, and looking at the source code of multiplication of two BigIntegers, it becomes evident that the algorithms are more smart and efficient than I could ever do.

What comes to the complexity of this approach, we need only \$\Theta(\log n)\$ matrix multiplications. Assuming that multiplying two (largest in the computation) BigIntegers takes time \$\mathcal{O}(f(n))\$, the complexity of the entire algorithm is \$\mathcal{O}(f(n) \log n)\$.

import java.math.BigInteger;

public class LargeFibonacciNumbers {

    public static String fibonacci(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                    "The (" + n + ")th Fibonacci number is not defined.");
        }

        switch (n) {
            case 0:
                return "0";

            case 1:
                return "1";
        }

        BigInteger[][] matrix = new BigInteger[2][2];

        matrix[0][0] = BigInteger.ONE;
        matrix[0][1] = BigInteger.ONE;
        matrix[1][0] = BigInteger.ONE;
        matrix[1][1] = BigInteger.ZERO;

        return fibonacciMatrix(matrix, n)[0][1].toString();
    }

    private static BigInteger[][] multiply(BigInteger[][] matrix1, 
                                           BigInteger[][] matrix2) {
        BigInteger[][] ret = new BigInteger[2][2];

        ret[0][0] = matrix1[0][0].multiply(matrix2[0][0])
               .add(matrix1[0][1].multiply(matrix2[1][0]));

        ret[0][1] = matrix1[0][0].multiply(matrix2[0][1])
               .add(matrix1[0][1].multiply(matrix2[1][1]));

        ret[1][0] = matrix1[1][0].multiply(matrix2[0][0])
               .add(matrix1[1][1].multiply(matrix2[1][0]));

        ret[1][1] = matrix1[1][0].multiply(matrix2[0][1])
               .add(matrix1[1][1].multiply(matrix2[1][1]));

        return ret;
    }

    private static BigInteger[][] 
        fibonacciMatrix(BigInteger[][] matrix, int n) {
        if (n == 1) {
            // End the recursion.
            return matrix;
        }

        if ((n & 1) == 1) {
            // 'n' is odd.
            return multiply(matrix, fibonacciMatrix(matrix, n - 1));
        } 

        // 'n' is even.
        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        return multiply(tmp, tmp);
    }

    public static void main(String[] args) {
        int n = -1;

        if (args.length > 0) {
            try {
                n = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {

            }
        }

        System.out.println(fibonacci(n));
    }
}

So, what do you think?

Answer 1

    public static String fibonacci(int n) {

Why? It makes far more sense for this method to return a BigInteger.

---

        if (n < 0) {
            throw new IllegalArgumentException(
                    "The (" + n + ")th Fibonacci number is not defined.");
        }

Negative-index Fibonacci numbers are perfectly well defined, so this error message is misleading. You could change the error message to something like "Negative indexes are not supported", but you might as well change the code to support them. It's just a case of negating n and using initial matrix [[0 1][1 -1]].

---

        switch (n) {
            case 0:
                return "0";

            case 1:
                return "1";
        }

I can understand having a special case for 0 because it saves you a special case in the matrix power code, but why the special case for 1?

---

    private static BigInteger[][] 
        fibonacciMatrix(BigInteger[][] matrix, int n) {

The name of this method makes no sense to me. Why isn't it called pow or matrixPower?

---

        if ((n & 1) == 1) {
            // 'n' is odd.
            return multiply(matrix, fibonacciMatrix(matrix, n - 1));
        } 

        // 'n' is even.
        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        return multiply(tmp, tmp);

Your argument in favour of recursion in the comments on an earlier answer is out by a factor of two, because you're potentially making twice as many calls as there are bits in n. Even if you don't want to do things iteratively, it makes sense to rewrite this as

        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        tmp = multiply(tmp, tmp);
        if ((n & 1) == 1) {
            tmp = multiply(matrix, tmp);
        }
        return tmp;

---

    public static void main(String[] args) {
        int n = -1;

        if (args.length > 0) {
            try {
                n = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {

            }
        }

        System.out.println(fibonacci(n));
    }

If I supply no command-line arguments, or if I supply an invalid one, the output is The (-1)th Fibonacci number is not defined. That doesn't help me at all with figuring out my mistake. I'd rather have the NumberFormatException!

Answer 2

The fibonacciMatrix implements a generic power algorithm. I am not very versed in Java - but if there is a way to express a generic (that is, parameterized by type, akin to C++ templates), consider implementing it in generic way.

That said, an algorithm may and should be iterative.