Fibonacci-Zahlen

[glkgereon]

hi

hier ein function die einem die Index'te Fibonacci-Zahl liefert.

Delphi-Quellcode:

function Fibonacci1(Index: Integer):Int64;
var i:Integer;
    Last, New: Int64;
begin
  Result:=1;
  Last:=0;
  New:=1;
  for i:=2 to Index do
    begin
    Last:=Result;
    Result:=New;
    New:=Result + Last;
    end;
end;

Edit: ich hatte ne alte Version genommen :wall:
wieso merk ich das jetzt erst???? :wall:

[leddl]

Warum so kompliziert? :gruebel:

Delphi-Quellcode:

function fibonacci(Index : Integer) : Int64;
Begin
  Case Index of
    1, 2 : Result := 1;
    Else Result := fibonacci(Index-2) + fibonacci(Index-1);
  End;
End;

PS: Rekursion is was Feines! :mrgreen:

//Edit: Integer in Int64 geändert. :oops:

[glkgereon]

joa, haste recht.

ich find rekursiv immer bisschen schwerer nachzuvollziehen, und was schneller ist müsste man mal ausführlich testen.

aber tu deins mal auf Int64 umstellen ;)

[leddl]

Zitat:

Zitat von glkgereon

ich find rekursiv immer bisschen schwerer nachzuvollziehen

Ich benutz es auch zu selten, aber in dem Fall springt einen die Rekursion ja schon fast an. ;)

Zitat:

Zitat von glkgereon

aber tu deins mal auf Int64 umstellen ;)

*Hust* *Hust* schon passiert. :wall: Hatte ich nich drangedacht!

[rantanplan99]

Mal eine Notiz am Rande:

Erste Version mit for-Schleife:
+ Weniger Speicherverbrauch
+ schneller
- Nicht ganz so intuitiv

Zweite Version mit rekursion:
+ Ist intuitiv, leichter Verständlich
- Verbraucht mehr Speicher (Stack für Prozedur aufrufe)
- durch die Rekursion bedingter 'overhead' für Prozeduraufrufe und Rücksprung und dadurch etwas langsamer

Ich würde die erste Version bevorzugen, da sie etwas schneller ist.

rantanplan

[glkgereon]

nichts gegen leddl, aber:

*g*

auch wenn ich die argumente nur teilweise nachvollziehen kann...

[JasonDX]

@leddl: Die Umstellung auf int64 bringt dir relativ wenig, nachdem durch den rekusiven aufruf Zeit eher knapp ist als die größe des 32-Bit-Integers ;)

wenn mich nicht alles täuscht, gibts hier in der DP aber auch schon nen Fibonacci-code über asm! (Ich glaub von Illuminator war der....)

[leddl]

Ach le**t mich doch alle! :mrgreen: :zwinker:

Ich kenn mich mit den ganzen Gschichten auch nich so aus. Is nur so, daß ich Rekursionen um einiges verständlicher und übersichtlicher finde. (Und ich hab halt nunmal gerne Code, den ich auch nach längerer Zeit schnell wieder verstehe) Und außerdem bekommt man in der Uni ständig beigebracht, möglichst viel rekursiv zu programmieren... :gruebel:

Aber wurscht, ich beuge mich der Mehrheit! Werde aber dennoch weiterhin meine hübschen Rekursionen verwenden. :mrgreen:

[JasonDX]

Zitat:

Zitat von leddl

Is nur so, daß ich Rekursionen um einiges verständlicher und übersichtlicher finde. (Und ich hab halt nunmal gerne Code, den ich auch nach längerer Zeit schnell wieder verstehe) Und außerdem bekommt man in der Uni ständig beigebracht, möglichst viel rekursiv zu programmieren... :gruebel:

Passt auch so. Rekursiv ist einfacher zu verstehn ect., und die meisten Algorithmen (z.B. Heap- und Merge-Sort) haben log n Funktionsaufrufe.
Nachdem die Fibonacci-Funktion ein paar mehr hat (ws exponentiell), isses da nicht unbedingt rentabel ;)

[malo]

Nur mal so, aber was sind Fibonacci-Zahlen? :gruebel:

[alcaeus]

Zitat:

Zitat von malo

Nur mal so, aber was sind Fibonacci-Zahlen? :gruebel:

Guckst du: http://de.wikipedia.org/wiki/Fibonacci-Zahlen
Ich frag mich warum Daniel wohl den wiki-Button eingebaut hat ;)

Greetz
alcaeus

[Binärbaum]

Zitat:

Zitat von malo

Nur mal so, aber was sind Fibonacci-Zahlen? :gruebel:

Schau mal hier: Fibonacci-Zahlen

MfG
Binärbaum

[Jelly]

Ob for-Schleife oder rekursiv. Aber auf jeden Fall sollte das gleiche Ergebnis rauskommen. Tuts in diesem Fall aber nicht :mrgreen:
Also irgendwer hat sich da wohl vertan.

[BenjaminH]

So wie ich das sehe (experimentiert) ist das von Leddl richtig :thumb:

[Elite]

Zitat:

Zitat von Jelly

Aber auf jeden Fall sollte das gleiche Ergebnis rauskommen.

Das wär allerdings nicht schlecht. Mit dieser Funktion dürftest du aber auch das Gewünschte erreichen:

Delphi-Quellcode:

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

Keine Rekursion und keine Schleife, sondern reine Mathematik.


Edit: Diese Version geht davon aus, dass die Fibonacci-Zahlenreihenfolge bei 0 und nicht bei 1 beginnt. (Definitionssache je nach Problemstellung)

[leddl]

Hehe, da sieht man wieder, was Rekursion so alles bringen kann. Das Ergebnis kann - schon wenn man nur einen Blick auf den Code wirft - eigentlich nur richtig sein.
Und besser langsam und richtig, als schnell und falsch! ;)
Das Problem an glkgereon's Code ist, daß nach dem ersten Aufruf Last immer gleich Result ist, und somit Result immer einfach nur verdoppelt wird. Aber das ist eben in so ner Schleife nicht sofort zu erkennen. Aber das hatte mich heute schon einmal irritiert.

[Sharky]

So,

jetzt habt ihr den Thread so schön zerredet das die lieben Code-Manager sicher nicht mehr wissen was sie nun in die Code-Library aufnhemen sollen und was nicht :roll:
Herzlichen Glückwunsch

[JasonDX]

hier findet man das:

Delphi-Quellcode:

procedure Fibonacci(von: integer): int64;
var 
  alt, uralt: int64;
  i: integer; 
begin 
  alt := 0; 
  result := 1; 
  for i := 2 to von do begin 
    uralt := alt; 
    alt := result; 
    result := uralt + alt; 
  end; 
end;

und

Delphi-Quellcode:

procedure Fibonacci(von: integer): integer;
asm
    MOV EDX, von
    SUB EDX, 1 
    MOV EAX, 0  //alt 
    MOV EBX, 1  //neu 
    JZ @@end 
    @@1: 
    MOV ECX, EAX 
    MOV EAX, EBX 
    MOV EBX, EAX 
    ADD EBX, ECX 
    SUB EDX, 1 
    CMP EDX, 1 
    JAE @@1 
    @@end: 
    MOV result, EBX 
end;

@Elite: Ich weiß nicht mehr genau, aber wird die Formel nach ziemlich großen Zahlen nicht etwas ungenau? (Ich weiß bloß noch, dassma mal durch Annäherung was ähnliches rausgekriegt ham)
Und durch ein inc(Index) dürft das Problem mit Beginn bei 0 oder 1 geklärt sein ;)

@Sharky: Man kann ja alle 4 Versionen hinzufügen (Rekursiv, Iterativ, Iterativ ASM und Formel) :zwinker:

[glkgereon]

ok, also meins funzt jetzt auch.

ich werd, wenns recht is, die versionen in nem neuen thread nochmal reinstellen.

werd alle eigentlichen autoren nennen, und'n performance-test machen vorher.

das asm endet imho in ner endlosschleife....mein prog hängt sich dabei einfach auf...

[glkgereon]

irgendwie hängen die asm und die rekursive ziemlich!!!

oder mach ich was falsch?

irgendwie funkt das net :(

[leddl]

Kanns bei mir nich compilieren, deshalb kann ich nich viel dazu sagen, aber was meinst du mit "hängen"? Brauchts nur lange oder hängt sich das Programm auf? Also mein Code funktioniert bei mir einwandfrei und selbst mit etwas höheren Zahlen merkt man keinen Hänger...

[Binärbaum]

Zitat:

Zitat von glkgereon

irgendwie hängen die asm und die rekursive ziemlich!!!

oder mach ich was falsch?

irgendwie funkt das net :(

Bei der rekursiven Funktion kann das an der Rekursion liegen. Dadurch, das bei großen Zahlen die Funktion ziemlich oft rekursiv aufgerufen wird, kann es schon mal etwas länger dauern. Deswegen bevorzuge ich auch iterative Verfahren ;-)

MfG
Binärbaum

[glkgereon]

naja, also ab 50 etwa brauchs deutlich mehr als 1-2 sek....so lang das ich abgebrochen hab.

aber die asm-lösung auch :gruebel:

[leddl]

Ok, habs jetzt mal selbst getestet. Der rekursive Aufruf hinkt wirklich ab ca. 30 deutlichst hinterher. Wohl doch wirklich nich so gut. ;)

[Khabarakh]

Ist doch logisch:

Code:

 -> = ruft auf
5. Fibonacci-Zahl

Rekursiv:


 
               2
          3 ->
               1
     4 ->

          2

5 ->
          2

     3 ->

          1

iterativ:

 2+1 -> 3 -> 4 -> 5

Und das ist erst die fünfte :stupid: .

[Binärbaum]

Man könnte die rekursive Variante noch verbessern (d.h. schneller machen), wenn man die schon berechneten Zwischenergebnisse speichert. Allerdings hat man dadurch wieder mehr Overhead, sodass letztlich dieser wieder den Performance-Gewinn dämpft.

MfG
Binärbaum

[JasonDX]

ich hab den asm-code nochmal angeguckt

wenn ich die funktion einmal aufrufe, reicht das:

Delphi-Quellcode:

function fib(von: integer): integer; assembler;
asm
  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
end;

wenn ich sie in einer for-schleife aufruf, muss ich

Delphi-Quellcode:

//Das am anfang:
  push eax
  push ebx
  push ecx
  push edx

//und das am ende:
  pop edx
  pop ecx
  pop ebx
  pop eax

anhängen :?:


Edit: source ausgebessert

[negaH]

Hier mal ein Program von mir.

Gruß Hagen

[glkgereon]

würdest du event. auch den source veröffentlichen?

[BenjaminH]

[ot]@negaH Was wohl passiert wenn ich da -3 eingeb ;-) [/ot]
[Edit] Was ich eigentlich meine ist, das jede dieser funktionen vielleicht noch eine überprüfung zur gültigkeit des Indexes braucht
[Edit=2] Jetzt weiß ich was passiert :-( nach einiger Zeit war der PC nicht mehr ansprechbar

[glkgereon]

die asm lösung funzt net

die zahlen:

1, 1, 3, ... hää???

[DP-Maintenance]

Dieses Thema wurde von "Sharky" von "Neuen Beitrag zur Code-Library hinzufügen" nach "Object-Pascal / Delphi-Language" verschoben.
Bis das ganze durchdiskutiert und getestet wurde verschiebe ich den Thread mal hier her. Wenn ihr fertig seit kann ja einer die Zusammenfassung in die Code-Library setzten.

[negaH]

Zitat:

negaH Was wohl passiert wenn ich da -3 eingeb

er rechnet die 2^32 -1 -3 'te Fibonacci Zahl aus.

Gruß Hagen

[JasonDX]

Zitat:

Zitat von glkgereon

die asm lösung funzt net

die zahlen:

1, 1, 3, ... hää???

hab was vergessen :oops: (sub ecx, 1)

is ausgebessert und müsst jetzt funzen

[negaH]

Der Source ist aus meinem DEC Math Package, er benutzt die Methode mit dem Goldenen Schnitt und kann auch die Fibonacci Zahlen modulo berechnen. Deshalb sieht er erstmal ziemlich kompliziert aus, ist er aber ncht. Ich habe mal noch par Kommentare hinzugefügt.

Delphi-Quellcode:

procedure NFibonacci(var R: IInteger; N: Cardinal; const M: IInteger);
// R := Fib(N) mod M, if M <> nil
var
  T,E,F: IInteger;
  Mask: Cardinal;
  I: Integer;
begin
// Assertion, Pre Checks
  if M <> nil then
  begin
    I := NSgn(M, True);
    if I = 0 then NRaise_DivByZero;
    if I = 1 then
    begin
      NSet(R, 0);
      Exit;
    end;
  end;
  if N = 0 then
  begin
    NSet(R, 0);
    Exit;
  end;
// ab hier gehts los
  NSet(F, 1);
  Mask := 1 shl (DBitHigh(N) -1);
  if Mask > 0 then
  begin
    NSet(E, 0);
    if M <> nil then
    begin
  // wir wollen Modulo rechnen
      I := NLow(M) + 1;
      if I = NSize(M) then // M = 2^i
      begin
    // Modulus ist von der Form 2^i, man kann also auf Divisionen verzichten
        while Mask <> 0 do
        begin
          NAdd(T, F, E);  NCut(T, I);
          NSqr(E);        NCut(E, I);
          NSqr(T);        NCut(T, I);
          NSqr(F);        NCut(F, I);
          NSub(T, E);     NCut(T, I);
          NAdd(E, F);     NCut(E, I);
          if N and Mask <> 0 then
          begin
            NSwp(T, E);
            NAdd(T, E);   NCut(T, I);
          end;
          NSwp(T, F);
          Mask := Mask shr 1;
        end;
        NAddMod(F, M, M);  // correct sign
      end else
      begin
      // Modulus hat keine spezialle Form
      // montgomery version are always slower
        while Mask <> 0 do
        begin
          NAdd(T, F, E);
          NMod(T, M);
          NSqrMod(E, M);
          NSqrMod(T, M);
          NSqrMod(F, M);
          NSubMod(T, E, M);
          NAddMod(E, F, M);
          if N and Mask <> 0 then
          begin
            NSwp(T, E);
            NAddMod(T, E, M);
          end;
          NSwp(T, F);
          Mask := Mask shr 1;
        end;
      end;
    end else
// normale Berechnung ohne modulare Arithmetik, Golden Ratio,
// das ist der Code der im obigen Program ausgeführt wird.
      while Mask <> 0 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;
      end;
  // Here, E + F*PHI = PHI^N, thus (E,F) = (F[N-1],F[N])
  end;
  NSwp(F, R);
end;

Klar dürfte sein das ich nicht meine ganze Library hier als Source posten kann und will :-)
Wie man sieht benötigt obige Methode nur Ln2(IndexOf Fibonacci) Iterationsschritte und ist somit von der Komplexität der schnellste bekannte Fibonaci Algorithmus. Beispiel NFibonacci(F, 1024) würde die Schleife 10 mal durchlaufen. Für die 100.000'endste Fibonacci Zahl würde man also 18 Schleifendurchläufe benötigen.

Gruß Hagen

[Khabarakh]

So etwas ist einfach genial.
(Mist, ich finde keinen geeigneten Smilie :mrgreen: )

[negaH]

Und für alle die mal einen Vergleich zwischen Assembler und normalen Pascal anstellen wollen :-)

Delphi-Quellcode:

function Fib(N: Byte): Int64;

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

var
  E,F,T,S: Int64;
  M: Byte;
begin
  if N < 2 then
    raise Exception.Create('Fib(N), N must be > 1');
  if N > 92 then
    raise Exception.Create('Fib(N),N must be < 93');

  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; // E = Fib(N -1);
end;

Bevor man irgendwas in Assembler macht sollte man den Algorithmus optimieren.

Gruß hagen

[himitsu]

hab jetzt auch mal 'ne kleine Fibonacci-Function erstellt :engel:

- zusammen mit meiner TBigInt arbeitet sie schnomal bis Fibonacci(737)
(Cardinal bis 47. und Int64 bis 92.)

Delphi-Quellcode:

Function Fibonacci(Index: Integer): Int64;
  Var Next: Int64;

  Begin
    If Index < 0 Then Error(reInvalidOp);
    Result := 0;
    Next   := 1;
    While Index > 0 do Begin
      Swap8(Result, Next); 
      Inc(Result, Next);
      Dec(Index);
    End;
  End;

Function Fibonacci(Index: Integer): TBigInt;
  Var Next: TBigInt;

  Begin
    If Index < 0 Then Error(reInvalidOp);
    Result := 0;
    Next   := 1;
    While Index > 0 do Begin
      Swap(@Result, @Next, SizeOf(TBigInt));
      Result.Add(Next);
      Dec(Index);
    End;
  End;


// alle Fibonacci-Zahlen bis zur 737. Zahl benötigten auf meinem PCchen ~90 ms
Var i: TBigInt;
  i2: Integer;

For i2 := 0 to 737 do
  i := Fibonacci(i2);

die Prozeduren Swap8 und Swap machen im Grunde nichts anderes als die Werte zu vertauschen

Delphi-Quellcode:

Var Temp: Typ_of_SwapVariables;

Temp   := Result;
Result := Next;
Next   := Temp;

PS: mal 'ne Frage, warum gibt es 2. CodeLib-Einträge?
Code-Library -> Algorithmen -> Fibonacci in 6 Versionen
Code-Library -> Algorithmen -> Fibonacci

[schöni]

Hallo!

Habe das hier zu den Fibonacci Zahlen in der Informatik gefunden:

http://de.wikipedia.org/wiki/Fibonacci-Folge

http://www.ijon.de/mathe/fibonacci/index.html

http://mathe-kiste.de/fibonacci/inhalt.htm

Es gibt noch mehr. Habe in Google den Begriff "Fibonacci Zahlen" eingegeben, ohne die Anführungszeichen.