74 votos

enésimo número de fibonacci en sublinear tiempo

¿Hay algún algoritmo para calcular el n-ésimo número de fibonacci en áfrica tiempo lineal?

98voto

Pete Kirkham Puntos 32484

Siguiente de Pillsy la referencia a la matriz de la exponenciación, de tal manera que para la matriz

M = [1 1] 
 [1 0] 

entonces

fib(n) = Mn1,2

Recaudación de las matrices de competencias mediante la multiplicación repetida no es muy eficiente.

Dos enfoques de la matriz de exponenciación se divide y vencerás que los rendimientos de Mn de O(ln n) pasos, o autovalor de descomposición que es constante en el tiempo, pero puede introducir errores debido a la limitación de punto flotante de precisión.

Si desea un valor exacto mayor que la precisión de su punto flotante aplicación, usted tiene que utilizar el O ( ln n ) enfoque basado en esta relación:

Mn = (Mn/2)2 si nincluso
 = M.Mn-1 si n es impar

El autovalor de la descomposición en M encuentra dos matrices U y Λ tal que Λ es la diagonal y

 M = U L U-1Mn = ( U Λ U-1) n
 = U L U-1U L U-1U L U-1 ... n veces
 = U Λ Λ Λ ... U-1
 = U L nU-1
Criar a un la diagonal de la matriz de L a la nº que el poder es una simple cuestión de crianza de cada elemento en Λ para el nth, así que esto le da un O(1) método de criar a M a nth poder. Sin embargo, los valores en Λ es probable que no sean números enteros, por lo que algunos errores.

La definición de Λ para nuestra matriz de 2x2 como

Λ = [ λ1 0 ]
 = [ 0 λ2]

Para encontrar cada λ, podemos resolver

 |M - λI| = 0
lo que da
 |M - λI| = -λ ( 1 - λ ) - 1

λ2 - λ - 1 = 0

el uso de la fórmula cuadrática

λ = ( -b ± √ ( b2 - 4ac ) ) / 2a
 = ( 1 ± √5 ) / 2
 { λ1, l2 } = { Φ, 1-Φ } donde Φ = ( 1 + √5 ) / 2

Si has leído Jason respuesta, usted puede ver donde esta se va a ir.

La solución para que los vectores propios de X1 y X2:

si X1 = [ X1,1, X1,2]

 M.X1 1 = λ1X1X1,1 + X1,2 = λ1X1,1X1,1 = λ1X1,2

=>
 X1 = [ Φ, 1 ]
 X2 = [ 1-Φ, 1 ]

Estos vectores dar U:

U = [ X1,1, X2,2]
 [ X1,1, X2,2]

 = [ Φ, 1-Φ ]
 [ 1, 1 ]

La inversión de U uso

Un = [ a b ]
 [ c, d ]
=>
Un-1 = ( 1 / |a Un| ) [ d-b ]
 [ -c ]

así que U-1 está dada por

U-1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
 [ -1 Φ ]
U-1 = ( √5 )-1 [ 1-Φ 1 ]
 [ -1 Φ ]

Verificación de cordura:

UΛU-1 = ( √5 )-1 [ Φ 1-Φ ] . [ Φ 0 ] . [ 1 Φ-1 ] 
 [ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]

vamos a Ψ = 1-Φ, el otro autovalor

como Φ es una raíz de λ2-λ-1=0 
así ΨΦ = Φ2-Φ = 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 [ Φ2-Ψ2 Φ-Ψ ] 
 [ Φ-Ψ 0 ]

 = [ Φ+Ψ 1 ] 
 [ 1 0 ]

 = [ 1 1 ] 
 [ 1 0 ]

 = M

Para la comprobación de validez tiene.

Ahora tenemos todo lo que necesitamos para calcular Mn1,2:

Mn = ULnU-1
 = ( √5 )-1 [ Φ Ψ ] . [ Φn 0 ] . [ 1-Ψ ] 
 [ 1 1 ] [ 0 Ψn ] [ -1 Φ ]

 = ( √5 )-1 [ Φ Ψ ] . [ Φn -ΨΦn ] 
 [ 1 1 ] [ -Ψn ΨnΦ ]

 = ( √5 )-1 [ Φ Ψ ] . [ Φn Φn-1 ] 
 [ 1 1 ] [ -Ψnn-1 ] como ΨΦ = -1

 = ( √5 )-1 [ Φn+1n+1 Φnn]
 [ Φnn Φn-1n-1]

así

 fib(n) = Mn1,2
 = ( Φn - (1-Φ)n ) / √5

Lo cual está de acuerdo con la fórmula dada en otros lugares.

Se puede derivar de un recurrance relación, pero en ingeniería de computación y simulación de cálculo de los autovalores y autovectores de matrices es una actividad importante, ya que da estabilidad y armónicos de los sistemas de ecuaciones, así como permitir la recaudación de las matrices a los altos poderes de manera eficiente.

64voto

Jason Puntos 125291

El nésimo número de Fibonacci está dada por

f(n) = Floor(phi^n / sqrt(5) + 1/2)

donde

phi = (1 + sqrt(5)) / 2

Suponiendo que la primitiva operaciones matemáticas (+, -, * y /) O(1) puede utilizar este resultado para calcular el nésimo número de Fibonacci en O(log n) de tiempo (O(log n) debido a la exponenciación en la fórmula).

En 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);
}

55voto

yairchu Puntos 9694

Si desea que 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 = floor (phin/√5 + 1/2)

fib n ~= phin/√5

Cuántos dígitos se fib n?

numDigits (fib n) = log (fib n) = log (pin/√5) = log phin - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

es O(n)

Desde que la solicitó resultado es de O(n), no puede ser calculado en menos de O(n) tiempo.

Si desea que sólo el menor de los dígitos de la respuesta, entonces es posible calcular en sub-tiempo lineal utilizando la matriz de exponenciación método.

33voto

Nietzche-jou Puntos 7711

Uno de los ejercicios en el SICP es esto, que tiene la respuesta se describe aquí.

En el imperativo de estilo, el programa sería algo como

La función de la Fib(recuento)
 un ← 1
 b ← 0
 p ← 0
 q ← 1

 Mientras count > 0 Hacer
 Si Aún(recuento) , a Continuación,
 pp2 + q2
 q ← 2pq + q2
 contarcontar ÷ 2
 Otra cosa
 unbq + aq + ap
 bbp + aq
 contarcount - 1
 End If
 Fin Mientras

 Retorno b
Final De La Función

24voto

Pillsy Puntos 7094

Usted puede hacerlo por exponentiating una matriz de enteros así. Si usted tiene la matriz

    / 1  1 \
M = |      |
    \ 1  0 /

a continuación, (M^n)[1, 2] va a ser igual a la nésimo número de Fibonacci, si [] es una matriz de subíndice y ^ es la matriz de exponenciación. Para un tamaño fijo de la matriz, la exponenciación a un positivo de poder integral se puede hacer en O(log n) tiempo de la misma manera que con los números reales.

EDIT: por supuesto, dependiendo del tipo de respuesta que usted desea, usted puede ser capaz de salirse con la constante de tiempo del algoritmo. Igual que las otras fórmulas de mostrar, la nth Fibonacci número crece exponencialmente con n. Incluso con 64 bits enteros sin signo, sólo necesitas un 94-entrada de la tabla de búsqueda con el fin de cubrir toda la gama.

SEGUNDA EDICIÓN: Haciendo la matriz exponencial, con un eigendecomposition primera es exactamente equivalente a JDunkerly de la solución a continuación. Los valores propios de esta matriz son los (1 + sqrt(5))/2 y (1 - sqrt(5))/2.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X