# Fibonacci Zahlen seeeehr schnell berechnen



## 0001001 (4. Sep 2008)

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 (4. Sep 2008)

Moivre-Binet Formel


----------



## SlaterB (4. Sep 2008)

> 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 (4. Sep 2008)

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 (4. Sep 2008)

0001001 hat gesagt.:
			
		

> 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 (4. Sep 2008)

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 (5. Sep 2008)

Landei hat gesagt.:
			
		

> 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
> 
> ...



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


----------



## SlaterB (5. Sep 2008)

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 (5. Sep 2008)

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 (6. Sep 2008)

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

}
```


----------

