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

Use the supplied pointer-to-record representation and allocate a fresh record:

PROCEDURE mkRat(n,d: INTEGER): rational;
VAR z: rational;
BEGIN
  ASSERT(d # 0);
  NEW(z); z.num := n; z.den := d;
  reduce(z);
  RETURN z
END mkRat;

The rational number constructor returns a value with positive denominator in lowest terms, using part (b). Zero is represented as

0/1

. Arithmetic below uses exact integers, or inputs whose intermediate values fit the chosen implementation; fixed-width overflow would otherwise invalidate exact arithmetic.

Solution

 0  0

Divide numerator and denominator by their positive greatest common divisor, then fix the sign:

PROCEDURE reduce(x: rational);
VAR g: INTEGER;
BEGIN
  ASSERT(x.den # 0);
  g := gcd(ABS(x.num),ABS(x.den));
  x.num := x.num DIV g; x.den := x.den DIV g;
  IF x.den < 0 THEN
    x.num := -x.num; x.den := -x.den
  END
END reduce;

The denominator condition ensures

g > 0

, including when the numerator is zero. Dividing both components by the same nonzero integer preserves the fraction, and the final simultaneous sign change preserves it again. The resulting numerator and denominator are coprime; for zero the denominator becomes one.

c

 0  0

Solution

 0  0

Use the ordinary fraction identities, returning fresh records rather than changing either argument:

PROCEDURE addRat(x,y: rational): rational;
BEGIN
  RETURN mkRat(x.num*y.den + y.num*x.den, x.den*y.den)
END addRat;

PROCEDURE mulRat(x,y: rational): rational;
BEGIN
  RETURN mkRat(x.num*y.num, x.den*y.den)
END mulRat;

PROCEDURE negRat(x: rational): rational;
BEGIN
  RETURN mkRat(-x.num,x.den)
END negRat;

Every result is reduced by mkRat. This preserves the representation invariant even if an input was initially unreduced, provided its denominator is nonzero. Aliasing between the arguments causes no problem because their fields are only read.

d

 0  0

Solution

 0  0

Represent

a + b 5

by the pair

(a, b)

in the quadratic field

Q (5)

. Its multiplication rule is

(a + b 5) (c + d 5) = (a c + 5 b d) + (a d + b c) 5 .

(1)

The constructor copies both rational components, so later reduction through another pointer cannot change the constructed value:

PROCEDURE mkIrr(r,i: rational): irrational;
VAR z: irrational;
BEGIN
  NEW(z);
  z.rat := mkRat(r.num,r.den);
  z.irr := mkRat(i.num,i.den);
  RETURN z
END mkIrr;

PROCEDURE addIrr(x,y: irrational): irrational;
BEGIN
  RETURN mkIrr(addRat(x.rat,y.rat),addRat(x.irr,y.irr))
END addIrr;

PROCEDURE mulIrr(x,y: irrational): irrational;
VAR r,i: rational;
BEGIN
  r := addRat(mulRat(x.rat,y.rat),
              mulRat(mkRat(5,1),mulRat(x.irr,y.irr)));
  i := addRat(mulRat(x.rat,y.irr),mulRat(x.irr,y.rat));
  RETURN mkIrr(r,i)
END mulIrr;

The representation includes rational values when the second coefficient is zero; the supplied type name does not require every stored value to be irrational.

e

 0  0

Solution

 0  0

First normalize fresh copies of the two components. The following output helpers print a reduced rational with no /1, suppress a zero radical term, and suppress a unit radical coefficient:

OutRat(q):
    Out.Int(q.num)
    if q.den != 1: Out.String("/"); Out.Int(q.den)

OutIrr(x):
    r = mkRat(x.rat.num,x.rat.den)
    b = mkRat(x.irr.num,x.irr.den)
    if b.num == 0:
        OutRat(r); return
    if r.num != 0: OutRat(r)
    if b.num < 0: Out.String("-")
    else if r.num != 0: Out.String("+")
    c = mkRat(abs(b.num),b.den)
    if c.num != c.den:
        OutRat(c); Out.String("*")
    Out.String("sqrt(5)")

Thus the examples print 1/2+1/2*sqrt(5) and 2; zero prints 0, and pure unit radicals print sqrt(5) or -sqrt(5). The positive-denominator invariant makes the coefficient sign test reliable. Input records are not mutated.

f

 0  0

Solution

 0  0

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.

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

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

f

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

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

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion