按索引获取斐波那契数 - PHP

Question

我有一个简单的 PHP 函数，它 returns 斐波那契数列索引并且有效：

function fibIndexCalculator($index)
{
    $numbers = [0, 1];
    for ($i = 0; $i < $index; $i++) {
        $lastNumbers = array_slice($numbers, count($numbers) - 2, 2);
        $numbers[] = $lastNumbers[0] + $lastNumbers[1];
    }
    return end($numbers);
}
var_dump(fibIndexCalculator(4));

但是如果我给函数一个像 200000 这样的索引，那么只有在 1 小时后我才能看到结果。

有什么方法可以改变快速获取大索引斐波那契数列的算法吗？

Answer 1

if I give the function an index like 200000, then only after 1 hour I can see the result.

如果这样做，您将看不到任何有用的结果。输出将是 INF。这是因为 PHP 使用的 64 位浮点数的最大值可以表示在 1.797E+308 附近。索引为1475的斐波那契数已经在1E+308左右...

但是到了浮点数的极限，可以直接用下面的公式：

function fibIndexCalculator($index) {
    $SQRT5 = sqrt(5);
    return round(((1 + $SQRT5) / 2)**$index / $SQRT5);
}

如果您想坚持迭代解决方案，请注意您如何累积一个数组，您永远不会再次使用该数组中的旧值——仅使用最后两个值。所以不要保留一个数组，而只保留两个变量：

function fibIndexCalculator2($index) {
    if ($index < 2) return $index;
    $b = 1;
    $c = 1;
    while ($index > 2) {
        $a = $b;
        $b = $c;
        $c = $a + $b;
        $index--;
    }
    return $c;
}

按索引获取斐波那契数 - PHP

Get Fibonacci number By Index - PHP

php

algorithm

fibonacci