Finding the closest fibonacci numbers

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

Then binary search

I just did a CodeChef puzzle that was this exact problem (http://www.codechef.com/problems/DPC204). I simply calculated the Fibonacci sequence from 0 to the end of the range, and counted how many were after the beginning of the range. My test for whatever their sample inputs were took 2.6M, and 0.00s, so the nieve solution is plenty fast enough.

Basically, I made a big-unsigned-int class made of unsigned int[333], and calculate two numbers per loop, to avoid swaps.

start with A=0,B=1;
A+=B;B+=A; 
now A==1,B==2, the next two Fib. numbers, with no swaps.
A+=B;B+=A; 
now A==3,B==5, the next two Fib. numbers, with no swaps.

It is slightly complicated by the fact you have to stop and check if the neither, one, or both numbers are in the range, but A

My solution on CodeChef clocked in at 0.00 seconds, so I think this method ought to be fast enough, you just have to write a function that adds one uint[333] to another uint[333] (using all 32 bits, just chars for each decimal digit)

Since you consider only 64 bit integers, there are at most about 100 Fibonacci numbers to consider. You can precompute them using their definition F_n = F_n-1 + F_n-2.

Then precompute another table that maps the number of leading zero bits to an index in the table of Fibonacci numbers, to the first number with that many leading zero bits.

Now to find the interval use the number of leading zero bits of your number (this can be computed quickly as many processors have a special instruction for it) to find a starting point using the second table, and linearly search through the first table for the interval. Since there are at most two Fibonacci numbers between adjacent powers of two this takes at most 2 steps.

This has the advantage that it only uses integer arithmetic, which is exact and tends to be faster than floating point computations.