# 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 < 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])

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

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

ret[1][1] = matrix1[1][0].multiply(matrix2[0][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?

• Have you ever taken a look at the Binet's formula? It might be useful to accelerate even more your computing. Oct 27, 2015 at 18:56
• I will try it, but later. Oct 27, 2015 at 18:59

    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!

• If $n < 0$, $F_n = - F_{-n}$? Oct 31, 2015 at 14:44
• No, $$F_n = (-1)^{n+1} F_{-n}$$. Oct 31, 2015 at 14:45

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.

• Why it should be iterative? Stack overflow is not an issue for 'n' like 1e6 will imply no more than 20 stack frames. Oct 27, 2015 at 18:50
• @coderodde It is just faster (and IMHO cleaner).
– vnp
Oct 27, 2015 at 18:53
• The power algorithm can be generalized to any square matrix, yes, yet I am pretty sure that there is no way to make the matrix entries generic due to the fact that generics in Java are not as versatile as C++ metaprogramming facilities. Oct 27, 2015 at 18:57
• Actually, I don't need generics: the attempt is to compute large Fibonaccies, and by using, say longs, I won't be able to compute much of them. Oct 27, 2015 at 19:05
• Another point on your generics point: I'm not a language theorist, but it would seem that implementing what you have in mind would require adding operator overloading to Java or introducing some interface for mathematical fields (which is absent as of now). Oct 27, 2015 at 19:09