Fibonacci Zahlen Struktogramm

[negaH]

Delphi-Quellcode:

function Fibonacci(N: Zahl): Zahl;
// Fibonacci mithilfe des Golden Ratio's PHI berechnen
// PHI = golden ratio
//           (E + F*PHI)²
// (E, F) := (E² + F², 2EF + F²)

var
  E,F,T,S: Zahl;
  Log2N: Zahl;
  Mask: Zahl;
begin
  if N = 0 then
  begin
    Result := 0;
    Exit;
  end
  F := 1;
  E := 0;
  Log2N := Log2(N);
  Mask := 2^LogN2;
  while Mask > 0 do
  begin
    T := F + E;
    E := E^2;
    T := T^2;
    F := F^2;
    T := T + E;
    E := E + F;

    if N and Mask <> 0 then
    begin
      S := T;
      T := E;
      E := S;  // swap T,E

      T := T + E;
    end;

    S := T;
    T := F;
    F := T;     // swap T,F

    Mask := Mask / 2;
  end;
  Result := F;
end;

Das ist ein Pseudocode der den effizientesten Fibonacci Algortihmus umschreibt. Insgesamt hat er die geringst mögliche Komplexität von exakt Log2(N) Iterarionsschritten, vergleiche das mal mit den allgemein üblichen rekusiven Funktionen

Gruß hagen