Fibonacci Zahlen seeeehr schnell berechnen

[0001001]

Hi,

vorweg: Ich weiß wie man die Fibonacci Zahlen berechnet

Ich versuche gerade einen möglichst schnellen Algorithmus zu entwerfen, die Fibonacci Zahlen zu berechnen. Ok fangen wir an.
Die Standard-Methode:

public static int fib(int n){		
	if (n <= 2){
		return 1;
	}
	else{
		return (fib(n-1) + fib(n-2));
	}
 }

Der Nachteil liegt auf der Hand: Für jedes n werden die Vorgängerwerte immer neu berechnet, was extrem ineffizient ist.

Memory-Methode (Quelle):

private static ArrayList<BigInteger> fibCache = new ArrayList<BigInteger>();
static {
      fibCache.add(BigInteger.ZERO);
      fibCache.add(BigInteger.ONE);
} 

public static BigInteger fib(int n) {
       if (n >= fibCache.size()) {
           fibCache.add(n, fib(n-1).add(fib(n-2)));
       }
       return fibCache.get(n);
}

Diese Methode ist wesentlich schneller, da sie die Vorgängerwerte nicht jedesmal neu berechnet. Nachteil ist allerdings, dass ab einer gewissen Fibonacci Zahl ( bei mir ca. f(1000000)) der schon auf 1,6 gb vergrößerte Java Heap Space überläuft.

Ein weiterer in Python geschriebener Algorithmus der sehr schnell sein soll ist hier zu finden: http://krenzel.info/?p=85
Den bekomm ich aber nicht nach Java portiert. Kann mir da jemand helfen?

Insgesamt meine Frage an euch:
Kennt jemand einen schnelleres Verfahren zur Berechnung der Fibonacci Zahlen als die beiden oben genannten?
Hat jemand Verbesserungsvorschläge zu den oben genannten Algorithmen?

 

[Wildcard]

Moivre-Binet Formel

 

[SlaterB]

> Nachteil ist allerdings, dass ab einer gewissen Fibonacci Zahl ( bei mir ca. f(1000000)) der schon auf 1,6 gb vergrößerte Java Heap Space überläuft.

vielleicht beide Verfahren kombinieren:
nur jede 1000te Zahl speichern bzw. zwei je hintereinander liegende,
senkt den Speicherbedarf auf 1.6 mb und die Berechnung ist immer noch 1000 mal schneller (statt 1000x1000 mal)

je größer die Zahlen, desto größer der Abstand bei der Speicherung und desto langsamer das Verfahren, falls verkraftbar

sofern es in diesem Fall eine fertige Formel gibt, ist das natürlich eher eine theoretische Überlegung

 

[0001001]

Die Moivre-Binet Formel hat den Nachteil, dass sie nicht genau rechnet, da man Wurzel(5) berechnen muss.

Die Idee von SlaterB finde ich gut. Mal testen.

Freue mich aber weiterhin über Optimierungsvorschläge.

 

[SchonWiederFred]

Freue mich aber weiterhin über Optimierungsvorschläge.

Wenn es nur um die Berechnung einer einzelnen Fibonacci-Zahl geht, dürfte folgendes am schnellsten sein:

public static BigInteger fibonacci(int n)
{
	BigInteger a = new BigInteger("0");
	BigInteger b = new BigInteger("1");
	while (--n > 0)
	{
		BigInteger c = a.add(b);
		a = b;
		b = c;
	}
	return b;
}

Und wenn Du die ersten n Fibonacci-Zahlen ausgeben willst, bau das println einfach mit ein:

public static void printFirstFibonacciNumbers(int n)
{
	BigInteger a = new BigInteger("0");
	BigInteger b = new BigInteger("1");
	while (--n >= 0)
	{
		System.out.println(b);
		BigInteger c = a.add(b);
		a = b;
		b = c;
	}
}

Falls Du allerdings völlig willkürlich irgendwelche Fibonacci-Zahlen berechnen willst (also keine Sequenz), dann fällt mir da auf Anhieb gerade nix vernünftiges ein.

 

[Landei]

Das ist laaange nicht die schnellste Methode. Es gibt dutzende Formeln zum "Abkürzen", etwa

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

Habe mal das Programm aus "Algorithmische Zahlentheorie" von Prof. O. Forster abgetippt, das solche Tricks benutzt. Schätze mal dagegen ist deine Variante lahm wie eine amputierte Ente...

   private final static BigInteger TWO = BigInteger.valueOf(2);

   public static BigInteger fib(int value) {
       BigInteger n = BigInteger.valueOf(value);
       if (n.compareTo(BigInteger.ONE) <= 0) {
           return n;
       }
       BigInteger x = BigInteger.ONE;
       BigInteger y = BigInteger.ZERO;

       for (int k = n.bitLength() - 2; k >= 0; k--) {
           BigInteger xx = x.pow(2);
           x = xx.add(TWO.multiply(x).multiply(y));
           y = xx.add(y.pow(2));
           if (n.testBit(k)) {
               BigInteger temp = x;
               x = x.add(y);
               y = temp;
           }
       }
       return x;
   }

 

[Guest]

Das ist laaange nicht die schnellste Methode. Es gibt dutzende Formeln zum "Abkürzen", etwa

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

Habe mal das Programm aus "Algorithmische Zahlentheorie" von Prof. O. Forster abgetippt, das solche Tricks benutzt. Schätze mal dagegen ist deine Variante lahm wie eine amputierte Ente...

   private final static BigInteger TWO = BigInteger.valueOf(2);

   public static BigInteger fib(int value) {
       BigInteger n = BigInteger.valueOf(value);
       if (n.compareTo(BigInteger.ONE) <= 0) {
           return n;
       }
       BigInteger x = BigInteger.ONE;
       BigInteger y = BigInteger.ZERO;

       for (int k = n.bitLength() - 2; k >= 0; k--) {
           BigInteger xx = x.pow(2);
           x = xx.add(TWO.multiply(x).multiply(y));
           y = xx.add(y.pow(2));
           if (n.testBit(k)) {
               BigInteger temp = x;
               x = x.add(y);
               y = temp;
           }
       }
       return x;
   }

Stimmt! Der Algorithmus ist wesentlich schneller. Leider verstehe ich nicht warum das funktioniert. Kann ich mir auch jede dazwischenliegende Fibonacci Zahl ausgeben lassen?

 

[SlaterB]

der Algorithmus ist gerade deswegen so schnell, weil so viele Zahlen übersprungen werden,
um die dazwischenliegenden auszugeben müsstest man die ja alle berechen,
das ist ein Widerspruch

warum F(2n) = F(n+1)^2 - F(n-1)^2 gilt steht auf irgendwelchen Seiten wie vielleicht Wikipedia als Beweis,
das muss man einmal durchrechnen, kann man nicht durch Anschauen 'verstehen'

edit: das angegebene Programm ist wohl noch ein anderes

 

[Landei]

Wenn du natürlich *alle* Zahlen ausgeben willst, ist die normale Berechnung natürlich OK, aber das war oben nicht gefragt. Habe nicht getestet, wie schnell es ist. Die Zeit für F(10000) war jedenfalls kaum meßbar.

Der Algorithmus verwendet zwei andere Formeln (eine für F(2n) und eine für F(2n+1)). Finden sich u.a. auf http://www.ijon.de/mathe/fibonacci/node2.html . Im Prinzip kann man die ganzen Fibo-Formeln einfach durch Einsetzen in die Binet-Formel beweisen, aber natürlich ist der Beweis "zu Fuß" interessanter...

Das Programm unter dem oben angegebenen Link (http://krenzel.info/?p=85) scheint übrigens so ähnlich wie meins zu arbeiten.

Da es auch eine Formel für F(3n) gibt, ist das Ende der Fahnenstange wohl noch nicht erreicht...

Übrigens gibt es einen einfachen Test, um festzustellen, ob eine gegebene Zahl eine Fibonacci-Zahl ist:
n ist eine Fibonacci-Zahl genau dann wenn entweder 5n²+4 oder 5n²-4 eine Quadratzahl ist (Gessel, 1972)

 

[Landei]

Hmmm, mit den Formeln für F(3n) bin ich sogar ein klein wenig langsamer. Sind wohl zuviele Multiplikationen ???:L

Trotzdem hier der Code, vielleicht kann man das noch optimieren:

import java.math.BigInteger;

/**
 *
 * @author Gronau
 */
public class Fibonacci3 {

    //solution[0] = F(n), solution[1] = F(n-1)
    private static void solve(int n, BigInteger[] solution) {
        switch(n) {
            case 1:   solution[0] = BigInteger.ONE;
                      solution[1] = BigInteger.ZERO;
                      return;
            case 2:   solution[0] = BigInteger.ONE;
                      solution[1] = BigInteger.ONE;
                      return;
            case 3:   solution[0] = BigInteger.valueOf(2);
                      solution[1] = BigInteger.ONE;
                      return;
        }
        int k = n / 3;
        solve(k, solution);
        BigInteger fk = solution[0];
        BigInteger fk_1 = solution[1];
        BigInteger fk1 = n % 3 == 0 ? null : fk.add(fk_1);
        BigInteger fk1_pow3 = n % 3 == 0 ? null : fk1.pow(3);
        BigInteger fk_pow2 = fk.pow(2);
        BigInteger fk_pow3 = fk_pow2.multiply(fk);
        switch(n % 3) {
            case 0 : if (k % 2 == 0) {
                        solution[0] = mult5(fk_pow3).add(mult3(fk));
                      } else {
                        solution[0] = mult5(fk_pow3).subtract(mult3(fk));
                      }
                     solution[1] = fk_pow3.add(mult3(fk_pow2).multiply(fk_1)).add(fk_1.pow(3));
                     return;
            case 1 : solution[0] = fk1_pow3.add(mult3(fk1).multiply(fk_pow2).subtract(fk_pow3));
                     if (k % 2 == 0) {
                       solution[1] = mult5(fk_pow3).add(mult3(fk));
                     } else {
                       solution[1] = mult5(fk_pow3).subtract(mult3(fk));
                     }
                     return;
            case 2 : solution[0] = fk1_pow3.add(mult3(fk1.pow(2)).multiply(fk)).add(fk_pow3);
                     solution[1] = fk1_pow3.add(mult3(fk1).multiply(fk_pow2).subtract(fk_pow3));
                     return;
        }
    }

    public static BigInteger fib(int n) {
        if (n < 2) {
            return BigInteger.valueOf(n);
        }
        //direct calculation if n divisible by 3
        //using F(3n) = 5 * F(n)^3 + 3*(-1)^n * F(n)
        if (n % 3 == 0) {
            int k = n / 3;
            BigInteger fk = fib(k);
            if (k % 2 == 0) {
                return mult5(fk.pow(3)).add(mult3(fk));
            } else {
                return mult5(fk.pow(3)).subtract(mult3(fk));
            }
        }
        BigInteger[] solution = new BigInteger[2];
        //special calculation if n is divisible by 4
        //using F(4n) = 4F(n)*F(n+1)*(F(n+1)^2+2*F(n) ^2) - 3*f(n)^2*(F(n)^2+2F(n+1)^2)
        if (n % 4 == 0) {
            int k = n / 4;
            solve(k, solution);
            BigInteger fk = solution[0];
            BigInteger fk1 = fk.add(solution[1]);
            BigInteger fk_2 = fk.pow(2);
            BigInteger fk1_2 = fk1.pow(2);
            return fk.shiftLeft(2).multiply(fk1).multiply(fk1_2.add(mult2(fk_2))).subtract(
                   mult3(fk_2).multiply(fk_2.add(mult2(fk1_2))));
        }
        solve(n, solution);
        return solution[0];
    }

    private static BigInteger mult2(BigInteger n) {
        return n.shiftLeft(1);
    }

    private static BigInteger mult3(BigInteger n) {
        return n.shiftLeft(1).add(n);
    }

    private static BigInteger mult5(BigInteger n) {
        return n.shiftLeft(2).add(n);
    }

}