Enésimo término de Fibonacci

Question

Se sabe que el enésimo término de la sucesión de Fibonacci se puede encontrar mediante la fórmula

$F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ ,

donde $\phi$ es la proporción áurea (1,618...).

1. ¿Sería esta la mejor fórmula para generar términos grandes de la secuencia (ej. $n = 10^{15}$ )?
2. ¿Cuántos decimales de $\phi$ debe ser conocido para generar un término tan grande?
3. ¿Cómo se puede invertir esta fórmula (es decir, encontrar $F_n^{-1}$ )?

Answer 1

Para la parte (3), $F_1=F_2=1$ por lo que no se puede esperar una fórmula de inversión que funcione para todos $n$ . Para grandes $n$ Sin embargo, el término en $\phi^{-n}$ se vuelve muy pequeño y $F_n$ es el número entero más cercano a $\frac {\phi^n} {\sqrt 5}$ y es casi cierto que $$n=\frac{\log {(F_n\sqrt 5)}}{\log {\phi}}$$

Answer 2

1. Incluso para un tamaño modesto $n$ No se trata de una buena manera de generar exacto valores de $F_n$ . ¿Por qué utilizar la aritmética de punto flotante cuando se puede simplemente exponer $\left(\begin{array}{cc}1&1\\1&0\end{array}\right)$ ¿al menos tan rápido? Sólo es útil para estimar rápidamente los primeros dígitos de $F_n$ .

2. No es práctico calcular los valores exactos de $F_n$ cuando $n=10^{15}$ . Se trata de un número con 200 billones de dígitos decimales. Necesitarás al menos esa cantidad de dígitos de precisión en $\phi$ Lo cual es una tontería.

3. Si ves la respuesta de Aang, esta forma se puede invertir con bastante facilidad.

Answer 3

Para la precisión de $\phi$ , ya que $F_n \approx \frac {\phi^n}{\sqrt 5}$ el error fraccionario en $F_n$ es el mismo que su error fraccionario en $\phi^n$ . Si en lugar de $\phi^n$ tienes $(\phi(1+\epsilon))^n$ el error fraccionario es $(1+\epsilon)^n \approx 1+n\epsilon$ . Si quieres $F_n$ para ser exactos, necesitas $\frac {n\epsilon}{\phi^n}\lt 1$ o $\epsilon \lt \frac {\phi^n}n$

Answer 4

Para la parte $(1)$ , Ya que $\frac{|\phi|^n}{\sqrt 5}\lt \frac{1}{2}$ $$F_n=\lfloor \frac{\phi^n}{\sqrt 5}+\frac{1}{2}\rfloor$$ como donde $\lfloor . \rfloor $ representa la mayor función entera

Para la parte $(3)$ , Para incluso $n$ , $$F_n=\frac{\phi^n-\frac{1}{\phi^n}}{\sqrt 5}=\frac{\phi^{2n}-1}{\phi^n\sqrt 5}$$ $$\implies (\phi^n)^2-(\sqrt 5 F_n) (\phi^n)-1=0$$ .

Se trata de una ecuación cuadrática en $\phi^n$ resolviendo lo que obtenemos,

$$\phi^n=\frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2}$$ (raíz negativa descartada) $$\implies n=\log_\phi \frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2}=\frac{\ln (\frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2})}{\ln \phi}$$

Como se puede ver, para los grandes $F_n$ , $\sqrt{5F_n^2+4}\approx\sqrt 5 F_n$ que da $$n\approx\frac{\ln \sqrt 5F_n}{\ln \phi}$$ para grandes $F_n$

Para impar $n$ se realizan cálculos similares que dan como resultado

$$n=\frac{\ln (\frac{\sqrt 5F_n+\sqrt{5F_n^2-4}}{2})}{\ln \phi}$$

Pero como no sabes si $n$ es par o impar,

mi sugerencia es calcular ambas expresiones (tanto para la par como para la impar) y comprobar cuál $n$ encaja mejor.

Para los grandes $F_n$ Estas expresiones darían el mismo resultado $n$ Así que no hay que preocuparse por los grandes $F_n$

Answer 5

Si lo calcula con un lenguaje de programación, la precisión dependerá de cuántos dígitos decimales tenga para $\phi$ una solución mejor es manipular la fórmula original $\phi = \frac{1+\sqrt5}2$ manteniéndolo como está hasta ampliarlo en el último cómputo..

Esta es la función inversa: $\frac{\log\left(\frac12\left(\sqrt 5 x - \sqrt{4 + 5 x^2}\right)\right)}{\log ϕ}$