寻找最接近的斐波那契数列

我正在尝试解决一个更大的问题，并且我认为该程序的重​​要部分花费在低效的计算上。

我需要计算给定数字 N 的区间 [P, Q]，其中 P 是 = 到 N 的最小斐波那契数。

目前，我正在使用地图来记录斐波那契数的值。 查询通常涉及搜索最多 N 的所有斐波那契数，并且它的时间效率不是很高，因为它涉及大量的比较。

这种类型的查询在我的程序中会经常出现，我对改进查找的方法很感兴趣，最好是具有亚线性复杂度。

斐波那契数列由比奈公式给出

F(n) = ( phi^n - (1-phi)^n ) / \sqrt{5}

where phi是黄金比例，

phi = (1 + \sqrt{5}) / 2. 

这可以直接实现（Python 示例）：

<<fibonacci_binet.py>>=
phi = (1 + 5**0.5) / 2

def fib(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

然而，由于浮点舍入误差，这只会给出正确的结果n < 70.

比奈公式可以通过忽略来反转(1-phi)^n项，对于大范围消失n。因此，我们可以定义逆斐波那契函数，当给定F(n)，返回n（忽略这一点F(1) = F(2)):

<<fibonacci_binet.py>>=
from math import log

def fibinv(f):
    if f < 2:
        return f
    return int(round(log(f * 5**0.5) / log(phi)))

这里使用舍入对我们有利：它消除了我们对比奈公式的修改所引入的误差。事实上，当给出任何可以作为精确整数存储在计算机内存中的斐波那契数时，该函数将返回正确的答案。另一方面，它并不验证给定的数字实际上是斐波那契数；输入一个大的斐波那契数或任何接近它的数都会得到相同的结果。因此，您可以使用这个想法来找到最接近给定数字的斐波那契数。

这个想法是应用逆斐波那契图来找到N and M，两边最接近的两个斐波那契数，然后使用直接斐波那契图来计算P = F(N) and Q = F(M)。这涉及更多的计算，但更少的搜索。