3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Have you ever taken a look at the Binet's formula? It might be useful to accelerate even more your computing. \$\endgroup\$ – IEatBagels Oct 27 '15 at 18:56
  • 1
    \$\begingroup\$ I will try it, but later. \$\endgroup\$ – coderodde Oct 27 '15 at 18:59
2
\$\begingroup\$
    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!

\$\endgroup\$
  • \$\begingroup\$ If \$n < 0\$, \$F_n = - F_{-n}\$? \$\endgroup\$ – coderodde Oct 31 '15 at 14:44
  • \$\begingroup\$ No, $$F_n = (-1)^{n+1} F_{-n}$$. \$\endgroup\$ – Peter Taylor Oct 31 '15 at 14:45
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why it should be iterative? Stack overflow is not an issue for 'n' like 1e6 will imply no more than 20 stack frames. \$\endgroup\$ – coderodde Oct 27 '15 at 18:50
  • \$\begingroup\$ @coderodde It is just faster (and IMHO cleaner). \$\endgroup\$ – vnp Oct 27 '15 at 18:53
  • \$\begingroup\$ 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. \$\endgroup\$ – coderodde Oct 27 '15 at 18:57
  • \$\begingroup\$ 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. \$\endgroup\$ – coderodde Oct 27 '15 at 19:05
  • \$\begingroup\$ 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). \$\endgroup\$ – coderodde Oct 27 '15 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.