Fibonacci, eine 7. Variante

[dizzy]

Zum Artikel Fibonacci in 6 Versionen ließe sich noch die folgende formelbasierte Version hinzufügen:

Delphi-Quellcode:

function Fib(k: Integer): Int64;
const
  sqt5inv =  0.447213595499957; // 1/sqrt(5)
  phi     =  1.618033988749895;
  nphiinv = -0.618033988749895;
begin
  result := Round(sqt5inv * (IntPower(phi, k)-IntPower(nphiinv, k)));
end;

Sie ist ähnlich der bereits vorhandenen, und nutzt den Zusammenhang der Fibonacci-Reihe mit dem goldenen Schnitt aus. Dieses Verfahren geht auf Binet zurück, und wird in dem Wikipedia-Artikel "Goldener Schnitt" beschrieben, sowie auf der von Hagen verlinkten Seite in ähnlicher Form.

Die o.g. Variante ist bis k=68 exakt. Mehr Genauigkeit ließe sich mit besseren Konstanten, und höher aufgelöster Gleitpunktarithmetik erzielen. Prinzipiell ist dieses Verfahren unendlich exakt, erfordert dann aber auch unendliche Genauigkeit.
Leider wird der Fehler bereits merkbar, bevor die Grenze von Int64 erreicht ist, was insbesondere auf die Potentierung zurückzuführen ist, die den in den Konstanten vorhandenen Fehler sehr verstärkt. Aber immerhin ein, wie ich finde, mathematisch sehr eleganter Weg einer expliziten Formel für die Fibonacci-Reihe, und Beispiel für die zum Teil echt irren Zusammenhänge in der Mathematik

[edit=Matze]Dieses Thema reicht nicht ganz aus, um in die Code-Library aufgenommen zu werden. MfG, Matze[/edit]