Fibonacci in 6 Versionen

[glkgereon]

Hi!

In einer angeregten Disskussion über verschiegene Algorithmen zur Errechnung einer bestimmten Fibonacci-Zahl kamen folgende 6 Lösungen heraus:
- Iterativ
- Rekursiv
- Formel
- Assembler
- Hagen 1
- Hagen 2

Die iterative Lösung
Autor: glkgereon
Kommentar: Recht gute Performance, gut zu verstehen
Geschwindigkeit:
25000 16ms
50000 47ms
75000 108ms

Delphi-Quellcode:

function Fibonacci_Iterativ(Index: Integer):Integer;
var i:Integer;
  Last, New: Integer;
begin
  NSet(Result,1);
  NSet(New,1);
  for i:=2 to Index do
  begin
    Last:=Result;
    Result:=New;
    NAdd(New,Result,Last);
  end;
end;

Die Rekursive Lösung
Autor: leddl
Kommentar: deutlich langsamer, sehr gut zu verstehen
Geschwindigkeit:
30 16ms
35 156ms
40 1750ms

Delphi-Quellcode:

function Fibonacci_Rekursiv(Index : Integer) : Int64;
begin
  case Index of
    1, 2 : Result := 1;
    else Result := Fibonacci_Rekursiv(Index-2) + Fibonacci_Rekursiv(Index-1);
  end;
end;

Die Formel-Lösung
Autor: Elite
Kommentar: kompliziert zu verstehen, ab 85 Rundungsfehler
Geschwindigkeit:
85 0ms

Delphi-Quellcode:

function Fibonacci_Formel(Index : Integer) : Int64;
begin
  result := round((1/sqrt(5))*(power((1+sqrt(5))/2, index-1)-power((1-sqrt(5))/2,index-1)));
end;

Die Assembler-Lösung
Autor: Chimaira
Kommentar: flott, leider nur bis 46, da Speicherüberlauf
Geschwindigkeit:
46 0ms

Delphi-Quellcode:

function Fibonacci_Asm(von: Integer): Integer;
  asm
    push eax
    push ebx
    push ecx
    push edx
    mov ecx, von
    mov eax, 1
    mov ebx, 0
    cmp ecx, 2
    jbe @@endoffib
    sub ecx, 1
    @@startLoop:
    mov edx, ebx
    mov ebx, eax
    add eax, edx
    sub ecx, 1
    jnz @@startLoop
    @@endoffib:
    mov result, eax
    pop edx
    pop ecx
    pop ebx
    pop eax
end;

Die Hagen-Lösung 1
Autor: negaH
Kommentar: schnell, und für riesige Zahlen, aber kompliziert
Geschwindigkeit:
500.000 31ms
1.000.000 93ms
5.000.000 515ms

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
    Mask := Mask shr 1;
    NAdd(T, F, E);
    NSqr(E);
    NSqr(T);
    NSqr(F);
    NSub(T, E);
    NAdd(E, F);
    if N and Mask <> 0 then
    begin
      NSwp(T, E);
      NAdd(T, E);
    end;
    NSwp(T, F);
  end;
  NSwp(F, R);
end;

Die Hagen-Lösung 2
Autor: negaH
Kommentar: superschnell

Delphi-Quellcode:

function Fibonacci_Hagen2(N: Byte): Int64;

function Log2(A: Cardinal): Cardinal; register;
  asm
    BSR EAX,EAX
end;

var
  E,F,T,S: Int64;
  M: Byte;
begin
  M := 1 shl Log2(N);
  F := 1;
  E := 0;
  while M > 1 do
  begin
    M := M shr 1;
    T := E * F;
    F := F * F;
    E := E * E + F;
    T := T + T + F;
    if N and M <> 0 then
    begin
      S := E;
      E := T;
      T := T + S;
    end;
    S := T;
    T := F;
    F := S;
  end;
  Result := F;
end;

Zusammenfassung:

Geschwindigkeit im Überblick(in ms):

Code:

Algo      ||  10       |  20       |  50       |  92       |  100      |  1000    |  10000

Iterativ  ||  0,003953 |  0,006155 |  0,013375 |  0,022969 |  0,024531 |  0,24155 |  3,7625

Rekursiv  ||  0,002609 |  0,113329 |           |           |           |          |

Formel    ||  0,002235 |  0,002265 |  0,002297 |           |           |          |

Assembler ||  0,001686 |  0,001717 |           |           |           |          |

Hagen 1   ||  0,003828 |  0,004421 |  0,005172 |  0,005795 |  0,005811 |  0,00953 |  0,092

Hagen 2   ||  0,001843 |  0,001906 |  0,001983 |  0,002062 |           |          |

Für die normale Anwendung ist Hagens zweite Lösung am besten / schnellsten, für große Zahlen seine Erste.
Will man jedoch den Quellcode verstehen, so sollte man bei kleinen Zahlen < 35 auf die Rekursive, bei großen Zahlen auf die Iterative zurückgreifen.

Bemerkungen:
Die Tests wurden auf folgendem System gemacht: AMD 2600, 768 MB DDR RAM, Windows 2000
Die Zahlen müssen folgendermaßen gelesen werden: X Y ms "für die X'te Fibonaccizahl brauch dieser Algorithmus Y Millisekunden."

für alle Varianten ausser der Iterativen und der Hagen1 empfehle ich einen Abfang zu hoher bzw zu niediger Zahlen.

Delphi-Quellcode:

if N < 2 then raise Exception.Create('Fibonacci(N), N must be > 1');
if N > 92 then raise Exception.Create('Fibonacci(N),N must be < 93');

Hagens und meine (die Iterative Lösung) brauchen den im DEC von Hagen Reddmann enthaltenen Typ IInteger sowie die zugehörigen Funktionen. Mit diesem sind sehr große Zahlen möglich.

Es folgte noch eine Ergänzung von negaH:

Zitat:

Zitat von negaH

Naja alternativ gibts ja noch die ganz schnelle Variante. N kann je bei Int64 nur bis 92 gehen.

Delphi-Quellcode:

function FibX(N: Byte): Int64;
const
  nFib: array[0..92] of Int64 =
    (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
     6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
     1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
     102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903,
     2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
     53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879,
     956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723,
     17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994,
     190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657,
     2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221,
     23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088,
     259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931,
     1779979416004714189,  2880067194370816120, 4660046610375530309, 7540113804746346429);
begin
  if N > 92 then raise Exception.Create('N must be < 93');
  Result := nFib[N]; 
end;

Und hier findet man eine Beschreibung zu dem Algo. den ich in meiner Lib benutzt habe:
http://www.mcs.surrey.ac.uk/Personal...ula.html#exact

Gruß hagen

[edit=flomei]formatiert und korrigiert. Sollten noch Verbesserungs- / Änderungswünsche bestehen bitte eine PN an mich senden. Mfg, flomei[/edit]
[edit=Matze]Code formatiert. Mfg, Matze[/edit]
[edit=Dax]Kleiner Fehler korrigiert. bedah, Dax[/edit]

[fkerber]

Codewalker stellt eine weitere rekursive, aber endrekursive, Variante vor. Die rekursive Variante ist deutlich langsamer als die iterative Lösung. Grund ist, dass die Funktion nicht endrekursiv ist. Das bedeutet, dass kein Zwischenergebnis errechnet werden kann, sondern die Rekursionstiefe doppelt exponentiell wächst.

Eine endrekursive Variante ist deutlich speicherschonendner und vor allem schneller:

Delphi-Quellcode:

function Fibonacci_Rekursiv2(Index : Integer) : Int64;
  function Fibonacci_Rekursiv_Help(f1,f2,n: Integer): Integer;
    begin
      if n = 0 then
        Result:=f1
      else 
        Result:=Fibonacci_Rekursiv_Help(f2,f1+f2,n-1);
    end;
begin
  case Index of
    1, 2 : Result := 1;
    else Result := Fibonacci_Rekursiv_Help(0,1,Index);
  end;
end;