如何找到给定斐波那契数的索引

Question

我尝试使用下面的公式

$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2} \right)\bigg\rfloor$

在一个编程问题中找到斐波那契数（ $text$ ）的索引，所有较小的测试用例都通过了，但一些 F 接近 10^18 的情况失败了。我做了一些 dry-run，发现如果 F = 99194853094755497（第 82 个斐波那契数），根据上面的公式，n 的值为 81。我在 Python 和 C++ 中编写了它，可以找到 here and here分别。我想知道该公式是否适用于 F 的每个值或有一些限制？

注意：在做了更多测试后，我发现代码给出了正确的答案，直到第 52 个斐波那契数。

更新：问题有 t 个测试用例，这就是我使用 for 循环的原因。给定的数字 F 不一定是斐波那契数。对于ex-如果F = 6，那么它位于两个斐波那契数5和8之间。现在斐波那契数列中'5'的索引是4所以答案是4.

Answer 1

我认为您的公式导致堆栈溢出，因为数字太大而无法保存在 int 中。

Answer 2

公式运行良好：

import math
n = 99194853094755497
print math.log(n * math.sqrt(5) + 0.5) / math.log(1.61803398875) - 1

输出：

82.0

对您的代码的评论：

如果浮点结果非常接近 82.0，则使用 int(...) 舍入为整数可能会导致问题。数值问题可能会导致它稍微大一些，即使从数学上讲它会更小。

Answer 3

F = 99194853094755497 是 84 斐波那契数，因此它的索引是 83。使用下面的脚本来获取正确的索引（整数而不是浮点数）。

eps = 10**-10
phi = (1+math.sqrt(5))/2  # golden search ratio
fibonacci_index = int(round(math.log(n * math.sqrt(5)+eps)/math.log(phi)))

附加信息，代码有关实施的更多详细文档，请参阅此 https://github.com/gvavvari/Python/tree/master/Fibonacci_index

如何找到给定斐波那契数的索引

How to find index of a given Fibonacci number

c++

python

math

fibonacci