斐波那契数列 1 kk 迭代

Question

我有一个计算斐波那契数列的函数

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

但是 n > 10000 我得到 Infiniti 语句。

如何在 JavaScript 中计算超过 (n > 1kk) 的斐波那契数列？

Answer 1

JavaScript中的最大整数是 2^53。斐波那契数列的第 1000 个成员在 ~4.35*10^208 大大超过了这个限制，所以你需要使用一个大数字库来计算这么高的数字。下面是使用 big.js 轻松解决此问题的示例。

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

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
alert(fib(1000)); // 4.346655768...e+208

Answer 2

你需要一个大整数库。要么自己滚一个（没那么复杂），要么使用网上流传的 js-bigint 库（让我在这里加入一个无耻的 self-plug）。

但是对于 lareg Fibonacci 数，您应该使用不同的算法并通过矩阵求幂来完成。如果你使用我的 bigint-library，你可以使用下面的脚本

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();

到字符串的转换仍然没有优化，这里需要大部分的运行时间。在这台中等功率的机器上计算（但不是打印！）F(1,000,000) 需要大约 24 秒。

斐波那契数列 1 kk 迭代

Fibonacci numbers 1 kk iteration

javascript

numbers

fibonacci

infinity

bignum