63 lines
1.5 KiB
ObjectPascal
63 lines
1.5 KiB
ObjectPascal
program Fibonacci_console;
|
|
|
|
{$mode objfpc}{$H+}
|
|
|
|
uses SysUtils;
|
|
|
|
function Fibonacci( n : word) : uint64;
|
|
{
|
|
Starts with the pair F[0],F[1]. At each iteration, uses the doubling formulae
|
|
to pass from F[k],F[k+1] to F[2k],F[2k+1]. If the current bit of n (starting
|
|
from the high end) is 1, there is a further step to F[2k+1],F[2k+2].
|
|
}
|
|
var
|
|
marker, half_n : word;
|
|
f, g : uint64; // pair of consecutive Fibonacci numbers
|
|
t, u : uint64; // -----"-----
|
|
begin
|
|
// The values of F[0], F[1], F[2] are assumed to be known
|
|
case n of
|
|
0 : result := 0;
|
|
1, 2 : result := 1;
|
|
else begin
|
|
half_n := n shr 1;
|
|
marker := 1;
|
|
while marker <= half_n do marker := marker shl 1;
|
|
|
|
// First time: current bit is 1 by construction,
|
|
// so go straight from F[0],F[1] to F[1],F[2].
|
|
f := 1; // = F[1]
|
|
g := 1; // = F[2]
|
|
marker := marker shr 1;
|
|
|
|
while marker > 1 do begin
|
|
t := f*(2*g - f);
|
|
u := f*f + g*g;
|
|
if (n and marker = 0) then begin
|
|
f := t;
|
|
g := u;
|
|
end
|
|
else begin
|
|
f := u;
|
|
g := t + u;
|
|
end;
|
|
marker := marker shr 1;
|
|
end;
|
|
|
|
// Last time: we need only one of the pair.
|
|
if (n and marker = 0) then
|
|
result := f*(2*g - f)
|
|
else
|
|
result := f*f + g*g;
|
|
end; // end else (i.e. n > 2)
|
|
end; // end case
|
|
end;
|
|
|
|
// Main program
|
|
var
|
|
n : word;
|
|
begin
|
|
for n := 0 to 93 do
|
|
WriteLn( SysUtils.Format( 'F[%2u] = %20u', [n, Fibonacci(n)]));
|
|
end.
|