Fibonacci numbers 1 kk iteration

Question

I've a function to calculate Fibonacci numbers

function fib(n) {
  var a = 1,
    b = 1;
  for (var i = 3; i <= n; i++) {
    var c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

But with n > 10000 I get Infiniti statement.

How can I calculate Fibonacci numbers over (n > 1kk) in JavaScript?

Answer 1

You need a big-integer library. Either roll one yourself (it's not that complicated) or use on of the js-bigint libraries floating around on the net (Let me include a shameless self-plug here).

But for lareg Fibonacci numbers you should use a different algorithm and do it by matrix exponetiation. If you use my bigint-library you can use the following script

function smallfibonacci(n) {
    var i = 1,
        j = 0,
        k, l;
    for (k = 1; k <= n; k++) {
        l = i + j;
        i = j;
        j = l;
    }
    return j;
}

function fibonacci(n) {
    var i = n - 1,
        r;
    var a, b, c, d, t, t1, t2, t3;
    var e;

    if (n <= 76) {
        return smallfibonacci(n).toBigint();
    }

    a = new Bigint(1);
    b = new Bigint(0);
    c = new Bigint(0);
    d = new Bigint(1);

    while (i > 0) {
        if (i & 0x1) {
            //t = d*(a + b) + c*b;
            t1 = c.mul(b);
            t2 = a.add(b);
            t3 = d.mul(t2);
            t = t3.add(t1);

            //a = d*b + c*a;
            t1 = d.mul(b);
            t2 = c.mul(a);
            a = t1.add(t2);
            //b = t;
            b = t.copy();
        }
        //t = d*(2*c + d);
        t1 = c.lShift(1);
        t2 = t1.add(d);
        t = d.mul(t2);

        //c = c*c + d*d;
        t1 = c.sqr();
        t2 = d.sqr();
        c = t1.add(t2);
        //d = t;
        d = t.copy();
        i >>>= 1;
    }
    r = a.add(b);
    return r;
}

fibonacci(10000).toString();

The conversion to string is still not optimized and needs most of the runtime here. Computing (but not printing!) F(1,000,000) needs about 24 seconds on this medium powered machine.