Fibonacci, eine 7. Variante

[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