Esiste un modo migliore (prestazioni) per calcolare Fibonacci rispetto a questo?

Question

Ho fatto questo codice .. E ho bisogno di ottenere il meglio .. Ho davvero bisogno delle migliori prestazioni di calcolo dei numeri di Fibonacci .. per favore aiutatemi ..

Ho letto qualche codice di questo tipo di calcolo e Penso che ho avuto il meglio di loro ..

Avaliate questo per me .. plz ..

ps: e ho davvero bisogno del BigInteger .. io calcolare Fibonacci di numeri enormi

ps2: ho calcolato alcuni grandi numeri con questo algoritmo e ho ottenuto un ottimo tempo di risposta .. ma ho bisogno di sapere se potrebbe essere meglio

ps3: per eseguire questo codice è necessario utilizzare questo argomento VM -Xss16384k (STACKSIZE)

public class Fibonacci { 

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) }; 

    public static BigInteger fibonacci(long v) { 

     BigInteger fib = BigInteger.valueOf(0); 

     if (v == 1) { 

      fib = BigInteger.valueOf(1); 

     } else if (v == 0) { 

      fib = BigInteger.valueOf(0); 

     } else { 

      BigInteger v1 = fibonacci(v - 1); 
      BigInteger v2 = fibTmp[(int) (v - 2)]; 

      fib = v1.add(v2); 
     } 

     synchronized (fibTmp) { 

      if (fibTmp.length - 1 < v) 
       fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10)); 

      fibTmp[(int) v] = fib; 
     } 

     return fib; 
    } 
} 

Answer 1

L'implementazione non funziona per qualsiasi numero decente perché rende l'overflow dello stack .

Non vedo alcun motivo per utilizzare la ricorsività qui. La ricorsività è carina ma generalmente più pesante (dipende dalla lingua). Ecco un'implementazione di lavoro con un semplice for ciclo:

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE}; 
private static int maxCached = 1; 
public static BigInteger fibonacci(int v) { 
    if (fibTmp.length<=v) { 
     fibTmp = Arrays.copyOf(fibTmp, v*5/4); 
    } 
    for (; maxCached<v;) { 
     maxCached++; 
     BigInteger v1 = fibTmp[maxCached - 1]; 
     BigInteger v2 = fibTmp[maxCached - 2]; 
     fibTmp[maxCached] = v1.add(v2); 
    } 
    return fibTmp[v]; 
} 

Questo è un'implementazione diretta senza cercare un algoritmo Fibonacci efficiente in letteratura. Faresti meglio a cercarli.

Si noti inoltre che questa implementazione basata su cache è costosa in termini di memoria e ha senso solo se si chiama la funzione più volte.

Answer 2

Prima di tutto, si utilizza la ricorsione, che non è efficiente in termini di tempo e complessità dello spazio. Dovresti usare l'approccio iterativo.

Quindi, se la memoria extra o lo spazio non sono breaker e se le prestazioni sono davvero critiche, potresti voler precomporre tutti i numeri che vorresti calcolare in un secondo momento e memorizzarli in un array o sul tuo disco se è troppo per la tua memoria Più tardi puoi ottenere il valore in tempo costante.

Answer 3

Sì, c'è un modo migliore. Questo è un metodo testato log(n) e molto efficiente per calcolare un valore di Fibonacci con precisione arbitraria, dato un intero positivo come input. L'algoritmo è stato adattato da una soluzione a SICP s' exercise 1.19:

public static BigInteger fibonacci(int n) { 

    int count = n; 
    BigInteger tmpA, tmpP; 
    BigInteger a = BigInteger.ONE; 
    BigInteger b = BigInteger.ZERO; 
    BigInteger p = BigInteger.ZERO; 
    BigInteger q = BigInteger.ONE; 
    BigInteger two = new BigInteger("2"); 

    while (count != 0) { 

     if ((count & 1) == 0) { 
      tmpP = p.multiply(p).add(q.multiply(q)); 
      q = two.multiply(p.multiply(q)).add(q.multiply(q)); 
      p = tmpP; 
      count >>= 1; 
     } 

     else { 
      tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p))); 
      b = b.multiply(p).add(a.multiply(q)); 
      a = tmpA; 
      count--; 
     } 

    } 

    return b; 

} 

Nel capitolo legato del libro c'è una spiegazione di come funziona (scorrere verso il basso per esercitare 1.19), ed è precisato che:

Questo è un algoritmo intelligente per calcolare i numeri di Fibonacci in un numero logaritmico di passaggi ... Questo esercizio è stato suggerito da Joe Stoy, basato su un esempio di Kaldewaij, Anne. 1990. Programmazione: Derivazione di algoritmi.

Naturalmente, se gli stessi valori devono essere calcolati più e più volte, ulteriori guadagni prestazioni possono essere raggiunti da memoizing risultati che sono stati già calcolati, ad esempio utilizzando una mappa per memorizzare valori precedenti.