Given an integer $n$ find the smallest index $k$ such that $\text{fib}(k) \ge n$ in logarithmic time? 
Given an integer $n$ find the smallest index $k$ such that $\text{fib}(k) \ge n$ in logarithmic time?

I've already programmed several algorithms to compute the $i$'th Fibonacci number $\text{fib}(i)$ in logarithmic time, i.e. by using a clever recurrence relation and matrix exponentation.
Computing $\text{fib}(k) \ge n$ in linear time is easy by using to accumulators and then incrementially proceed.
However, the logarithmic procedures operate top-down wrt. $i$ with base case $i=0$.
Any ideas?
 A: This isn’t an algorithm; it’s a closed form for the smallest $k$ such that $F_k\le n<F_{k+1}$, from which it’s not hard to get what you want.
It’s easy to prove from Binet’s exact formula for $F_n$ that $F_n$ is the integer nearest $\frac{\varphi^n}{\sqrt5}$, where $\varphi=\frac12\left(1+\sqrt5\right)$, and hence that
$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;.$$
An immediate consequence of this is that if $F>1$ is a Fibonacci number, its index in the Fibonacci sequence is
$$\left\lfloor\log_\varphi\left(F\sqrt5+\frac12\right)\right\rfloor\;.$$
It follows that if $F_k\le n<F_{k+1}$, then
$$k=\left\lfloor\log_\varphi\left(n\sqrt5+\frac12\right)\right\rfloor\;,$$
and only a little minor manipulation is required to get what you want.
A: Let $A(n)$ be the algorithm that return $(k,fib(k),fib(k-1)$ where $k$ is the smallest $k$ such that $fib(k)\geq n$
We defined $A(n)$ as follow:
$A(n)=(1,1,0)$ if $n=1$
otherwise let $(k,f_1,f_2)=A(n/2)$; $n\leq f_1$ return $(k,f_1,f_2)$ otherwise if $n\leq f_1+f_2$ return $(k+1,f_1+f_2,f_1)$ otherwise return $(k+2,2*f_1+f_2,f_1+f_2)$
