斐波那契数1 KK迭代

问题描述：

我有一个函数来计算斐波那契数斐波那契数1 KK迭代

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）？

与一个大号码库它应该是可能的。 –

是的，[这]（http://stackoverflow.com/questions/2622144/is-there-a-decimal-math-library-for-javascript）问题的答案有一些，如果你谷歌的东西像“JavaScript无限精度算术“，其中有一堆。 – blm

答

您需要一个大整数库。你可以自己滚动（不是那么复杂），也可以使用在网上漂浮的js-bigint库（让我在这里包含一个无耻的self-plug）。

但是为了排列斐波纳契数字，你应该使用不同的算法，并通过矩阵指数来完成。如果你用我的BIGINT库，你可以使用下面的脚本

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秒。

答

JavaScript中的最大整数是2^53。 Fibonacci序列的第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

斐波那契数1 KK迭代

相关推荐