Fibonacci sequence: Difference between revisions
Added another Pascal solution (doubling, iterative)
(Added another Pascal solution (doubling, iterative)) |
|||
Line 10,415:
writeln(Fibo_BigInt(555))
>>>43516638122555047989641805373140394725407202037260729735885664398655775748034950972577909265605502785297675867877570
===Doubling (iterative)===
The Clojure solution gives a recursive version of the Fibonacci doubling algorithm. The code below is an iterative version, written in Free Pascal. The unsigned 64-bit integer type can hold Fibonacci numbers up to F[93].
<syntaxhighlight lang="pascal">
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.
</syntaxhighlight>
{{out}}
<pre>
F[ 0] = 0
F[ 1] = 1
F[ 2] = 1
F[ 3] = 2
F[ 4] = 3
F[ 5] = 5
F[ 6] = 8
F[ 7] = 13
[...]
F[90] = 2880067194370816120
F[91] = 4660046610375530309
F[92] = 7540113804746346429
F[93] = 12200160415121876738
</pre>
=={{header|PascalABC.NET}}==
| |||