37 lines
828 B
ObjectPascal
37 lines
828 B
ObjectPascal
function fib(n: Int64): Int64;
|
|
|
|
type TFibMat = array[0..1] of array[0..1] of Int64;
|
|
|
|
function FibMatMul(a,b: TFibMat): TFibMat;
|
|
var i,j,k: integer;
|
|
tmp: TFibMat;
|
|
begin
|
|
for i := 0 to 1 do
|
|
for j := 0 to 1 do
|
|
begin
|
|
tmp[i,j] := 0;
|
|
for k := 0 to 1 do tmp[i,j] := tmp[i,j] + a[i,k] * b[k,j];
|
|
end;
|
|
FibMatMul := tmp;
|
|
end;
|
|
|
|
function FibMatExp(a: TFibMat; n: Int64): TFibmat;
|
|
begin
|
|
if n <= 1 then fibmatexp := a
|
|
else if (n mod 2 = 0) then FibMatExp := FibMatExp(FibMatMul(a,a), n div 2)
|
|
else if (n mod 2 = 1) then FibMatExp := FibMatMul(a, FibMatExp(FibMatMul(a,a), n div 2));
|
|
end;
|
|
|
|
var
|
|
matrix: TFibMat;
|
|
|
|
begin
|
|
matrix[0,0] := 1;
|
|
matrix[0,1] := 1;
|
|
matrix[1,0] := 1;
|
|
matrix[1,1] := 0;
|
|
if n > 1 then
|
|
matrix := fibmatexp(matrix,n-1);
|
|
fib := matrix[0,0];
|
|
end;
|