(*------------------------------------------------------------------*)
(*
** Berechnung der Fibonacci-Zahlen
**
** Anfangswerte: 	fib(0) = 0; fib(1) = 1;
** Rekusionsformel: 	fib(n) = fib(n-1) + fib(n-2) fuer n >= 2
*)
(*------------------------------------------------------------------*)
(*
** Rekursive Version, sehr langsam!
*)
function fib_rec(n: integer): integer;
begin
    if n <= 1 then
        return n;
    else
        return fib_rec(n-1) + fib_rec(n-2);
    end;
end;
(*------------------------------------------------------------------*)
(*
** Iterative Version
*)
function fib_it(n: integer): integer;
var
    x, y, temp, i: integer;
begin
    if n <= 1 then 
	return n;
    end;
    x := 1; y := 0;
    for i := 2 to n do
        temp := x;
        x := x + y;
        y := temp;
    end;
    return x;
end;
(*-------------------------------------------------------*)
(*
** Schneller Potenzierungs-Algorithmus
** berechnet die n-te Potenz von x
*)
function power(x,n: integer): integer;
var
    k, pow: integer;
begin
    if n = 0 then 
	return 1; 
    end;
    pow := x;
    for k := bit_length(n)-2 to 0 by -1 do
        pow := pow * pow;
        if bit_test(n,k) then
            pow := pow * x;
        end;
    end;
    return pow;
end;
(*-------------------------------------------------------*)
(*
** Typ-Deklaration: ganzzahlige 2x2-Matrix
*)
type
    mat2x2 = record
        a11, a12, a21, a22: integer;
    end;
end;
(*-------------------------------------------------------*)
(*
** erzeugt Matrix mit den Eintraegen a11, a12, a21, a22.
*)
function mat_set(a11, a12, a21, a22: integer): mat2x2;
var
    A: mat2x2;
begin
    A.a11 := a11;
    A.a12 := a12;
    A.a21 := a21;
    A.a22 := a22;
    return A;
end;
(*-------------------------------------------------------*)
(*
** erzeugt Einheitsmatrix
*)
function mat_unit(): mat2x2;
begin
    return mat_set(1,0,0,1);
end;
(*-------------------------------------------------------*)
(*
** Matrix-Multiplikation
*)
function mat_mult(A,B: mat2x2): mat2x2;
var
    C: mat2x2;
begin
    C.a11 := A.a11 * B.a11 + A.a12 * B.a21;
    C.a12 := A.a11 * B.a12 + A.a12 * B.a22;
    C.a21 := A.a21 * B.a11 + A.a22 * B.a21;
    C.a22 := A.a21 * B.a12 + A.a22 * B.a22;
    return C;
end;
(*-------------------------------------------------------*)
(*
** berechnet n-te Potenz der Matrix A mittels
** des schnellen Potenzierungs-Algorithmus
*)
function mat_power(A: mat2x2; n: integer): mat2x2;
var
    C: mat2x2;
    k: integer;
begin
    if n < 0 then
	writeln("exponent n must be nonnegative: ",n);
	halt(-1);
    end;
    if n = 0 then
	return mat_unit();
    end;
    C := A;
    for k := bit_length(n) - 2 to 0 by -1 do
        C := mat_mult(C,C);
        if bit_test(n,k) then
	    C := mat_mult(C,A);
	end;
    end;
    return C;
end;
(*-------------------------------------------------------*)
(*
** Berechnung der Fibonacci-Zahlen mit Matrix-Potenzierung
*)
function fib_mat(n: integer): integer;
var
    A: mat2x2;
begin
    A := mat_set(0,1,1,1);
    A := mat_power(A,n);
    return A.a12;
end;
(*-------------------------------------------------------*)
(*
** Optimierte Berechnung der Fibonacci-Zahlen mittels der Formeln
**      fib(2*n-1) = fib(n)**2 + fib(n-1)**2
**      fib(2*n)   = fib(n)**2 + 2*fib(n)*fib(n-1)
**
** Beispiel-Aufruf: fib(1000).
*)
function fib(n: integer): integer;
var
    k, x, y, xx, temp: integer;
begin
    if n <= 1 then return n end;
    x := 1; y := 0;
    for k := bit_length(n)-2 to 0 by -1 do
        xx := x*x;
        x := xx + 2*x*y;
        y := xx + y*y;
        if bit_test(n,k) then
            temp := x;
            x := x + y;
            y := temp;
        end;
    end;
    return x;
end.
(*-------------------------------------------------------*)
(*********************************************************)