Haciendo que Fibonacci sea más rápido [duplicar]

Si necesita calcular n los números de fibonacci muy frecuentemente sugiero usar la respuesta de amalsom.

Pero si desea calcular un número de fibonacci muy grande, se quedará sin memoria porque está almacenando todos los números de fibonacci más pequeños. El siguiente pseudocódigo solo mantiene los dos últimos números de fibonacci en memoria, es decir, requiere mucha menos memoria:

fibonacci(n) {
    if n = 0: return 0;
    if n = 1: return 1;
    a = 0;
    b = 1;
    for i from 2 to n: {
        sum = a + b;
        a = b;
        b = sum;
    }
    return b;
}

Análisis
Esto puede calcular números de fibonacci muy altos con memoria bastante baja consumo: Tenemos O(n) tiempo como el bucle se repite n-1 veces. La complejidad del espacio también es interesante: El enésimo número de fibonacci tiene una longitud de O (n), que se puede mostrar fácilmente:
F _n n-1
Lo que significa que el n-ésimo número de fibonacci es a lo sumo el doble de grande que su predecesor. Duplicar un número en binario es equivalente con un solo desplazamiento a la izquierda, lo que aumenta el número de bits necesarios en uno. Por lo que representa la enésima el número de fibonacci toma como máximo el espacio O(n). Tenemos como máximo tres números sucesivos de fibonacci en la memoria que hacen que O(n) + O(n-1) + O(n-2) = O (n) consumo total de espacio. En contraste con esto, el algoritmo de memoización siempre mantiene los primeros n números de fibonacci en la memoria, lo que hace que O(n) + O(n-1) + O(n-2) + ... + O(1) = O (n^2) consumo de espacio.

Entonces, ¿de qué manera se debe usar?
La única razón para mantener todos los números de fibonacci más bajos en la memoria es si necesita números de fibonacci con mucha frecuencia. Se trata de equilibrar el tiempo con el consumo de memoria.

Aléjese de la recursión de Fibonacci y use las identidades

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

Esto le permite calcular (F(m+1), F(m)) en términos de (F(k+1), F(k)) para k la mitad del tamaño de m. Escrito iterativamente con algún desplazamiento de bits para la división por 2, esto debería darle la velocidad teórica O(log n) de exponenciación por cuadratura mientras se mantiene completamente dentro de la aritmética de enteros. (Bueno, O (log n) operaciones aritméticas. Dado que trabajará con números con aproximadamente n bits, no será O (log n) tiempo una vez que se ve obligado a cambiar a una gran biblioteca de enteros. Después de F (50), desbordará el tipo de datos entero, que solo sube a 2^(31).)

(Disculpas por no recordar Java lo suficientemente bien como para implementar esto en Java; cualquiera que quiera es libre de editarlo.)

• Fibonacci (0) = 0
• Fibonacci(1) = 1
• Fibonacci ( n) = Fibonacci(n - 1) + Fibonacci(n - 2), cuando n > = 2

Generalmente hay 2 maneras de calcular el número de Fibonacci:

1. Recursión :

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     } else {
       return getFibonacci(n - 1) + getFibonacci(n - 2);
     }
   }
   

   Esta forma es intuitiva y fácil de entender, mientras que debido a que no reutiliza el número de Fibonacci calculado, la complejidad del tiempo es de O(2^n), pero no almacena el resultado calculado, por lo que ahorra mucho espacio, en realidad la complejidad del espacio es O(1).

2. Programación Dinámica:

   public long getFibonacci(long n) {
     long[] f = new long[(int)(n + 1)];
     f[0] = 0;
     f[1] = 1;
     for(int i=2;i<=n;i++) {
       f[i] = f[i - 1] + f[i - 2];
     }
     return f[(int)n];
   }
   

   Este Memoization forma calculó los números de Fibonacci y reutilizarlos cuando calcule el siguiente. La complejidad temporal es bastante buena, que es O(n), mientras que la complejidad espacial es O(n). Investiguemos si se puede optimizar la complejidad del espacio... Dado que {[7] } solo requiere f(i - 1) y f(i - 2), no es necesario almacenar todos los Fibonacci calculados numero.

   La implementación más eficiente es:

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     }
     long x = 0, y = 1;
     long ans;
     for(int i=2;i<=n;i++) {
       ans = x + y;
       x = y;
       y = ans;
     }
     return ans;
   }
   

   Con complejidad de tiempo O(n), y complejidad de espacio O(1).

Añadido: Dado que el número de Fibonacci aumenta increíblemente rápido, long solo puede manejar menos de 100 números de Fibonacci. En Java, podemos usar BigInteger para almacenar más números de Fibonacci.

Precomputa un gran número de resultados fib(n) y guárdalos como una tabla de búsqueda dentro de tu algoritmo. Bam,"velocidad" libre

Ahora, si necesita calcular fib(101) y ya tiene fibs 0 a 100 almacenados, esto es como tratar de calcular fib(1).

Es probable que esto no sea lo que esta tarea está buscando, pero es una estrategia completamente legítima y básicamente la idea de almacenamiento en caché extraída más lejos de ejecutar el algoritmo. Si sabe que es probable que esté computando el primero 100 fibs a menudo y usted necesita hacerlo realmente realmente rápido, no hay nada más rápido que O (1). Así que calcular esos valores totalmente fuera de banda y almacenarlos para que puedan ser buscados más tarde.

Por supuesto, los valores de caché a medida que los calcula también :) La computación duplicada es un desperdicio.

Aquí se corta el código con un enfoque iterativo en lugar de recursión.

ejemplo de Salida:

Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 5,718 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 0 milliseconds

Algunas piezas de resultados se omiten con ... para una mejor vista.

fragmento de Código:

public class CachedFibonacci {
    private static Map<BigDecimal, BigDecimal> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<>();
        previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
        previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
    }

    public static BigDecimal getFibonacciOf(long number) {
        if (0 == number) {
            return BigDecimal.ZERO;
        } else if (1 == number) {
            return BigDecimal.ONE;
        } else {
            if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
                return previousValuesHolder.get(BigDecimal.valueOf(number));
            } else {
                BigDecimal olderValue = BigDecimal.ONE,
                        oldValue = BigDecimal.ONE,
                        newValue = BigDecimal.ONE;

                for (int i = 3; i <= number; i++) {
                    newValue = oldValue.add(olderValue);
                    olderValue = oldValue;
                    oldValue = newValue;
                }
                previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
                return newValue;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("Enter n: ");
            long inputNumber = scanner.nextLong();
            if (inputNumber >= 0) {
                long beginTime = System.currentTimeMillis();
                BigDecimal fibo = getFibonacciOf(inputNumber);
                long endTime = System.currentTimeMillis();
                long delta = endTime - beginTime;

                System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds\n", inputNumber, fibo, delta);
            } else {
                System.err.println("You must enter number > 0");
                System.out.println("try, enter number again, please:");
                break;
            }
        }
    }
}

Este enfoque se ejecuta mucho más rápido que la versión recursiva.

En tal situación, la solución iterativa tiende a ser un poco más rápida, porque cada la llamada al método recursivo toma una cierta cantidad de tiempo del procesador. En principio, es es posible que un compilador inteligente evite las llamadas a métodos recursivos si siguen patrones, pero la mayoría de los compiladores no hacen eso. Desde ese punto de vista, una iterativa solución es preferible.

Después de haber seguido un enfoque similar hace algún tiempo, me acabo de dar cuenta de que hay otra optimización que puedes hacer.

Si conoce dos respuestas consecutivas grandes, puede usar esto como punto de partida. Por ejemplo, si usted sabe F(100) y F(101), a continuación, el cálculo de F(104) es aproximadamente como difícil (*) como el cálculo de los F(4) basado en F(0) y F(1).

Calcular iterativamente hacia arriba es tan eficiente en el cálculo como hacer lo mismo usando la recursión en caché, pero usa menos memoria.

Habiendo hecho algunas sumas, también me he dado cuenta de que, para cualquier z < n:

F(n)=F(z) * F(n-z) + F(z-1) * F(n-z-1)

Si n es impar, y elige z=(n+1)/2, entonces esto se reduce a

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

Me parece que usted debe ser capaz de utilizar esto por un método que todavía tengo que encontrar, que usted debe ser capaz de utilizar la información anterior para encontrar F (n) en el número de operaciones igual a:

El número de bits en n duplicaciones (según lo anterior) + el número de 1 bits en n adiciones; en el caso de 104, esto sería (7 bits, 3 '1' bits) = 14 multiplicaciones (cuadrantes), 10 adiciones.

( * ) suponiendo sumando dos números toma el mismo tiempo, irrelevante del tamaño de los dos números.

Aquí hay una manera de demostrarlo en O (log n ) (como el bucle se ejecuta log n veces):

/* 
 * Fast doubling method
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    https://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static long getFibonacci(int n) {
    long a = 0;
    long b = 1;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        long d = a * ((b<<1) - a);
        long e = (a*a) + (b*b);
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            long c = a+b;
            a = b;
            b = c;
        }
    }
    return a;
}

Estoy asumiendo aquí (como es convencional) que una operación de multiplicar / sumar / lo que sea es tiempo constante independientemente del número de bits, es decir, que se utilizará un tipo de datos de longitud fija.

Esta página explica varios métodos de los cuales este es el más rápido. Simplemente lo traduje lejos de usar BigInteger para legibilidad. Aquí está la versión BigInteger:

/* 
 * Fast doubling method.
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    http://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static BigInteger getFibonacci(int n) {
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        BigInteger d = a.multiply(b.shiftLeft(1).subtract(a));
        BigInteger e = a.multiply(a).add(b.multiply(b));
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
    }
    return a;
}