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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

For a finite size solution, perform a dichotomic search in the table below (blue up to 32 bits, 64 otherwise). This never takes more than $7$ comparisons.

$$\color{blue}{0:0\\ 1:1\\ 2:1\\ 3:2\\ 4:3\\ 5:5\\ 6:8\\ 7:13\\ 8:21\\ 9:34\\ 10:55\\ 11:89\\ 12:144\\ 13:233\\ 14:377\\ 15:610\\ 16:987\\ 17:1597\\ 18:2584\\ 19:4181\\ 20:6765\\ 21:10946\\ 22:17711\\ 23:28657\\ 24:46368\\ 25:75025\\ 26:121393\\ 27:196418\\ 28:317811\\ 29:514229\\ 30:832040\\ 31:1346269\\ 32:2178309\\ 33:3524578\\ 34:5702887\\ 35:9227465\\ 36:14930352\\ 37:24157817\\ 38:39088169\\ 39:63245986\\ 40:102334155\\ 41:165580141\\ 42:267914296\\ 43:433494437\\ 44:701408733\\ 45:1134903170\\ 46:1836311903\\ 47:2971215073}\\ 48:4807526976\\ 49:7778742049\\ 50:12586269025\\ 51:20365011074\\ 52:32951280099\\ 53:53316291173\\ 54:86267571272\\ 55:139583862445\\ 56:225851433717\\ 57:365435296162\\ 58:591286729879\\ 59:956722026041\\ 60:1548008755920\\ 61:2504730781961\\ 62:4052739537881\\ 63:6557470319842\\ 64:10610209857723\\ 65:17167680177565\\ 66:27777890035288\\ 67:44945570212853\\ 68:72723460248141\\ 69:117669030460994\\ 70:190392490709135\\ 71:308061521170129\\ 72:498454011879264\\ 73:806515533049393\\ 74:1304969544928657\\ 75:2111485077978050\\ 76:3416454622906707\\ 77:5527939700884757\\ 78:8944394323791464\\ 79:14472334024676221\\ 80:23416728348467685\\ 81:37889062373143906\\ 82:61305790721611591\\ 83:99194853094755497\\ 84:160500643816367088\\ 85:259695496911122585\\ 86:420196140727489673\\ 87:679891637638612258\\ 88:1100087778366101931\\ 89:1779979416004714189\\ 90:2880067194370816120\\ 91:4660046610375530309\\ 92:7540113804746346429\\ 93:12200160415121876738\\ $$