Fibonacci-Zahlen

[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.