Últimos 10 dígitos de la milmillonésima número fibonacci?

Question

Quiero calcular los últimos diez dígitos de la milmillonésima parte de fibonacci número, pero mi notebook no tiene el poder para calcular dichos números grandes, así que a pesar de un truco muy simple: El acarreo de la suma es siempre ir de un dígito menos significativo al más significativo dígitos, para que yo pudiera agregar los números de fibonacci dentro de un límite de 8 bytes ( $0$ $18\cdot10^{18}$) y el abandono de los más dígitos significativos, porque no van a cambiar el menos significativo dígitos más.

Así, en lugar de utilizar $$F_{n+1}=F_n+F_{n-1}$$ to compute the whole number, I would use $$F_{n+1}=(F_n+F_{n-1})\operatorname{mod}18\cdot10^{18}$$ para ser capaces de seguir la pista de los últimos 10 dígitos.

Aquí mi pregunta: ¿puedo hacer esto?

Answer 1

EDIT: El período de repetición me dijo que era incorrecto. Gracias a @dtldarek por señalar mi error. La pertinente, correcta declaración sería

Para $n\geq 3$, la última $n$ dígitos de la secuencia de Fibonacci que se repita todos los $15\cdot 10^{n-1}$ términos.

Así que para el particular propósito de conseguir los últimos $10$ dígitos de $F_{1{,}000{,}000{,}000}$, este hecho no ayuda.

---

Para $n\geq 1$, la última $n$ dígitos de la secuencia de Fibonacci que se repita todos los $60\cdot 5^{n-1}$ términos. Por lo tanto, la última $10$ dígitos de $F_{1{,}000{,}000{,}000}$ son los mismos que la última $10$ dígitos de $F_{62{,}500{,}000}$ porque $$1{,}000{,}000{,}000\equiv 62{,}500{,}000\bmod \underbrace{117{,}187{,}500}_{60\cdot 5^9}$$ Esto ayudará a hacer que el problema computacionalmente tratable.

Answer 2

Una sugerencia con respecto a algunos de los comentarios: Decir $$X_n=\left[\begin{array}{}F_n\\F_{n+1}\end{array}\right].$$ Then $$X_{n+1}=AX_n$$for a certain $2\veces 2$ matrix $$. So you just have to calculate $^n$.

¿Por qué ir a la dificultad de la implementación de $2\times 2$ la multiplicación de la matriz? Porque entonces usted puede utilizar "exponenciación rápida", dando el resultado en el tiempo $\log(n)$. Un ejemplo dando la idea de que: Se podría calcular el $A^{11}$ $$A^{11}=AA^2A^8,$$after finding $A^{2^k}$ for $1\le k \le 3$. Which you do very quickly using $$A^{2^{k+1}}=\left(A^{2^k}\right)^2$$en un bucle. Un muy corto bucle...

Oh. No se dan cuenta de que es lo que el vínculo "de hecho" se fue. De todos modos, ahí está.

Answer 3

Una idea es muy buena, pero las cifras son las que sólo se conserva en cada iteración si el módulo es un múltiplo de a $10^{10}$. En otras palabras, mira en $$\tilde{F}_{n+1} = (\tilde{F}_n + \tilde{F}_{n-1}) \bmod 10^{10}$$ en su lugar. $\tilde{F}_{1000000000}$ consistirá entonces exactamente de la última $10$ dígitos de $F_{1000000000}$

Answer 4

Dado el siguiente código de Mathematica, basado en identidades encontrar aquí

Clear[f];
f[0] := 0;
f[1] := 1;
f[2] := 1;
f[n_ /; Mod[n, 3] == 0] := f[n] = With[{m = n/3}, 
    Mod[5 f[m]^3 + 3 (-1)^m f[m], 10^10]];
f[n_ /; Mod[n, 3] == 1] := f[n] = With[{m = (n - 1)/3}, 
    Mod[f[m + 1]^3 + 3 f[m + 1] f[m]^2 - f[m]^3, 10^10]];
f[n_ /; Mod[n, 3] == 2] := f[n] = With[{m = (n - 2)/3}, 
    Mod[f[m + 1]^3 + 3 f[m + 1]^2 f[m] + f[m]^3, 10^10]];

evaluación f[1000000000] de resultados en

1560546875

en menos de un 0.000887 segundos.

La única evaluaciones no son

f[0] = 0
f[1] = 1
f[2] = 1
f[3] = 2
f[7] = 13
f[8] = 21
f[23] = 28657
f[24] = 46368
f[69] = 9030460994
f[70] = 2490709135
f[209] = 3274930109
f[210] = 9082304280
f[627] = 3331634818
f[628] = 5364519011
f[1881] = 6891052706
f[1882] = 7684747991
f[5645] = 9674730645
f[5646] = 6983060328
f[16935] = 3041238690
f[16936] = 6494990027
f[50805] = 9095828930
f[50806] = 1802444783
f[152415] = 8092298210
f[152416] = 439009787
f[457247] = 3467735873
f[457248] = 3439061376
f[1371742] = 3463150271
f[1371743] = 8878860737
f[4115226] = 976213368
f[4115227] = 2499441093
f[12345679] = 9190666621
f[12345680] = 4288166885
f[37037037] = 2169005442
f[37037038] = 1145757919
f[111111111] = 7067038114
f[111111112] = 440574219
f[333333333] = 6434013378
f[333333334] = 4572218287
f[1000000000] = 1560546875