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;
    }
}

This looks like java. For best performances, the language might be important. Can you add a language tag ? — Denys Séguret, Feb 26 '13 at 15:57
no.. forget about the language.. is algorithm performance.. language in this case doesnt matter! =) — thiagoh, Feb 26 '13 at 15:58
As you like but not all languages are equal related to deep recursivity... — Denys Séguret, Feb 26 '13 at 15:58
a better algorithm would be faster no matter the language or machine on which it is implemented(when you get a big enough number, that is). Oh, the fun and joys of asymptotic analysis. — Benjamin Trent, Feb 26 '13 at 16:08
There is an O(log n) algo to find fibonacci number. Its called matrix exponentiation method. You can try that. http://fusharblog.com/solving-linear-recurrence-for-programming-contest/ — dejavu, Feb 26 '13 at 16:09
If you really need the best complexity, you can do it in constant time, using the closed formula. See http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression. — Eyal Schneider, Feb 26 '13 at 16:31
@AndroidDecoded That's `O(log n)` steps. Since `F(n)` has `theta(n)` digits, no algorithm to compute it can be better than `O(n)` bit operations. — Daniel Fischer, Feb 26 '13 at 16:43

Óscar López · Answer 1 · 2013-02-26T16:53:30.677

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.

For even better performance you could replace `BigInteger` with something like [jscience LargeInteger](http://jscience.org) (java.math.BigInteger.multiply has cuadratic complexity) — Joni, Feb 26 '13 at 17:15

Denys Séguret · Accepted Answer · 2013-02-26T16:42:56.527

Your implementation doesn't work for any decent number because it makes the stack overflow.

I don't see any reason to use recursivity here. Recursivity is pretty but generally heavier (it's language dependent). Here's a working implementation with a simple for loop :

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE};
private static int maxCached = 1;
public static BigInteger fibonacci(int v) {
    if (fibTmp.length<=v) {
        fibTmp = Arrays.copyOf(fibTmp, v*5/4);
    }
    for (; maxCached<v;) {
        maxCached++;
        BigInteger v1 = fibTmp[maxCached - 1];
        BigInteger v2 = fibTmp[maxCached - 2];
        fibTmp[maxCached] = v1.add(v2);
    }
    return fibTmp[v];
}

That's a direct implementation without looking for an efficient Fibonacci algorithm in the literature. You'd better look for them.

Note also that this cache based implementation is memory costly and makes only sense if you call the function multiple times.

score 0 · Answer 3 · answered Feb 26 '13 at 16:12

First of all, you are using recursion, which is not efficient in terms of both time and space complexity. You should use the iterative approach.

Then if extra memory or space is not deal breaker and if the performance is really critical, you might want to precompute all the numbers that you'd like to compute later and store them in an array or on your disk if it's too much for your memory. Later you can get the value in constant time.

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

3 Answers3

Linked