AGB  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Fibonacci in 6 Versionen

Ein Thema von glkgereon · begonnen am 13. Apr 2005 · letzter Beitrag vom 26. Feb 2009
Antwort Antwort
Foren-Tage 2017
DIE Konferenz für Delphi-Entwickler mit vielen Vorträgen und ganztägigen Workshops, veranstaltet u.A. von der Delphi-PRAXiS und Embarcadero.
21.-23. September 2017 in Hamburg · Mehr Infos unter forentage.de.
Benutzerbild von glkgereon
glkgereon

Registriert seit: 16. Mär 2004
2.287 Beiträge
 
#1

Fibonacci in 6 Versionen

  Alt 13. Apr 2005, 17:00
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 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]
»Unlösbare Probleme sind in der Regel schwierig...«
  Mit Zitat antworten Zitat
Benutzerbild von fkerber
fkerber
(CodeLib-Manager)
Online

Registriert seit: 9. Jul 2003
Ort: Ensdorf
6.698 Beiträge
 
Delphi XE Professional
 
#2

Re: Fibonacci in 6 Versionen

  Alt 26. Feb 2009, 17:58
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;
Frederic Kerber
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:13 Uhr.
Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2017 by Daniel R. Wolf