enésimo número de Fibonacci en tiempo sublineal
¿Existe algún algoritmo para calcular el enésimo número de Fibonacci en tiempo sublineal?
Siguiendo la referencia de Pillsy a la exponenciación matricial, de modo que para la matriz
METRO = [1 1]
[1 0]
entonces
fib ( norte ) = M norte 1,2
Elevar matrices a potencias mediante multiplicación repetida no es muy eficiente.
Dos enfoques para la exponenciación matricial son dividir y conquistar, que produce M n en O ( ln n ) pasos, o la descomposición de valores propios, que es un tiempo constante, pero que puede introducir errores debido a la precisión limitada del punto flotante.
Si desea un valor exacto mayor que la precisión de su implementación de punto flotante, debe usar el enfoque O ( ln n ) basado en esta relación:
M n = ( M n /2 ) 2 si n es par = M · M n -1 si n es impar
La descomposición de valores propios en M encuentra dos matrices U y Λ tales que Λ es diagonal y
M = U Λ U -1
M n = ( U Λ U -1 ) n
= U Λ U -1 U Λ U -1 U Λ U -1 ... n veces
= U Λ Λ Λ ... U -1
= U Λ n U -1
Elevar a la matriz diagonal Λ a la n -ésima potencia es una simple cuestión de elevar cada elemento en Λ a la n- ésima, por lo que esto da un método O(1) para elevar M a la n -ésima potencia. Sin embargo, no es probable que los valores de Λ sean números enteros, por lo que se producirá algún error.
Definiendo Λ para nuestra matriz 2x2 como
Λ = [ λ 1 0 ] = [ 0 λ 2 ]
Para encontrar cada λ , resolvemos
| M - λI | = 0
lo que da
| M - λI | = -λ ( 1 - λ ) - 1 λ² - λ - 1 = 0
usando la fórmula cuadrática
λ = ( -b ± √ ( b² - 4ac ) ) / 2a
= ( 1 ± √5 ) / 2
{ λ 1 , λ 2 } = { Φ, 1-Φ } donde Φ = ( 1 + √5 ) / 2
Si ha leído la respuesta de Jason, podrá ver hacia dónde irá esto.
Resolviendo para los vectores propios X 1 y X 2 :
si X 1 = [ X 1,1 , X 1,2 ] M. _ X 1 1 = λ 1 X 1 X 1,1 + X 1,2 = λ 1 X 1,1 X 1,1 = λ 1 X 1,2 => X 1 = [ Φ, 1 ] X 2 = [ 1-Φ, 1 ]
Estos vectores dan U :
U = [ X 1,1 , X 2,2 ]
[ X 1,1 , X 2,2 ]
= [Φ, 1-Φ]
[ 1, 1 ]
Invirtiendo U usando
A = [ ab ]
[ cd ]
=>
A -1 = ( 1 / | A | ) [ re -b ]
[-ca]
entonces U -1 está dado por
U -1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
[ -1 Φ ]
U -1 = ( √5 ) -1 [ 1 Φ-1 ]
[ -1 Φ ]
Prueba de cordura:
UΛU -1 = ( √5 ) -1 [ Φ 1-Φ ] . [ Φ 0 ] . [ 1Φ-1 ]
[ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]
sea Ψ = 1-Φ, el otro valor propio
ya que Φ es una raíz de λ²-λ-1=0
entonces -ΨΦ = Φ²-Φ = 1
y Ψ+Φ = 1
UΛU -1 = ( √5 ) -1 [ Φ Ψ ] . [ Φ 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ ] [ -1 Φ ]
= ( √5 ) -1 [ Φ Ψ ] . [Φ-ΨΦ]
[ 1 1 ] [ -Ψ ΨΦ ]
= ( √5 ) -1 [ Φ Ψ ] . [Φ1]
[ 1 1 ] [ -Ψ -1 ]
= ( √5 ) -1 [ Φ²-Ψ² Φ-Ψ ]
[ Φ-Ψ 0 ]
= [Φ+Ψ1]
[ 1 0 ]
= [1 1]
[ 1 0 ]
= METRO
Así que el control de cordura se mantiene.
Ahora tenemos todo lo que necesitamos para calcular M n 1,2 :
M norte = U Λ norte U -1
= ( √5 ) -1 [ Φ Ψ ] . [ Φ norte 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ norte ] [ -1 Φ ]
= ( √5 ) -1 [ Φ Ψ ] . [ Φ norte -ΨΦ norte ]
[ 1 1 ] [ -Ψ norte Ψ norte Φ ]
= ( √5 ) -1 [ Φ Ψ ] . [ Φ norte Φ norte -1 ]
[ 1 1 ] [ -Ψ n -Ψ n -1 ] como ΨΦ = -1
= ( √5 ) -1 [ Φ n +1 -Ψ n +1 Φ n -Ψ n ]
[ Φ norte -Ψ norte Φ norte -1 -Ψ norte -1 ]
entonces
fib ( n ) = M n 1,2
= ( Φ n - (1-Φ) n ) / √5
Lo que concuerda con la fórmula dada en otra parte.
Puede derivarlo de una relación de recurrencia, pero en ingeniería, computación y simulación, calcular los valores propios y vectores propios de matrices grandes es una actividad importante, ya que proporciona estabilidad y armónicos a los sistemas de ecuaciones, además de permitir elevar matrices a altas potencias de manera eficiente.
El nnúmero de Fibonacci está dado por
f(n) = Floor(phi^n / sqrt(5) + 1/2)
dónde
phi = (1 + sqrt(5)) / 2
Suponiendo que las operaciones matemáticas primitivas ( , +y ) son , puede usar este resultado para calcular el enésimo número de Fibonacci en el tiempo ( debido a la exponenciación en la fórmula).-*/O(1)nO(log n)O(log n)
Cª#:
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
const double inverseSqrt5 = 0.44721359549995793928183473374626
const double phi = 1.6180339887498948482045868343656
*/
static int Fibonacci(int n) {
return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
Si desea el número exacto (que es un "bignum", en lugar de un int/float), entonces me temo que
¡Es imposible!
Como se indicó anteriormente, la fórmula de los números de Fibonacci es:
fib n = piso (phi n /√5 + 1 / 2 )
fib norte ~= fi norte /√5
¿ Cuántos dígitos tiene fib n?
numDigits (fib n) = log (fib n) = log (phi n /√5) = log phi n - log √5 = n * log phi - log √5
numDigits (fib n) = n * constante + constante
esta encendido ) _ _
Dado que el resultado solicitado es de O ( n ), no se puede calcular en menos de O ( n ) tiempo.
Si solo desea los dígitos inferiores de la respuesta, entonces es posible calcular en tiempo sublineal utilizando el método de exponenciación matricial.
Uno de los ejercicios en SICP trata sobre esto, cuya respuesta se describe aquí.
En el estilo imperativo, el programa se vería así
Función Fib ( recuento )
a ← 1
b ← 0
p ← 0
q ← 1
Mientras cuenta > 0 Hazlo
si Par( cuenta ) Entonces
p ← p ² + q ²
q ← 2 pq + q ²
cuenta ← cuenta ÷ 2
De lo contrario
a ← bq + aq + ap
b ← bp + aq
cuenta ← cuenta - 1
Fin si
terminar mientras
Regresar b
Función final
