javascript - Javascript 中大数的斐波那契数

Question

我有以下代码:

function fib(n) {

  let first=BigInt(0);
  let snd=BigInt(1);
  let currentNumber;
  let countMax=Math.abs(n)+1;
  let counter=2;
  if(n==0){

    return first;
  } 
  else if (n==1||n==-1){

    return snd;
  }
  while(counter<countMax)
  {
        currentNumber=first+snd;
        first=snd;
        snd=currentNumber;
        counter++;
  }
  if((n<0) && (n % 2 ==0))
  {
    return -currentNumber;
  }
  return currentNumber;
}

返回给定 (n) 的斐波那契数。

我的问题是我必须提高这段代码的性能。我尝试使用不同的斐波那契公式(指数公式)，但我失去了很多精度，因为 phi 数字有无限小数，所以我必须 chop ，对于大数字我失去了很多精度。

当我执行 fib(200000) 时，我得到了一个巨大的数字，但代码花费了超过 12000 毫秒。

另一方面，我尝试使用递归，但性能下降。

您能给我提供一篇文章或线索吗？

感谢和问候。

Answer 1

首先可以引用答案here上面说的是

Fib(-n) = -Fib(n)

这是递归实现，正如您提到的那样效率不高

function fib(n) {
    // This is to handle positive and negative numbers
    var sign = n >= 0 ? 1 : -1;
    n = Math.abs(n);

    // Now the usual Fibonacci function
    if(n < 2)
        return sign*n;
    return sign*(fib(n-1) + fib(n-2));
}

这非常简单，我不做任何解释，因为如果您了解斐波那契数列，您就知道上面的代码的作用。正如您已经知道的，这对于非常大的数字来说并不好，因为它会一次又一次地递归计算相同的事情。但我们稍后会在我们的方法中使用它。

现在正在寻找更好的方法。请参阅下面的代码，它与您的代码类似，只是稍微简洁一点。

function fib(n) {
    if(n == 0)
        return 0;
    var a = 1;
    var b = 1;
    while(n > 2) {
        b = a + b;
        a = b - a;
    }
    // If n is negative then return negative of fib(n)
    return n < 0 ? -1*b : b;
}

当您只想调用此函数几次时，最好使用此代码。但如果你想频繁调用它，那么你最终会多次计算同一件事。在这里您应该跟踪已经计算出的值。

例如，如果您调用fib(n)它将计算 n th 斐波那契数并返回它。下次如果您调用fib(n)它会再次计算并返回结果。 如果我们将此值存储在某处并下次在需要时检索它会怎样？

这也有助于计算大于 n 的斐波那契数第一个斐波那契数列。 如何？

假设我们必须计算 fib(n+1)，那么根据定义 fib(n+1) = fib(n) + fib(n-1) 。因为，我们已经有了fib(n)计算并存储在某个地方，我们可以使用该存储的值。另外，如果我们有 fib(n)计算并存储，我们已经有 fib(n-1)计算并存储。再读一遍。

我们可以通过使用 JavaScript 对象和上面使用的相同递归函数(是的，递归函数!)来做到这一点。请参阅下面的代码。

// This object will store already calculated values
// This should be in the global scope or atleast the parent scope
var memo = {};

// We know fib(0) = 0, fib(1) = 1, so store it
memo[0] = 0;
memo[1] = 1;

function fib(n) {
    var sign = n >= 0 ? 1 : -1;
    n = Math.abs(n);

    // If we already calculated the value, just use the same
    if(memo[n] !== undefined)
        return sign*memo[n];

    // Else we will calculate it and store it and also return it
    return sign*(memo[n] = fib(n-1) + fib(n-2));
}

// This will calculate fib(2), fib(3), fib(4) and fib(5). 
// Why it does not calculate fib(0) and fib(1) ? 
// Because it's already calculated, goto line 1 of this code snippet
console.log(fib(5)); // 5

// This will not calculate anything 
// Because fib(-5) is -fib(5) and we already calculated fib(5)
console.log(fib(-5)); // -5

// This will also not calculate anything
// Because we already calculated fib(4) while calculating fib(5)
console.log(fib(4)); // 3

// This will calculate only fib(6) and fib(7)
console.log(fib(7)); // 13

尝试一些测试用例。很容易理解为什么这样更快。

现在您知道可以存储已经计算的值，您可以修改解决方案以使用此方法，而无需使用递归，因为对于大数，递归方法将抛出 Uncaught RangeError 。我把这个留给你，因为它值得你自己尝试!

该解决方案使用了称为动态编程的编程概念。您可以引用here .