Finding the closest fibonacci numbers

I posted a complete Proof-Of-Concept implementation of this on https://ideone.com/H6SAd

• it is blazingly fast
• it uses an adhoc binary search
• Edit after reading the other responses, I have a feeling that mathematical ideas outlined there (PengOne) will lead to a quicker lookup (basically: a calculation of the inverted formula plus a floor()/ceil() call?)

.

#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);
}

The output is:

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]

You can use the closed-form expression of the fibonacci numbers.

Since the second term in it is very small, you can approximate it with just the first term, so n can be found with base-golden ratio logarithm.

The Fibonacci numbers are given by Binet's formula

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

where phi is the golden ratio,

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

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))

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

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)))

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.

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.

Use the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Then binary search