寻找最接近的斐波纳契数

Question

我试图解决一个更大的问题,我认为该程序的一个重要部分是花在低效计算上.

我需要计算给定数N,区间[P,Q],其中P是<=到N的最大斐波纳契数,而Q是> =到N的最小斐波纳契数.

目前,我正在使用地图来记录斐波纳契数的值.查询通常涉及搜索最多为N的所有斐波纳契数,并且它不是非常节省时间,因为它涉及大量的比较.

这种类型的查询将在我的程序中经常出现,我对可以改进查找的方式感兴趣,最好是使用子线性复杂性.

Answer 1

Fibonacci数字由Binet公式给出

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

哪个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.

Binet的公式可以通过忽略该(1-phi)^n术语来反转,该术语消失得很大n.因此,我们可以定义反Fibonacci函数,当给定时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)))

这里使用舍入对我们有利:它消除了我们修改Binet公式所引入的错误.实际上,当给定任何Fibonacci数时,该函数将返回正确的答案,该数字可以存储为计算机内存中的精确整数.另一方面,它不验证给定的数字实际上是斐波纳契数; 输入一个大的Fibonacci数或任何接近它的数字都会得到相同的结果.因此,您可以使用此想法查找最接近给定数字的斐波纳契数.

这个想法,然后是应用逆斐波纳契地图找N和M,两边的两个最接近的斐波那契数,然后使用直接斐波那契映射来计算P = F(N)和Q = F(M).这涉及更多的计算,但搜索较少.

Answer 2

我在https://ideone.com/H6SAd上发布了完整的Proof-Of-Concept实现

• 它非常快
• 它使用adhoc二进制搜索
• 在阅读其他回复后编辑,我感觉那里概述的数学思想(PengOne)将导致更快的查找(基本上:反转公式的计算加上floor()/ ceil()调用？)

.

#include <cmath>
#include <iostream>

const double pheta = 0.5*(std::sqrt(5)+1);

double fib(unsigned int n)
{
    return (std::pow(pheta, n) - std::pow(1 - pheta, n)) / std::sqrt(5);
}

unsigned int fibo_lowerbound(double N, unsigned min=0, unsigned max=1000)
{
    unsigned newpivot = (min+max)/2;
    if (min==newpivot)
        return newpivot;

    if (fib(newpivot) <= N)
        return fibo_lowerbound(N, newpivot, max);
    else
        return fibo_lowerbound(N, min, newpivot);
}

std::pair<double, double> fibo_range(unsigned int n)
{
    unsigned int lbound = fibo_lowerbound(n);
    return std::make_pair(fib(lbound), fib(lbound+1));
}

void display(unsigned int n)
{
    std::pair<double, double> range = fibo_range(n);
    std::cout << "Fibonacci range wrapping " << n << " is "
              << "[" << (unsigned long long) range.first << ", " << (unsigned long long) range.second << "]"
              << std::endl;
}

int main()
{
    display(1044);
    display(8999913);
    display(7);
    display(67);
}

输出是:

Fibonacci range wrapping 1044 is [987, 1597]
Fibonacci range wrapping 8999913 is [5702887, 9227465]
Fibonacci range wrapping 7 is [5, 8]
Fibonacci range wrapping 67 is [55, 89]

Answer 3

您可以使用斐波纳契数的闭合表达式.

由于它的第二项非常小,你可以用第一项来近似它,因此n可以找到基本黄金比率对数.