algorithm - Fibonacci algortihm to find if a number(or a close neighbour) is the difference between 2 fibonacii numbers -

algorithm - Fibonacci algortihm to find if a number(or a close neighbour) is the difference between 2 fibonacii numbers -

i hope can help me. given number n(which not necessary fibonacci number), must find if number equal difference between 2 fibonacci numbers, if not must homecoming closest number n, let's phone call m(which not necessary fibonacci number), difference between 2 fibonnaci numbers.

i not looking exact algorithm implementation pointers at.

thank in advance

assume without much loss of generality n > 0. since 1 = 1 - 0 = fib(1) - fib(0), result m positive well. allow 0 ≤ < j , consider fib(j) - fib(i). have bounds

fib(j-2) = fib(j) - fib(j-1) ≤ fib(j) - fib(i) ≤ fib(j).

therefore, each n, possibilities fib(j-2) ≤ n ≤ fib(j) need considered. in fact, can tighten fib(j-2) < n ≤ fib(j), since can write fib(j) - fib(j-1) fib(j-2) - fib(0). compute logarithm/use binary search find 2 valid settings of j. each setting of j, find best value of i same way.

algorithm math fibonacci