= Solution
Use <Binet's formula> entirely within $\mathbb Q(\sqrt5)$. Set
$$
\phi=(1/2,1/2),\quad\psi=(1/2,-1/2),\quad c=(0,1/5)=1/\sqrt5.
$$
Here pairs mean the rational and radical coefficients. An exact program using the preceding procedures is
``
z = mkRat(0,1); one = mkRat(1,1)
half = mkRat(1,2)
phi = mkIrr(half,half)
psi = mkIrr(half,negRat(half))
c = mkIrr(z,mkRat(1,5))
p = mkIrr(one,z); q = mkIrr(one,z)
for i = 0,...,n-1:
minusQ = mkIrr(negRat(q.rat),negRat(q.irr))
OutIrr(mulIrr(c,addIrr(p,minusQ)))
Out.Ln()
p = mulIrr(p,phi)
q = mulIrr(q,psi)
``
At iteration $i$, $p=\phi^i$ and $q=\psi^i$, so the printed value is exactly $F_i$. The irrational coefficient cancels algebraically, and the rational result is an integer. This prints \b[$F_0,\ldots,F_{n-1}$]; to use the convention $F_1,\ldots,F_n$, initialize `p=phi` and `q=psi`. There are $O(n)$ field operations, with growing arbitrary-precision arithmetic costs kept separate from that count.
Back to article page
