Very Large Fibonacci in Java

Question

I am trying to rapidly calculate large Fibonacci numbers. Here is my code. It is prohibitively slow for numbers above 1 million, how can it be improved?

public static BigInteger fib(BigInteger n) {

        int k = n.intValue();
        BigInteger ans = null;

        if(k == 0) { 
            ans = new BigInteger("0");
        } else if(Math.abs(k) <= 2) {
            ans = new BigInteger("1");
        } else {
            BigInteger km1 = new BigInteger("1");
            BigInteger km2 = new BigInteger("1");

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = km1.add(km2);
                km2 = km1;
                km1 = ans;
            }
        }

       if(k<0 && k%2==0) { ans = ans.negate(); }
       return ans;
    }

Binet's worked well. Thanks guys!

You can profile it. Or you could try a log(n) algorithm. http://tech-queries.blogspot.com.au/2010/09/nth-fibbonacci-number-in-ologn.html?m=1 — xiaofeng.li, Apr 10 '15 at 01:05
I think this might be a good question over on [Codereview](http://codereview.stackexchange.com/) — James Hay, Apr 10 '15 at 01:05
Use a [closed-form formula](http://www.scibuff.com/2009/05/13/golden-nature-closed-form-formula-for-fibonacci-sequence/). Like [Binet's](http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html). — Elliott Frisch, Apr 10 '15 at 01:14
@ElliottFrisch if you want exact results, a closed form formula is actually really slow for large `n`, as the only way to calculate it precisely is to calculate large binomial coefficients. — k_g, Apr 10 '15 at 01:51
@ElliottFrisch The OP's solution (at least the one I see here) is not recursive, it uses the last two values and keeps adding. If you factor non-constant addition, it has a complexity of `n^2` (`F_n ~ phi^n` so addition is `~ log(F_n) ~ n`). A closed form solution is probably better, but probably not as good as an `n*log (n)` solution like the one given by @infgeoax (I say `n*log (n)` again because addition is not constant time) — k_g, Apr 10 '15 at 01:59
You should use `BigInteger.ZERO, ONE, TWO` where possible, and `BigInteger.valueOf()` rather than `new BigInteger(...)`. But if you really want to do this fast you should use a better algorithm. — user207421, Apr 10 '15 at 02:40

score 3 · Accepted Answer · edited May 23 '17 at 10:31

3

One way is to calculate the (N-1)th power of the 2x2 matrix:

A = ((1, 1), (1, 0))

Then we have

Fib(n) = A^(n-1)[0][0], for n >= 1

And the power of matrix A can be calculated efficiently using Exponentiation by squaring

edited May 23 '17 at 10:31

Community

1
1

answered Apr 10 '15 at 04:11

xiaofeng.li

8,237
2
23
30

Nice formula, where does it come from? I haven't find it as I needed it and had to derive my own from Binet (which itself was unusable due to round-off error) and it was a pain. – maaartinus Apr 10 '15 at 05:01

score 0 · Answer 2 · edited May 22 '22 at 14:06

static void multiply(BigInteger m[][], BigInteger n[][]) {
    BigInteger a = (m[0][0].multiply(n[0][0])).add(m[0][1].multiply(n[1][0]));
    BigInteger b = (m[0][0].multiply(n[0][1])).add(m[0][1].multiply(n[1][1]));
    BigInteger c = (m[1][0].multiply(n[0][0])).add(m[1][1].multiply(n[0][1]));
    BigInteger d = (m[1][0].multiply(n[0][1])).add(m[1][1].multiply(n[1][1]));
    m[0][0] = a;
    m[0][1] = b;
    m[1][0] = c;
    m[1][1] = d;
}

static void fib(int x) {
    BigInteger m[][] = new BigInteger[2][2];
    m[0][0] = new BigInteger("1");
    m[0][1] = new BigInteger("1"); //f1
    m[1][0] = new BigInteger("1");
    m[1][1] = new BigInteger("0");

    BigInteger n[][] = new BigInteger[2][2];
    n[0][0] = new BigInteger("1");
    n[0][1] = new BigInteger("1"); //f1
    n[1][0] = new BigInteger("1");
    n[1][1] = new BigInteger("0");

    int i = x;
    ArrayList <Integer> a = new ArrayList<>();
    while (i != 1) {
        if (i%2 == 0) {
            a.add(0);
            i = i / 2;
        } else {
            a.add(1);
            i = i / 2;
        }
    }
    for (int j = a.size() - 1; j >= 0 ; j--) {
        if (a.get(j) == 0) {
            multiply(m, m);
        } else {
            multiply(m, m);
            multiply(m, n);
        }
    }
    System.out.println(m[1][0]);
}

Very Large Fibonacci in Java

2 Answers2

Linked