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