Computing even huger Fibonacci numbers in Java - follow-up
Theory

As described in a related Python answer, it's possible to refactor the recursion into a for loop and to use matrix arithmetics without using matrices.

Code

import java.math.BigInteger;

public class LargeFibonacciNumbers
{

    public static BigInteger fibonacci(int n) {
        BigInteger f_n = BigInteger.ZERO;
        BigInteger f_n_plus_1 = BigInteger.ONE;
        BigInteger two = BigInteger.valueOf(2);
        BigInteger f_n_plus_1_squared, f_2n, f_n_squared, f_2n_plus_1;
        for (int i = Integer.SIZE - Integer.numberOfLeadingZeros(n); i &gt;= 0; i--) {
            f_n_squared = f_n.multiply(f_n);
            f_n_plus_1_squared = f_n_plus_1.multiply(f_n_plus_1);
            f_2n = f_n.multiply(f_n_plus_1).multiply(two).subtract(f_n_squared);
            f_2n_plus_1 = f_n_squared.add(f_n_plus_1_squared);
            if ((n &gt;&gt; i &amp; 1) == 1) {
                f_n = f_2n_plus_1;
                f_n_plus_1 = f_2n.add(f_2n_plus_1);
            } else {
                f_n = f_2n;
                f_n_plus_1 = f_2n_plus_1;
            }
        }
        return f_n;
    }

    public static void main(String[] args) {
        int n = 10000000;
        long start = System.nanoTime();
        System.out.println(fibonacci(n).bitLength());
        long finish = System.nanoTime();
        System.out.println((finish - start) / 1000000 + " ms");
    }
}


Comments

bitLength() isn't defined for ints, so this method has been used instead.

Performance

This code calculates the 10-millionth Fibonacci number in less than 1.5s on my computer. In comparison, the matrix version needs almost 4s.

Note that the test code only displays the bit length of the result, not the result itself. fibonacci(1E7) has more than 2 million digits, and it takes much longer to display it in the console than to calculate it.