Fibonacci-Zahlen

Die Fibonacci-Zahlen sind eine festgelegte Folge von positiven ganzen Zahlen und wurden um ca. 1200 von Leonardo Fibonacci (Leonardo von Pisa) entdeckt. Ursprünglich dienten sie ihm dazu, das Wachstum einer Kaninchen population zu beschreiben.

Definition der Fibonacci-Zahlen

Die Folge ist rekursiv definiert durch:

f(0) = 1
f(1) = 1
f(n+2) = f(n) + f(n+1)

Das bedeutet,

dass die ersten beiden Zahlen als eins festgelegt sind
dass folgende Zahlen durch Summieren der beiden jeweils vorangehenden erhalten werden.

Daraus ergibt sich die Folge zu:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Manchmal werden als Startwerte auch 0 und 1 genommen, es ergibt sich damit die um eine Stelle verschobene Fibonacci-Folge

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Formel von Binet

Will man die Fibonacci-Zahl für ein großes n berechnen, so ist das mit dem angegebenen Bildungsgesetz recht umständlich, weil man zunächst alle vorhergehenden Fibonacci-Zahlen berechnen muss. Wünschenswert wäre deshalb eine geschlossene Formel, mit der man eine Fibonacci-Zahl direkt - ohne Kenntnis der vorhergehenden Zahlen - berechnen kann.

Tatsächlich hat der französische Mathematiker Jacques-Philippe-Marie Binet bereits 1843 eine solche geschlosssene Darstellung angegeben:

$f(n)={\frac {1}{\sqrt {5}}}(a^{n+1}-b^{n+1})\ mit\ a={\frac {1}{2}}(1+{\sqrt {5}})\ und\ b={\frac {1}{2}}(1-{\sqrt {5}})$

Diese Formel ist bekannt als Formel von Binet.

Näherungsformel für große n

Für große Werte von n kann man den Ausdruck bⁿ⁺¹=-0,618033989 ⁿ⁺¹ gegenüber dem Ausdruck aⁿ⁺¹=1,618033989ⁿ⁺¹ vernachlässigen. Dann erhält man die Näherungsformel

$f(n)={\frac {1}{\sqrt {5}}}a^{n+1}={\frac {1}{\sqrt {5}}}\cdot ({\frac {1}{2}}(1+{\sqrt {5}}))^{n+1}\approx 0,223606798\cdot 3,236067977^{n+1}$

Verwandtschaft mit dem Goldenen Schnitt

Wie von Johannes Kepler festgestellt wurde, nähert sich der Quotient zweier aufeinander folgender Glieder f(n+1)/f(n) dem Goldenen Schnitt an.

Dies kann man sehr einfach einsehen, wenn man die obige Näherungsformel für große n benutzt:

${\frac {f(n+1)}{f(n)}}=a={\frac {1}{2}}(1+{\sqrt {5}})$

Computerprogramm

Wie sieht ein Programm aus, das die Fibonacci-Zahlen ausrechnet?

Sub 
  a = 0
  b = 1
  For x = 1 To 100
    Print a
    Print b
    a = a + b
    b = a + b
  Next x
End Sub

Dieses Programm berechnet die ersten 200 Fibonacci-Zahlen. Genauer die Fibonacci-Zahlen F(0) bis F(199). Die Variable a enthält immer die Fibonacci-Zahlen mit geradem Index (0, 2, 4, ...) und b die mit ungeradem (1, 3, 5, ...).

Dieses Beispiel hat eine sinnvolle Laufzeit zum Berechnen der ersten 200 Fibonacci-Zahlen, allerdings tritt bei diesem Beispiel die rekursive Definition der Fibonacci-Folge nicht so stark in den Vordergrund, wie beim nächsten Beispiel:

function fibonacci(n)
  wenn n=0 gib 0 zurueck
  wenn n=1 gib 1 zurueck
   sonst
    gib ( fibonacci(n-1) + fibonacci(n-2) ) zurueck

main
  For x = 1 To 200
    a = fibonacci(x)
    Print a
  Next x

Dieses Beispiel gibt ebenfalls die ersten 200 Fibonacci-Zahlen aus, allerdings mit einer verheerenden Laufzeit:

Um z.B. fibonacci(3) zu berechnen, muss zunächst fibonacci(2) und fibonacci(1) berechnet werden. Dazu ruft das Programm die Funktion fibonacci(n) zweimal erneut auf(wurde jetzt schon insg. drei mal aufgerufen). Um fibonacci(2) zu berechnen muss nun zunächst fibonacci(1) und fibonacci(0) berechnet werden. Dazu werden zwei weitere rekursionen von fibonacci(n) gestartet, die aber beide sofort ein Ergebniss melden können: fibonacci(1) gibt 1 zurück und fibonacci(0) 0. Jetzt hat die laufende Funktion fibonacci(2) alle benötigten Angaben und kann nun 0+1=1 als Ergebnis melden. Am Anfang wurde aber außerdem fibonacci(1) gestartet. Dieser Aufruf kann wieder ohne weitere Aufrufe ein Ergebnis melden: 1. Die Funktion wurde also 5 mal aufgerufen.

Um z.B. fibonacci(4) zu berechnen, muss zunächst fibonacci(3) und fibonacci(2) berechnet werden. Dazu ruft das Programm die Funktion fibonacci(n) zweimal erneut auf(wurde jetzt schon insg. drei mal aufgerufen). Wir wissen schon, dass 5 Aufrufe nötig sind, um fibonacci(3) zu berechnen. Der Aufruf von fibonacci(2) benötigt zwei weitere. Das ergibt zusammen 10 Aufrufe zum rekursiven Berechnen von fibonacci(4).

Eine erheblich bessere Laufzeit haben die folgenenden Python-Programme, die sich der Dynamische_Programmierung bedienen. Bereits berechnete Werte werden in einer Tabelle bereit gehalten, so dass jeder Wert nur genau einmal berechnet wird:

rekursiver Algorithmus:

 fibTable = [1, 1]
 def recfib(x):
    """Compute the Fibonacci number of a given number using recursion"""
    if len(fibTable) <= x:
       fibTable.append(recfib(x-2) + recfib(x-1))
    return fibTable[x]

iterativer Algorithmus:

 fibTable = [1, 1]
 def itfib(x):
    """Compute the Fibonacci number of a given number using iteration"""
    y = len(fibTable)
    if y >= x: return fibTable[x]
    while y <= x:
       fibTable.append(fibTable[y-1] + fibTable[y-2])
       y += 1
    return fibTable[x]

Hier noch ein lauffähiges Java-Programm, welches die rekursive Methode und eine sehr primitive (Aussage vom Autor des Programms) Methode (mithilfe vom Goldenen Schnitt - durch ungenaues rechnen kommt es hier aber ggf. zu Rundungsfehlern) nutzt, um bestimmte Fibonacci-Zahlen oder die ersten 40 zu bestimmen. Beim Berechen der ersten 40 Fibonacci-Zahlen wird die laufzeit in Millisekunden gemessen.

import java.io.*;
class Fibonacci
  {
  // Hilfsprozeduren fuer iterative Berechnung
  public static double sigma() {
   return (1+Math.sqrt(5))/2; }

  public static double sigmad() {
    return (1-Math.sqrt(5))/2;}

// Iterative Berechnung
  public static long itfib(int n) {
    if (n<0) return -1; // Fehlermeldung, wenn n<0
    // eigentliche Berechnung
    return (long)(( Math.pow(((1+Math.sqrt(5))/2), n) - Math.pow(((1-Math.sqrt(5))/2), n) ) / Math.sqrt(5)); }

// rekursive Berechnung
  public static long refib(int n) {
    if (n<0) return -1;  // Fehlermeldung, wenn n<0
    // eigentliche Berechnung
    if (n<=1) return n;  // F(0)=0, F(1)=1
    return refib(n-1) + refib (n-2); }

  // Routine um ein bestimmtes F(n) z berechnen
  public static void eine() throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int ganzzahl; // Variable, welche Fibonacci Zahl berechnet werden soll
    System.out.println("Bitte positive ganze Zahl n eingeben: ");
    ganzzahl = Integer.parseInt(in.readLine()); System.out.println();
    System.out.println("iterativ: F(" + ganzzahl + ") = " + itfib(ganzzahl));
    System.out.println("rekursiv: F(" + ganzzahl + ") = " + refib(ganzzahl)); }

  // Routine um F(0) bis F(40) zu berchnen und dabei die Zeit zu messen
  public static void alle() throws IOException {
    int i;
    long itestartTime, iteendTime, rekstartTime, rekendTime, wert;
    FileWriter fileWrit = new FileWriter("zeitdatei");
    PrintWriter printWrit = new PrintWriter(fileWrit);
    for (i=0;i<=40;i++) {
      itestartTime = System.currentTimeMillis();
      wert = refib(i);
      iteendTime = System.currentTimeMillis();
      System.out.println("rekursiv: F("+i+") = " + wert + " - Laufzeit: "+(iteendTime-itestartTime)+"mSek");
      rekstartTime = System.currentTimeMillis();
      wert = itfib(i);
      rekendTime = System.currentTimeMillis();
      System.out.println("iterativ: F("+i+") = " + wert + " - Laufzeit: "+(rekendTime-rekstartTime)+"mSek");
      /* Zeit in Datei ausgeben */
      printWrit.println("Zeit zur Berechnung von F("+i+"): iterativ: "+(iteendTime-itestartTime)+"mSek rekursiv: "+(rekendTime-rekstartTime)+"mSek"); }
      // next i
    /* Datei schliessen */
    printWrit.close(); }

  // Hauptprogramm
  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int auswahl; // Variable, welche Fibonacci Zahl berechnet werden soll
    System.out.println(" Fibonacci Zahlen by took - free software");
    System.out.println();
    System.out.println("Bitte wahlen Sie:");
    System.out.println("1 .. Berechne eine F.-Zahl auf beide Arten");
    System.out.println("2 .. Berechne F.-Zahlen von 0 bis 40 (Zeit in Files)");
    auswahl = Integer.parseInt(in.readLine());
    if (auswahl==1) {eine();}
     else {alle();}
    } //Ende main
  }  //Ende Class

Um das Programm laufen zu lassen, benötigt man eine Java-Maschine. Falls du den Quellcode in einer Datei Namens "Fibonacci.java" gespeichert hast, geht das Starten dann so:

javac Fibonacci.java
java Fibonacci