¿Qué es un algoritmo rápido para encontrar el resto de la división de un gran número de Fibonacci por algún entero grande?

Answer 1

Cada recurrencia similar a los números de Fibonacci se puede expresar en términos de multiplicación de matrices de la siguiente manera:
Para calcular el próximo número de Fibonacci [matemática] F_ {n + 2} [/ matemática], necesitamos dos anteriores: [matemática] (F_n, F_ {n + 1}) [/ matemática]. La transformación que cambia [matemática] (F_n, F_ {n + 1}) [/ matemática] a [matemática] (F_ {n + 1}, F_ {n + 2}) [/ matemática] es lineal, y por lo tanto puede encontrar una matriz que lo realiza:

[matemáticas] \ forall a, b: (a, b) \ cdot \ left (\ begin {smallmatrix} 0 & 1 \\\\ 1 & 1 \ end {smallmatrix} \ right) = (b, a + b) [/matemáticas].

Llamemos a la matriz anterior [matemáticas] A [/ matemáticas]. Obviamente, para cualquier [matemática] n [/ matemática] tenemos:

[matemáticas] (F_n, F_ {n + 1}) \ cdot A = (~ F_ {n + 1}, ~ F_n + F_ {n + 1} ~) [/ matemáticas]

que es precisamente [matemáticas] (F_ {n + 1}, F_ {n + 2}) [/ matemáticas].

Podemos usar [math] A [/ math] varias veces. Por ejemplo:

[matemáticas] \ Big (\ Big ((F_0, F_1) \ cdot A \ Big) \ cdot A \ Big) \ cdot A = (F_3, F_4) [/ math]

Ahora viene una observación importante: la multiplicación de matrices es asociativa. Por lo tanto, podemos escribir lo anterior simplemente de la siguiente manera:
[matemáticas] (F_0, F_1) \ cdot A ^ 3 = (F_3, F_4) [/ matemáticas]
Y en general:
[matemáticas] (0,1) \ cdot A ^ n = (F_n, F_ {n + 1}) [/ matemáticas]

La ecuación anterior es válida en enteros, por lo tanto, es válido módulo any [math] m [/ math].

Calculando el módulo [math] m [/ math], podemos usar la exponenciación al cuadrar para calcular [math] A ^ n [/ math] usando las operaciones [math] O (\ log n) [/ math] en números menores que [math ] m ^ 2 [/ matemáticas].

En términos de una implementación práctica: siempre que [math] m [/ math] se ajuste a una variable entera de 32 bits, todos los valores intermedios se ajustarán a variables de 64 bits, y puede usar la fórmula anterior para calcular [math] F_n ~ \ bmod ~ m [/ math] incluso para [math] n = 10 ^ {1000} [/ math].

(O use un lenguaje con números enteros de precisión arbitraria si necesita valores mayores de [math] m [/ math]. Por ejemplo, [math] n = m = 10 ^ {1000} [/ math] sigue siendo perfectamente factible).

Implementación de muestra: http://ideone.com/fP8krp

Answer 2

bueno, si su número contiene 1000 de dígitos, le sugiero que use
gmpy Es una solución elegante implementada en Python. Alternativamente, también puede usar BigInteger si el idioma de su preferencia es Java. Espero que esto ayude :).