Geek asks and answers

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

I made this code .. And I need to get my best. I really need a better fibonacci number calculation performance .. please help ...

I read some code for this type of computation, and I think I got the best of them.

Rate it for me .. plz ..

ps: And I really need BigInteger. I calculated Fibonacci huge numbers

ps2: I figured out some big numbers with this algorithm and I got great response time ... but I need to know if it could be better

ps3: to run this code you will 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;
    }
}
+5
source share
3 answers

- , .

. , ( ). for:

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

. .

, , .

+4

, . log(n) , . SICP 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;  

}

, ( 1.19), , :

... , Kaldewaij, Anne. 1990. : .

, , memoizing , , , .

+7

, , . .

, , , , , , . .

0

More articles:


All Articles