寻找最接近的斐波那契数 [英] Finding the closest fibonacci numbers

问题描述

我正在尝试解决更大的问题，我认为程序的重要部分花在了低效的计算上.

I am trying to solve a bigger problem, and I think that an important part of the program is spent on inefficient computations.

对于给定的数字N，我需要计算间隔[P，Q]，其中P是对N≤的最大斐波那契数，而Q是对N≥的最小斐波那契数.

I need to compute for a given number N, the interval [P, Q], where P is the biggest fibonacci number that is <= to N, and Q is the smallest fibonacci number that is >= to N.

目前，我正在使用地图记录斐波那契数字的值. 查询通常涉及搜索直到N的所有斐波那契数，而且由于涉及大量比较，因此效率不高.

Currently, I am using a map to record the value of the fibonacci numbers. A query normally involves searching all the fibonacci numbers up to N, and it is not very time efficient, as it involves a big number of comparisons.

这类查询会在我的程序中经常发生，并且我对可以改善查询的方式感兴趣，最好是使用亚线性复杂度.

This type of queries will occur quite often in my program, and I am interested in ways that I could improve the lookup, preferably with sub-linear complexity.

推荐答案

斐波那契数由Binet公式给出

The Fibonacci numbers are given by Binet's formula

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

其中phi是黄金比例，

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

这可以直接实现(Python示例):

This can be implemented straightforwardly (Python example):

<<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提供正确的结果.

Because of floating-point rounding errors, this will however only give the right result for n < 70.

Binet的公式可以通过忽略(1-phi)^n项来反转，而(1-phi)^n项在大的n中消失.因此，我们可以定义反斐波那契函数，当给定F(n)时，该函数将返回n(忽略该F(1) = F(2)):

Binet's formula can be inverted by ignoring the (1-phi)^n term, which disappears for large n. We can therefore define the inverse Fibonacci function that, when given F(n), returns n (ignoring that 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)))

在这里使用舍入法是我们的​​优势:它消除了由于我们对Binet公式的修改而引入的错误.实际上，如果给定任何可以作为精确整数存储在计算机内存中的斐波那契数，该函数将返回正确的答案.另一方面，它不验证给定的数字实际上是斐波那契数；输入大的斐波那契数或接近它的任何数将得到相同的结果.因此，您可以使用此想法来找到最接近给定数字的斐波那契数.

Here rounding is used to our advantage: it removes the error introduced by our modification to Binet's formula. The function will in fact return the right answer when given any Fibonacci number that can be stored as an exact integer in the computer's memory. On the other hand, it does not verify that the given number actually is a Fibonacci number; inputting a large Fibonacci number or any number close to it will give the same result. Therefore you can use this idea to find the Fibonacci number closest to a given number.

然后，想法是应用反斐波那契映射来查找任一侧上两个最接近的斐波那契数字N和M，然后使用直接斐波那契映射来计算P = F(N)和Q = F(M).这涉及更多的计算，但搜索更少.

The idea, then is to apply the inverse Fibonacci map to find N and M, the two closest Fibonacci numbers on either side, then use the direct Fibonacci map to compute P = F(N) and Q = F(M). This involves more computation, but less searching.

这篇关于寻找最接近的斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！