n-ésimo número de fibonacci en tiempo sublineal

76

¿Existe algún algoritmo para calcular el n-ésimo número de fibonacci en tiempo sub lineal?

Biswajyoti Das
fuente
4
Se podría argumentar que está relacionado con los algoritmos, ya que el OP hace una vaga referencia a la complejidad algorítmica ... Aunque todavía tendría curiosidad por saber qué algoritmo.
Matthew Scharley
2
Las dos respuestas siguientes tienen la fórmula correcta. Sobre si esta pregunta está relacionada con la programación: es parte de la informática. El aparato utilizado para derivar la fórmula se conoce como "funciones generadoras" y tiene un papel importante en el análisis de algoritmos.
azheglov
1
@azheglov: Si bien las funciones de generación son útiles, no son necesarias para derivar la expresión de forma cerrada para la secuencia de Fibonacci.
Jason
7
Tiene un problema que desea resolver por cualquier motivo y desea hacerlo de manera eficiente. A veces, la información necesaria será una nueva implementación, a veces un algoritmo y, a veces, matemáticas. No hay necesidad de denunciar la situación como "no relacionada con la programación" cada vez que ocurre esto último.
ShreevatsaR
7
El tamaño del resultado es lineal en n. Por lo tanto, no existe tal algoritmo. Por supuesto, eso no invalida ninguna de las buenas respuestas a continuación que calculan números de Fibonacci usando operaciones aritméticas O (log n).
Accipitridae

Respuestas:

66

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 O(1)puede utilizar este resultado para calcular la nésimo número de Fibonacci en O(log n)el tiempo ( O(log n)debido a la exponenciación en la fórmula).

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);
}
jason
fuente
7
@Json No te he votado negativamente, pero es posible que otros lo estén haciendo porque tu respuesta sugiere que el número Nth de fibonacci se puede calcular en tiempo O (log n), lo cual es falso. Su código está calculando una aproximación. Su código sería al menos O (n) con precisión arbitraria, porque la longitud de la respuesta es O (n).
PeterAllenWebb
10
@PeterAllenWebb: La fórmula proporcionada no es una aproximación. El n-ésimo número de Fibonacci es igual al piso de phi^n / sqrt(5) + 1/2donde phi = (1 + sqrt(5)) / 2. Esto es un hecho. En segundo lugar, entiendo el punto que otros están haciendo acerca de la longitud de la respuesta, O(n)pero agregué un comentario a mi respuesta asumiendo que las operaciones matemáticas primitivas toman un tiempo constante (sé que no lo son a menos que limite las entradas). Mi punto es que podemos encontrar el número n de Fibonacci en O(log n)operaciones aritméticas.
Jason
4
@Jason: Suponiendo que la potenciación es O (1) también hace que todo el algoritmo sea O (1). Eso sería bueno, sin embargo, la exponenciación no es O (1) y tampoco lo son las otras operaciones matemáticas primitivas. Entonces, en resumen, la fórmula es buena, pero no calcula el resultado en tiempo sublineal.
yairchu
12
@Jason: La fórmula no es una aproximación, pero el código es una aproximación (excepto en una implementación imaginaria de C # en la que Math.Pow (…) tiene precisión infinita, en cuyo caso el código es O (n)).
ShreevatsaR
14
@ Jason: No. Ejecute su código en n = 1000 (para el cual el número de Fibonacci 43466 ... 849228875 tiene 209 dígitos miserables) y dígame si obtiene todos los dígitos correctamente. Para que Math.Floor obtenga la parte entera correcta, Math.Pow debe calcular con precisión esos dígitos. De hecho, en mi implementación de C ++, incluso el F_ {74} = 130496954492865 de 16 dígitos se calcula incorrectamente, aunque el número entero 130496954492865 se puede representar exactamente (con long long), y me sorprendería si C # obtiene muchos más dígitos que eso.
ShreevatsaR
100

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

METRO = [1 1]
    [1 0] 

luego

fib ( n ) = M n 1,2

Elevar matrices a potencias usando multiplicaciones repetidas no es muy eficiente.

Dos enfoques para la exponenciación de matrices son dividir y conquistar, lo que produce M n en O ( ln n ) pasos, o descomposición de valores propios, que es tiempo constante, pero puede introducir errores debido a la precisión limitada de coma 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 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 en Λ 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, puede ver a dónde va a ir esto.

Resolver 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]

Invertir U usando

UN    = [ab]
      [ discos compactos ]
=>
A -1 = (1 / | A |) [d -b]
                   [-ca]

entonces U -1 viene 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]

       = M 

Entonces el control de cordura se mantiene.

Ahora tenemos todo lo que necesitamos para calcular M n 1,2 :

M n = U Λ n U -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) -1n 1n 1       Φ nn ]
              [Φ nn       Φ n -1n -1 ]

entonces

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

Lo cual concuerda con la fórmula dada en otra parte.

Se puede derivar de una relación de recurrencia, pero en ingeniería computacional y simulación calcular los autovalores y autovectores de matrices grandes es una actividad importante, ya que da estabilidad y armónicos de sistemas de ecuaciones, además de permitir elevar matrices a altas potencias de manera eficiente.

Pete Kirkham
fuente
+1 - Cosas increíbles, como siempre. ¿Qué usaste para componerlo? ¿Látex?
duffymo
Está copiado y pegado del libro de Álgebra de Gilbert Strang, o de otro buen libro de Álgebra lineal.
alinsoar
1
@alinsoar no fue 'copia pegada', pero se hizo como un ejercicio para comprobar que todavía podía recordar mi línea, con alguna referencia a las notas del curso de Open University y wikipedia.
Pete Kirkham
Tomé el curso de Álgebra L con Gilbert Strang, y ahí era idéntico. Por cierto, el problema de expresar la recursividad a través de la descomposición matricial es clásico y se puede encontrar en cualquier buen libro de texto / curso.
alinsoar
56

Si desea el número exacto (que es un "bignum", en lugar de un int / float), me temo que

¡Es imposible!

Como se indicó anteriormente, la fórmula para los números de Fibonacci es:

fib n = piso (phi n / √5 + 1 / 2 )

fib n ~ = phi n / √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 * const + const

es O ( n )

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 más bajos de la respuesta, entonces es posible calcular en tiempo sub-lineal usando el método de exponenciación matricial.

yairchu
fuente
2
@yairchu: Permítanme reformular esto, si lo entiendo correctamente. En teoría, calcular fib_n requiere calcular n dígitos, por lo que para cualquier n arbitrario tomará O (n) tiempo. Sin embargo, si fib_n <sizeof (largo tiempo), entonces podemos calcular fib_n en O (log n) tiempo desde la arquitectura de la máquina está proporcionando un mecanismo paralelo de ajuste de los bits. (Por ejemplo, int i = -1; requiere la configuración de 32 bits, pero en una máquina de 32 bits todos los 32 bits se pueden configurar en tiempo constante.
Sumit
7
@Sumit: si solo desea admitir resultados que se ajusten a 32 bits, también puede tener una tabla de búsqueda para estos primeros 48 resultados de la serie. Eso es obviamente O (1), pero: Hacer un análisis de O grande para un N limitado es una tontería, ya que siempre se puede incorporar cualquier cosa en el factor constante. Entonces mi respuesta se refiere a la entrada ilimitada.
yairchu
1
@yairchu: ¿Podrías demostrar tu lógica para un ejemplo conocido, como la O(n*log n)clasificación basada en la comparación de una secuencia de nnúmeros donde cada número tiene O(log n)dígitos?
jfs
1
Esto es correcto o incorrecto dependiendo de lo que pretenda que signifique "tiempo". Para ordenar (o buscar tablas hash), "tiempo" significa el número de comparaciones. En la pregunta podría significar operaciones aritméticas. En esta respuesta, se entiende que significa algo así como operaciones con dígitos.
Paul Hankin
4
Los enteros tendrán una representación finita en la base sqrt (2), pero solo será cero en los dígitos impares, es decir, equivalente a la base 2. Si alguno de los dígitos impares en la base sqrt (2) es distinto de cero, tienes un número irracional . Un caso en el que es posible que desee phi base es en los ADC al convertir señales continuas en analógicas. Afaik esta es la aplicación "industrial" de phi base, donde se usa para reducir el granulado grueso al redondear la señal. Personalmente, sin embargo, utilicé codificaciones base phi y fibonacci como una forma notablemente conveniente de trabajar con las representaciones de Fibonacci anyon del grupo de trenzas.
sábado,
34

Uno de los ejercicios en SICP trata sobre esto, que tiene la respuesta descrita aquí.

En el estilo imperativo, el programa se vería algo así como

Función  Fib ( cuenta )
     a ← 1
     b ← 0
     p ← 0
     q ← 1

    While  count > 0 Do 
        If Even ( count ) Entonces 
             pp ² + q ²
              q ← 2 pq + q ²
              countcount ÷ 2 De lo
         contrario 
             abq + aq + ap 
             bbp + aq 
             countcount - 1
         End If 
    Finalizar mientras

    Retorno  b 
Fin Función
Nietzche-jou
fuente
aquí hay una implementación en Python (para usar con el twistedmarco).
jfs
"Si par (cuenta) entonces" debería ser "Si impar (cuenta) entonces"
Monirul Islam Milon
@MonirulIslamMilon if even(count)tiene razón. La secuencia comienza con cero (el número cero de Fibonacci es cero): 0,1,1,2,3,5,8,13, ...
jfs
Comentario tardío, pero las variables py a se sobrescriben antes de usarse para calcular q y b. Para evitar este problema, calcule previamente los términos y cambie el orden de las asignaciones pyq: | qq = q · q | q = 2 · p · q + qq | p = p · p + qq | ... | aq = a · q | a = b · q + aq + a · p | b = b · p + aq | .
rcgldr
24

También puede hacerlo exponenciando una matriz de números enteros. Si tienes la matriz

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

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

EDITAR: Por supuesto, dependiendo del tipo de respuesta que desee, es posible que pueda salirse con la suya con un algoritmo de tiempo constante. Como muestran las otras fórmulas, el nnúmero de Fibonacci crece exponencialmente con n. Incluso con enteros sin signo de 64 bits, solo necesitará una tabla de búsqueda de 94 entradas para cubrir todo el rango.

SEGUNDA EDICIÓN: Hacer la matriz exponencial con una descomposición propia primero es exactamente equivalente a la solución de JDunkerly a continuación. Los valores propios de esta matriz son (1 + sqrt(5))/2y (1 - sqrt(5))/2.

Pastoso
fuente
3
Utilice la descomposición propia de M para calcular M ^ n de manera eficiente.
Pete Kirkham
1
El método propuesto está bien para cálculos en números enteros (probablemente con aritmética larga). El enfoque con descomposición propia no es interesante: si no necesita cálculos de números enteros, utilice la fórmula de la respuesta de Jason.
Konstantin Tenzin
1
@Konstantin La fórmula de la respuesta de Jason es el resultado de la descomposición propia, por lo que te estás contradiciendo.
Pete Kirkham
@Pete Kirkham Esa fórmula se puede obtener por varios métodos: ecuación de características, descomposición propia, prueba por inducción. No estoy seguro, esa descomposición propia es la más fácil. En cualquier caso, es bien conocido y es más fácil de usar de inmediato
Konstantin Tenzin
5

Wikipedia tiene una solución de formato cerrado http://en.wikipedia.org/wiki/Fibonacci_number

O en c #:

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }
JDunkerley
fuente
2
Puede evitar la necesidad de calcular a dos exponenciales utilizando el hecho de que |1 - phi|^n / sqrt(5) < 1/2when nes un número entero no negativo.
Jason
No sabía que el ajuste siempre había usado la otra forma, pero esa es una buena optimización
JDunkerley
1
Aproximación del resultado de la solución correcta implica la multiplicación de matrices.
cerkiewny
4

Para los realmente grandes, esta función recursiva funciona. Utiliza las siguientes ecuaciones:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

Necesita una biblioteca que le permita trabajar con números enteros grandes. Utilizo la biblioteca BigInteger de https://mattmccutchen.net/bigint/ .

Comience con una serie de números de Fibonacci. Use fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3, etc. En este ejemplo, uso una matriz de los primeros 501 (contando 0). Puede encontrar los primeros 500 números de Fibonacci distintos de cero aquí: http://home.hiwaay.net/~jalison/Fib500.html . Se necesita un poco de edición para ponerlo en el formato correcto, pero eso no es demasiado difícil.

Luego puede encontrar cualquier número de Fibonacci usando esta función (en C):

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

He probado esto para el número 25.000 de Fibonacci y similares.

usuario3137939
fuente
Este código no es tan eficiente. Imagina que la matriz fibs [] es solo de tamaño 10 y llamas Fib (101). Fib (101) llama Fib (51) y Fib (50). Fib (51) llama Fib (26) y Fib (25). Fib (50) llama Fib (25) y Fib (24). Entonces Fib (25) se llamó dos veces, lo cual es un desperdicio. Incluso con fibs de hasta 500, tendrá el mismo problema con Fib (100000).
Eyal
3

Aquí está mi versión recursiva que recurre log (n) veces. Creo que es más fácil de leer en forma recursiva:

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

Funciona porque puede calcular fib(n),fib(n-1)usando fib(n-1),fib(n-2)si n es impar y si n es par, puede calcular fib(n),fib(n-1)usando fib(n/2),fib(n/2-1).

El caso base y el caso extraño son simples. Para derivar el caso par, comience con a, b, c como valores de fibonacci consecutivos (por ejemplo, 8,5,3) y escríbalos en una matriz, con a = b + c. Darse cuenta:

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

A partir de eso, vemos que una matriz de los primeros tres números de Fibonacci, multiplicada por una matriz de tres números de Fibonacci consecutivos, es igual a la siguiente. Entonces sabemos que:

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

Entonces:

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

Simplificar el lado derecho conduce al caso par.

Eyal
fuente
Quiero enfatizar aquí que desea calcular F (2n) y F (2n + 1) en función de F (n) y F (n-1). No indicó lo que quiere hacer.
alinsoar
1

usando R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765
George Dontas
fuente
1

La aritmética de punto fijo es inexacta. El código C # de Jason da una respuesta incorrecta para n = 71 (308061521170130 en lugar de 308061521170129) y más.

Para obtener una respuesta correcta, use un sistema de álgebra computacional. Sympy es una biblioteca de este tipo para Python. Hay una consola interactiva en http://live.sympy.org/ . Copiar y pegar esta función

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Entonces calcula

>>> f(10)
55

>>> f(71)
308061521170129

Es posible que desee intentar inspeccionar phi.

Coronel Panic
fuente
1

Aparte del ajuste mediante enfoques matemáticos, una de las mejores soluciones óptimas (creo) es usar un diccionario para evitar cálculos repetitivos.

import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

Comenzamos con un diccionario trivial (los dos primeros valores de la secuencia de Fibonacci) y agregando constantemente valores de Fibonacci al diccionario.

Tomó alrededor de 0,7 segundos para los primeros 100000 valores de Fibonacci (Intel Xeon CPU E5-2680 a 2,70 GHz, 16 GB de RAM, sistema operativo Windows 10-64 bit)

bilalsamioguz
fuente
Sin embargo, esto es en tiempo lineal, la pregunta pregunta específicamente cómo lograr el tiempo sublineal (lo cual es posible usando una especie de solución de forma cerrada).
Romeo Valentin
0

ver el algoritmo divide y vencerás aquí

El enlace tiene un pseudocódigo para la exponenciación de la matriz mencionada en algunas de las otras respuestas para esta pregunta.

Chinmay Lokesh
fuente
0

Puedes usar la extraña ecuación de raíz cuadrada para obtener una respuesta exacta. La razón es que $ \ sqrt (5) $ cae al final, solo tiene que realizar un seguimiento de los coeficientes con su propio formato de multiplicación.

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55
Él
fuente
0

Aquí hay una línea que calcula F (n), usando números enteros de tamaño O (n), en operaciones aritméticas O (log n):

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Usar números enteros de tamaño O (n) es razonable, ya que es comparable al tamaño de la respuesta.

Para entender esto, sea phi la proporción áurea (la solución más grande de x ^ 2 = x + 1) y F (n) sea el n-ésimo número de Fibonacci, donde F (0) = 0, F (1) = F (2) = 1

Ahora, phi ^ n = F (n-1) + F (n) phi.

Prueba por inducción: phi ^ 1 = 0 + 1 * phi = F (0) + F (1) phi. Y si phi ^ n = F (n-1) + F (n) phi, entonces phi ^ (n + 1) = F (n-1) phi + F (n) phi ^ 2 = F (n-1) phi + F (n) (phi + 1) = F (n) + (F (n) + F (n-1)) phi = F (n) + F (n + 1) phi. El único paso complicado en este cálculo es el que reemplaza phi ^ 2 por (1 + phi), que sigue porque phi es la proporción áurea.

También los números de la forma (a + b * phi), donde a, b son números enteros, se cierran mediante multiplicación.

Prueba: (p0 + p1 * phi) (q0 + q1 * phi) = p0q0 + (p0q1 + q1p0) phi + p1q1 * phi ^ 2 = p0q0 + (p0q1 + q1p0) phi + p1q1 * (phi + 1) = ( p0q0 + p1q1) + (p0q1 + q1p0 + p1q1) * phi.

Usando esta representación, se puede calcular phi ^ n en operaciones de números enteros O (log n) usando exponenciación al elevar al cuadrado. El resultado será F (n-1) + F (n) phi, del cual se puede leer el n-ésimo número de Fibonacci.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Tenga en cuenta que la mayoría de este código es una función estándar de exponenciación al cuadrado.

Para llegar al principio de una sola línea que inicia esta respuesta, se puede notar que al representar phi por un entero lo suficientemente grande X, se puede realizar (a+b*phi)(c+d*phi)como la operación de entero (a+bX)(c+dX) modulo (X^2-X-1). Entonces la powfunción puede ser reemplazada por la powfunción estándar de Python (que convenientemente incluye un tercer argumento zque calcula el módulo de resultado z. El Xelegido es 2<<i.

Paul Hankin
fuente
0

Me he encontrado con algunos de los métodos para calcular Fibonacci con una complejidad de tiempo eficiente, los siguientes son algunos de ellos:

Método 1 - Programación dinámica Ahora, aquí la subestructura se conoce comúnmente, por lo tanto, iré directamente a la solución:

static int fib(int n) 
{ 
int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
int i; 

f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
}

Una versión optimizada para el espacio de lo anterior se puede hacer de la siguiente manera:

static int fib(int n) 
 { 
    int a = 0, b = 1, c; 
    if (n == 0) 
        return a; 
    for (int i = 2; i <= n; i++) 
    { 
        c = a + b; 
        a = b; 
        b = c; 
    } 
    return b; 
} 

Método 2- (usando el poder de la matriz {{1,1}, {1,0}})

Este es un O (n) que se basa en el hecho de que si multiplicamos n veces la matriz M = {{1,1}, {1,0}} a sí misma (en otras palabras, calculamos la potencia (M, n)), entonces obtenemos el (n + 1) número de Fibonacci como el elemento en la fila y columna (0, 0) en la matriz resultante. Esta solución tendría O (n) tiempo.

La representación matricial da la siguiente expresión cerrada para los números de Fibonacci: fibonaccimatrix

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

/*multiplies 2 matrices F and M of size 2*2, and 
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/*function that calculates F[][] raise to the power n and puts the 
result in F[][]*/
static void power(int F[][], int n) 
{ 
int i; 
int M[][] = new int[][]{{1,1},{1,0}}; 

// n - 1 times multiply the matrix to {{1,0},{0,1}} 
for (i = 2; i <= n; i++) 
    multiply(F, M); 
} 

Esto se puede optimizar para trabajar en complejidad de tiempo O (Logn). Podemos hacer multiplicaciones recursivas para obtener potencia (M, n) en el método anterior.

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

static void multiply(int F[][], int M[][]) 
{ 
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

static void power(int F[][], int n) 
{ 
if( n == 0 || n == 1) 
  return; 
int M[][] = new int[][]{{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
   multiply(F, M); 
} 

Método 3 (tiempo O (log n)) A continuación se muestra una fórmula de recurrencia más interesante que se puede usar para encontrar el número n de Fibonacci en el tiempo O (log n).

Si n es par, entonces k = n / 2: F (n) = [2 * F (k-1) + F (k)] * F (k)

Si n es impar, entonces k = (n + 1) / 2 F (n) = F (k) * F (k) + F (k-1) * F (k-1) ¿Cómo funciona esta fórmula? La fórmula se puede derivar de la ecuación matricial anterior. fibonaccimatrix

Tomando determinante en ambos lados, obtenemos (-1) n = Fn + 1Fn-1 - Fn2 Además, dado que AnAm = An + m para cualquier matriz cuadrada A, se pueden derivar las siguientes identidades (se obtienen de dos coeficientes diferentes de el producto de matriz)

FmFn + Fm-1Fn-1 = Fm + n-1

Al poner n = n + 1,

FmFn + 1 + Fm-1Fn = Fm + n

Poniendo m = n

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn + 1) Fn = (2Fn-1 + Fn) Fn (Fuente: Wiki)

Para que la fórmula sea probada, simplemente necesitamos hacer lo siguiente Si n es par, podemos poner k = n / 2 Si n es impar, podemos poner k = (n + 1) / 2

public static int fib(int n) 
{ 

    if (n == 0) 
        return 0; 

    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    // If fib(n) is already computed 
    if (f[n] != 0) 
        return f[n]; 

    int k = (n & 1) == 1? (n + 1) / 2 
                        : n / 2; 

    // Applyting above formula [See value 
    // n&1 is 1 if n is odd, else 0. 
    f[n] = (n & 1) == 1? (fib(k) * fib(k) +  
                    fib(k - 1) * fib(k - 1)) 
                   : (2 * fib(k - 1) + fib(k))  
                   * fib(k); 

    return f[n]; 
} 

Método 4: uso de una fórmula En este método, implementamos directamente la fórmula para el enésimo término de la serie de Fibonacci. Tiempo O (1) Espacio O (1) Fn = {[(√5 + 1) / 2] ^ n} / √5

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n)  
                    / Math.sqrt(5)); 
} 

Referencia: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

el alquimista
fuente
0

Primero debemos notar que los números de Fibonacci (F(n))crecen muy rápido con ny no se pueden representar en 64 bits para nmás de 93. Entonces, un programa para calcularlos para talesn necesidades debe usar mecanismos adicionales para operar en estos números grandes. Ahora, considerando solo el recuento de operaciones (de gran número), el algoritmo para calcularlas secuencialmente requerirá un número lineal de operaciones.

Podemos beneficiarnos de la siguiente identidad sobre los números de Fibonacci:

F(2m) = 2*F(m)*F(m+1) − (F(m))^2

F(2m+1) = (F(m))^2 + (F(m+1))^2

(un símbolo como A ^ 2 denota el cuadrado de A).

Entonces, si conocemos F(m)y F(m+1), podemos calcular directamente F(2m)y F(2m+1).

Considere la representación binaria de n. Observe que comenzando con x = 1, podemos hacer x = nduplicando iterativamente y posiblemente agregando 1 a x. Esto se puede hacer iterando sobre los bits de ny verificando si es 0 o 1.

La idea es que podamos mantenernos F(x)sincronizados con x. En cada una de esas iteraciones, a medida que duplicamos xy posiblemente agregamos 1 x, también podemos calcular el nuevo valor de F(x)usar el valor anterior de F(x)y F(x+1), con las ecuaciones anteriores.

Dado que el número de iteraciones será logarítmico en n, las operaciones totales (números grandes) también son logarítmicas en n.

Para obtener más detalles, consulte la sección "Algoritmo mejorado" de este artículo .

Nitin Verma
fuente