timeline Fibonacci-Folge Rechner star

Wie wird die Fibonacci-Folge berechnet?

Die Fibonacci-Folge wird durch eine einfache Rekursion definiert: F(0) = 0, F(1) = 1, und jedes folgende Glied ist die Summe der beiden vorhergehenden, F(n) = F(n-1) + F(n-2). Diese eine Regel erzeugt 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… jede Zahl ist einfach die Summe der letzten beiden — das macht die Folge für das erste gute Dutzend Glieder leicht von Hand nachprüfbar.

Weit weniger offensichtlich ist, wie schnell die Zahlen wachsen. Bei F(30) liegt der Wert bereits über 800.000; bei F(100) ist es eine 21-stellige Zahl. Standard-64-Bit-Zahlentypen (die von den meisten Taschenrechnern und von gewöhnlichen JavaScript-Zahlen verwendet werden) verlieren stillschweigend an Genauigkeit, sobald eine Ganzzahl etwa 9 × 10^15 überschreitet — eine Schwelle, die Fibonacci um das 78. Glied herum erreicht. Ab diesem Punkt zeigt ein naiver Rechner ohne jede Warnung ein gerundetes, leicht falsches Ergebnis. Dieses Tool umgeht das vollständig, indem es jedes Glied mit BigInt-Arithmetik berechnet, die Ganzzahlen beliebiger Größe exakt darstellt, Ziffer für Ziffer, egal wie groß n wird — sodass F(100), F(500), sogar F(1000), bis zur letzten Ziffer präzise herauskommen.

Eine zweite bekannte Eigenschaft ist die Verbindung zum Goldenen Schnitt: Mit wachsendem n konvergiert das Verhältnis aufeinanderfolgender Glieder F(n)/F(n-1) gegen φ ≈ 1,6180339887…, dieselbe Konstante, die in den Proportionen eines regelmäßigen Fünfecks auftaucht und in Binets geschlossener Formel zur Berechnung von Fibonacci-Zahlen ohne Rekursion. Frühe Glieder nähern sich ihr nur grob an (3/2 = 1,5, 8/5 = 1,6), doch bereits um das 15. Glied herum ist das Verhältnis auf vier Dezimalstellen genau.

Was Sie wissen sollten

• Indexierungskonvention. Manche Quellen beginnen die Folge bei F(1) = F(2) = 1 statt bei F(0) = 0. Dieses Tool folgt der mathematischen Standardkonvention F(0) = 0 und F(1) = 1, wie sie auch in den meisten Lehrbüchern und Informatikkursen verwendet wird.
• Wachstumsrate. Jedes Glied ist etwa das 1,618-fache des vorhergehenden, sodass die Anzahl der Ziffern linear mit n wächst — F(1000) hat über 200 Ziffern, genau der Bereich, in dem Gleitkomma-Rechner versagen und BigInt erforderlich wird.
• Häufige Falle. Wird ein großer Fibonacci-Wert aus einer Tabellenkalkulation oder einem Rechner kopiert, der Standard-Gleitkommazahlen verwendet (etwa gewöhnliches JavaScript oder Excel), rundet dieser ab etwa dem 78. Glied stillschweigend die letzten Ziffern — sehr große Werte sollte man daher stets mit einem für beliebige Genauigkeit gebauten Tool gegenprüfen.
• Praktischer Nutzen. Über die reine Mathematik hinaus taucht die Folge in der Algorithmenanalyse auf (Fibonacci-Suche, Lehrbeispiele für dynamische Programmierung), bei der Beschreibung bestimmter natürlicher Wachstumsmuster sowie in den Retracement-Niveaus der finanztechnischen Analyse.