Is there a better way (performance) calculate fibonacci than this one?

Question

I made this code.. And I need to get the best of it.. I really need the best performance of calculating fibonacci numbers.. please help be..

I've read some code of this type of calculation and I think I got the best of them..

Avaliate this for me.. plz..

ps: And I really need the BigInteger.. I'll calculate Fibonacci of enormous numbers

ps2: I have calculated some big numbers with this algorithm and I got a great response time.. but I need to know whether it could be better

ps3: to run this code you'll need to use this VM argument -Xss16384k (StackSize)

public class Fibonacci {

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) };

    public static BigInteger fibonacci(long v) {

        BigInteger fib = BigInteger.valueOf(0);

        if (v == 1) {

            fib = BigInteger.valueOf(1);

        } else if (v == 0) {

            fib = BigInteger.valueOf(0);

        } else {

            BigInteger v1 = fibonacci(v - 1);
            BigInteger v2 = fibTmp[(int) (v - 2)];

            fib = v1.add(v2);
        }

        synchronized (fibTmp) {

            if (fibTmp.length - 1 < v)
                fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10));

            fibTmp[(int) v] = fib;
        }

        return fib;
    }
}

Answer 1

Yes, there's a better way. This is a log(n) tested and very efficient way for calculating a value of Fibonacci with arbitrary precision, given a positive integer as input. The algorithm was adapted from a solution to SICP's exercise 1.19:

public static BigInteger fibonacci(int n) {

    int count = n;
    BigInteger tmpA, tmpP;
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ZERO;
    BigInteger p = BigInteger.ZERO;
    BigInteger q = BigInteger.ONE;
    BigInteger two = new BigInteger("2");

    while (count != 0) {

        if ((count & 1) == 0) {
            tmpP = p.multiply(p).add(q.multiply(q));
            q = two.multiply(p.multiply(q)).add(q.multiply(q));
            p = tmpP;
            count >>= 1;
        }

        else {
            tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p)));
            b = b.multiply(p).add(a.multiply(q));
            a = tmpA;
            count--;
        }

    }

    return b;  

}

In the linked chapter of the book there's an explanation of how it works (scroll down to exercise 1.19), and it's stated that:

This is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps ... This exercise was suggested by Joe Stoy, based on an example in Kaldewaij, Anne. 1990. Programming: The Derivation of Algorithms.

Of course, if the same values need to be calculated over and over again, further performance gains can be achieved by memoizing results that have been already calculated, for instance using a map for storing previous values.