Búsqueda de índice de un número Fibonacci: cualquier matemático solución posible?

Question

El problema:

               Given a Fibonacci number,find its index.

Soy consciente de la solución estándar de 'generar-hash-encontrar'. Estoy solo por curiosidad, si hay algunos inversa sistema de matriz de exponenciación o algún otro método matemático que da la solución.

Answer 1

De la wikipedia: "Del mismo modo, si ya sabemos que el número F es un número de Fibonacci, podemos determinar su índice dentro de la secuencia

$$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2} \right)\bigg\rfloor.$$

Answer 2

El uso de esta mi respuesta
Usando números enteros solamente, me gustaría utilizar el Binario de Búsqueda. Ciertamente, se puede calcular el $F_n$ sólo con números enteros, la forma más sencilla es la matriz de exponenciación. Mediante Búsqueda Binaria usted puede encontrar los números de `cerca de" su número $x$ y usted encontrará $x = F_n$ (e $n$). Supongo que este método es genérico para nada monótona puede calcular rápido. A initiliaze la búsqueda binaria, sólo seguir doblando $ F_{2n} $

Binario de búsqueda le permite buscar un número x en función de un criterio de "matriz" F[] (en la programación de sentido). El uso de este método para la búsqueda de su número. Cuando usted necesita F[n] al calcular $F_n$. Esto funciona porque la secuencia es estrictamente creciente, excepto para la inicial de 1,1.