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 :D

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

[negaH]

Hi Fabian,

diese Funktion

Delphi-Quellcode:

procedure NFibonacci(var R: Integer; N: Cardinal);
var
  T,E,F: Integer;
  Mask: Cardinal;
begin
  if N = 0 then
  begin
    NSet(R, 0);
    Exit;
  end;
  NSet(F, 1);
  Mask := 1 shl Log2(N);
  while Mask > 1 do
  begin
         // PHI = golden ratio
          // Square (E + F*PHI)
          // (E, F) := (E² + F², 2EF + F²)
        NAdd(T, F, E);        // F + E
        NSqr(E);              // E²
        NSqr(T);              // (F + E)²
        NSqr(F);              // F²
        NSub(T, E);           // (F + E)² - E² = 2EF + F²
        // above trick exchange 2EF multiplication by faster Squaring T² + one addition -E²
        NAdd(E, F);           // E² + F²
        if N and Mask <> 0 then
        begin
          // Multiply (E + F*PHI) by PHI
          // (E, F) := (F, E + F)
          NSwp(T, E);
          NAdd(T, E);
        end;
        NSwp(T, F);
        Mask := Mask shr 1;
  // Here, E + F*PHI = PHI^N, thus (E,F) = (F[N-1],F[N])
  end;
  NSwp(F, R);
end;

arbeitet ebenfalls mit dem Golden Schnitt. Ich habe mal die Kommentierungen aus meinem Original mit eingefügt.
Für die Genauigkeit mit Double oder Extended ist deine Funktion das Effizienteste, aber bei immer größer werdenden Zahlen wird das immer ineffizienter. Zb. die IntPower() Funktion wird das Verfahren enorm ausbremsen. Wenn du in meinem Code ganz genau hinschaust so wird Iterativ in Ln2(N) Schritten ebenfalls eine Exponentation durchgeführt, aber eben von so spezieller Form das in jedem Schritt nur Quadrierungen und Additionen mit dem vorherigen Zwischenresultat durchgeführt werden. Nach meinem Wissenstand besitzt dieses Verfahren die beste Komplexität und Performance durch die Anwendung von nur Quadrierung als langsamste Operation. Quadrierungen sind 1.5 mal schneller als eine Multiplikation mit gleichgroßen Zahlen.

Also im Grunde rechnet diese Funktion PHI^N aus, wobei PHI der Goldene Schnitt ist, man potenziert PHI.
Nun PHI^N = E + F*PHI und (E,F) = (Fib[N-1], Fib[N]) -> Fib[N] = n'te Fibonacci Zahl.

Gruß Hagen

[dizzy]

Ich hatte hinter dieser Version schon leise eine geniale Zerlegung der Potenzierung vermutet. Das wäre auch der Punkt an dem ich intuitiv als erstes angesetzt hätte, wenn es drum ginge es noch weiter zu verfeinern. Danke dir für die Erläuterungen! Für solche mathematische Kniffe bin ich doch immer zu haben :)