I've been working on a coding challenge, and have determined how to perform a solution in logarithmic time; however, I'd like to solve it in constant time.
Given Binet's Formula for calculating the $n$-th Fibonacci sequence, I'd like to find the inverse to calculate when the Fibonacci sequence is equal to or less than some number.
Here is Binet's formula for a refresher:
$F_n = ((\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2}) ^n) / \sqrt5$
which can be simplified to:
$y = A^x - B^x$
$A = \frac{1+\sqrt5}{2}$, $B = \frac{1-\sqrt5}{2}$, $y = \frac{F_n}{\sqrt5}$, $x = n$
I'd like to solve for x; however I do not have the knowledge or educational experience to solve logarithms of different bases.
If I try:
$A^x = y + B^x$
$\log_A(A^x) = \log_A(y + B^x)$
$x = \log_A(y + B^x)$
which I am unsure how to solve from there. Is this problem even solvable?
As no solution has yet been posted, using the hint that was provided about a month ago, we have
$$ \lim_{n \to \infty} \left( \frac{1-\sqrt{5}}{2} \right)^{n} = 0$$
and so, as $n$ increases,
$$ F_{n} \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{n} $$
So, solving the following inequality for $n$:
$$ \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{n} \leq K, $$
we get, after multiplying both sides by $\sqrt{5}$ and taking the natural log of both sides:
$$ n \ln\left( \frac{1 + \sqrt{5}}{2} \right) \leq \ln(\sqrt{5}K) $$
and therefore,
$$ n \leq \frac{\ln(\sqrt{5}K)}{\ln\left(\frac{1 + \sqrt{5}}{2} \right)} = \frac{\ln(\sqrt{5}K)}{\ln(1 + \sqrt{5}) - \ln 2};$$
So, we may take
$$ n = \left\lfloor \frac{\ln(\sqrt{5}K)}{\ln(1 + \sqrt{5}) - \ln 2} \right\rfloor.$$
$Remark:$ The RHS of Binet's equation is always $< 1$, tends to zero rapidly as a commentator pointed out, and so contributes very little (almost nothing as $n$ gets large) to the value of $F_{n}$. Therefore, we were able to pretty much ignore it for this problem.