斐波那契數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

您需要一個大整數庫。你可以自己滾動（不是那麼複雜），也可以使用在網上漂浮的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秒。

Answer 2

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