Encontrar la representación binaria de la $n$th Fibonacci plazo

Question

Objetivo: encontrar la representación binaria ( o no. de 1 en representación binaria) de n-ésimo término en la secuencia de Fibonacci, donde n es del orden de 10^6.

Mi enfoque actual: Encontrar el n-ésimo término (en decimal) en la secuencia de Fibonacci utilizando la matriz de exponenciación método y, a continuación, convertir el enésimo término a binario y luego encontrar el número de 1's.

Mi pregunta: ¿el programa Puede ser mejorado si yo recta por trabajar con números binarios? Hay un comparativamente manera más rápida de encontrar el n-ésimo término en la secuencia de Fibonacci si tratamos con números binarios?

Fibonacci sequence in decimal: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Fibonacci sequence in binary: 1, 10, 11, 101, 1000, 1101, 10101, 100010, 110111, 1011001, ...

Answer 1

Usted no sería un binario directo para calcular esto, pero en la actualidad no hay ninguno descubierto.

El modo más rápido es de alrededor de $O(\log^2 n)$ donde de una manera binaria puede parecerse más a $O(\log n)$. Esta comparación es como la diferencia entre lo rápido que las computadoras pueden agregar números, y lo rápido que las computadoras pueden multiplicar (multiplicando el uso normal de la escuela-basado, como lo hacemos nosotros. Hay maneras más complejas que son mucho más rápido). Así que, esencialmente, de la siguiente manera es todavía bastante rápido en comparación con un enfoque directo:

Curiosamente, en lugar de utilizar $F_n$ en una manera binaria, el siguiente algoritmo que utiliza $n$ en binario.

Tome nota de estas propiedades básicas de los números de Fibonacci:

• $F_{2k+1} = 4F_k^2 - F_{k-1}^2 + 2(-1)^k$
• $F_{2k-1} = F_k^2 + F_{k-1}^2$
• $F_{2k} = F_{2k+1} - F_{2k-1}$

Con estas propiedades podemos duplicar la posición de un número Fibonacci del índice, en lugar de ir uno por uno, lo cual hace que sea mucho más rápido.

Pasos:

1. Convertir el $n$ (en $F_n$) a binario. Ex: El $11th$ número Fibonacci, por lo $11$ en binario es $1011_2$
2. Ha $F_0 = 0$$F_1 = 1$, y deje $k = 1$ a empezar. Por último inicio de la $2nd$ dígito binario lugar de la izquierda. En este caso es el $0$.
3. Calcular el $(F_{2k-1}, F_{2k},F_{2k+1})$ el uso de las fórmulas mencionadas anteriormente.
4. Si el dígito lugar es $0$ uso de $(F_{2k-1}, F_{2k})$, si es impar el uso de $(F_{2k},F_{2k+1})$ para el próximo valores sustituto de $(F_{k-1},F_k)$. Ahora el turno de los dígitos uno a la derecha.
5. Repita los pasos 3 y 4 hasta que todos los dígitos lugares se han ido, y tendrá su final número Fibonacci que terminará siendo el valor final para su próxima $F_k$.

Ejemplo:

1. Para encontrar $F_{13}$, $n = 13$ en binario es $1101_2$
2. A partir de $(F_0,F_1) = (0,1)$, el siguiente valor de conjuntos son: $(1^2+0^2,F_{2k+1}-F_{2k-1},4(1)^2-0^2-2) = (1, 2-1, 2) = (1,1,2)$
3. Debido a que el $2nd$ dígito de la izquierda es un $1$, utilizaremos $(1,2)$ para nuestro próximo valores.
4. Siguiente valores: $(5,8,13)$. $3rd$ el dígito de la izquierda es un $0$, por lo que utilizamos (5,8).
5. Siguiente valores: $(89,144,233)$. $4th$ dígitos formulario de la izquierda es un $1$, por lo que utilizamos $(144,233)$, pero ese fue el último dígito lugar, por lo que nuestra respuesta es $F_k$,$233$.

Optimizaciones:

• Calcular el $F_k^2$ $F_{k-1}^2$ primer y reciclarlos cuando el cálculo de $F_{2k+1}$$F_{2k-1}$.
• Debido a $2(-1)^k$ $-2$ al $k$ es impar, y $+2$ al $k$ es incluso, Cualquier dígito lugar de lectura para determinar qué valores a utilizar para $(F_{k-1},F_k$), también predice que $+2$ o $-2$ a utilizar. Así, en nuestro ejemplo, porque lo hemos leído un $1$$2nd$, nos vamos a utilizar $-2$ para los próximos $2(-1)^k$. Y porque lo hemos leído un $0$$3rd$, nos vamos a utilizar $+2$ $2(-1)^k$ después. Así que use un $+2$ si usted lee un $0$, y el uso de $-2$ si usted lee un $1$.