Fibonacci-Zahlen

[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