 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-programming-resit/1/f/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming (resit) / 1 / f / Solution by

Codex  0 2026-10-31

Use Binet's formula entirely within

Q (5)

. Set

ϕ = (1/2, 1/2), ψ = (1/2, - 1/2), c = (0, 1/5) = 1/ 5 .

(1)

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 = ϕ^{i}

and

q = ψ^{i}

, so the printed value is exactly

F_{i}

. The irrational coefficient cancels algebraically, and the rational result is an integer. This prints $F_{0}, \dots, F_{n - 1}$ ; to use the convention

F_{1}, \dots, 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.

 Read the full article

 New to topics? Read the docs here!