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;
}

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

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

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

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

你能给我一篇文章或线索吗？

感谢和问候。

Answer 1

如果您只是将以前的值添加到当前值，然后使用旧的当前值作为以前的值，您将获得显着的性能改进。

function fib(n) {
  var current = 1;
  var previous = 0;
  while (--n) {
    var temp = current;
    current += previous;
    previous = temp;
  }
  return current;
}

console.log(fib(1)); // 1
console.log(fib(2)); // 1
console.log(fib(3)); // 2
console.log(fib(4)); // 3
console.log(fib(5)); // 5

您也可以在父作用域中使用数组来存储以前的值，以避免重做相同的计算。

var fibMap = [1, 1];

function fib(n) {
  var current = fibMap[fibMap.length - 1];
  var previous = fibMap[fibMap.length - 2];
  while (fibMap.length < n) {
    var temp = current;
    current += previous;
    previous = temp;
    fibMap.push(current);
  }
  return fibMap[n - 1];
}

console.log(fib(1)); // 1
console.log(fib(2)); // 1
console.log(fib(3)); // 2
console.log(fib(4)); // 3
console.log(fib(5)); // 5

Benchmark for getting the 1000th number 3 times

Answer 2

首先，你可以参考答案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 个斐波那契数和 return。下次如果您调用 fib(n) 它将再次计算它并 return 结果。如果我们将这个值存储在某处并在下次需要时检索它会怎么样？

这也有助于计算大于第 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.

Javascript 中大数的斐波那契数列

Fibonacci for large numbers in Javascript

javascript

fibonacci