Computing even huger Fibonacci numbers in Java

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 > 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?

public static String fibonacci(int n) {


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

if (n

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`!

StackExchange Code Review Q#108912, answer score: 2