Computing even huger Fibonacci numbers in Java - follow-up See the previous and initial iteration.

I have incorporated almost all the suggestions by Peter Taylor:


The actual method returns a BigInteger instead of String.
The actual method can deal with Fibonacci numbers with negative indices, so there is no any need to throw IllegalArgumentException.
The only base case that is checked is \$n = 0\$.
fibonacciMatrix renamed to pow.
main is now more sensible.


(The matrix power method is still recursive.)

See what I have:

import java.math.BigInteger;

public class LargeFibonacciNumbers {

    public static BigInteger fibonacci(int n) {
        if (n == 0) {
            return BigInteger.ZERO;
        }

        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;

        BigInteger tmp = pow(matrix, Math.abs(n))[0][1];

        if (n &gt; 0 || ((n &amp; 1) == 1)) {
            return tmp;
        } else {
            return tmp.negate();
        }
    }

    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[][] pow(BigInteger[][] matrix, int n) {
        if (n == 1) {
            // End the recursion.
            return matrix;
        }

        BigInteger[][] tmp = pow(matrix, n &gt;&gt; 1);
        tmp = multiply(tmp, tmp);

        if ((n &amp; 1) == 1) {
            tmp = multiply(matrix, tmp);
        }

        return tmp;
    }

    public static void main(String[] args) {
        if (args.length &gt; 0) {
            int n;

            try {
                n = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {
                System.err.println("Could not parse \"" + args[0] + 
                                   "\" as an integer.");
                return;
            }

            System.out.println(fibonacci(n));
        } else {
            System.out.println("Usage: java -jar File.jar N");
            System.out.println("Where N is the index of the Fibonacci number " +
                               "to compute.");
        }
    }
}


So, what do you think?
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.