Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1

Use the remainder form of the Euclidean algorithm to compute the greatest common divisor, then divide both components of the fraction by it:

def Reduce(num: Int, den: Int): (Int, Int) = {
  require(0 <= num && num < den)
  var a = den
  var b = num
  while (b != 0) {
    val r = a % b
    a = b
    b = r
  }
  (num / a, den / a)
}

The loop invariant is

a > 0

b \geq 0

, and

g cd (a, b) = g cd (d e n, n u m)

. Initially it holds by symmetry of the greatest common divisor. For

b > 0

, the integer division identity

a = q b + r

, with

0 \leq r < b

, shows that

a, b

and

b, r

have exactly the same common integer divisors. Thus the update preserves the loop invariant. The loop variant is the nonnegative integer

b

, which strictly decreases on each iteration. At exit

b = 0

, so

a = g cd (d e n, n u m) > 0

. Dividing by

a

preserves the rational number and makes the returned components coprime. In particular, zero is returned as $(0, 1)$ . No multiplication is needed, and all remainders remain within the original nonnegative Int range.

b

 0  0

Solution

 0  0

For a positive remaining fraction

n / d

, the condition

1/ q \leq n / d

is equivalent to

q \geq d / n

. Since

1/ q

decreases as the positive integer

q

increases, choose $q = ⌈ d / n ⌉$ . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.

The remaining fraction is

\frac{n}{d} - \frac{1}{q} = \frac{n q - d}{d q} .

(1)

The defining inequalities

q - 1 < d / n \leq q

give

0 \leq n q - d < n

. Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.

c

 0  0

Solution

 0  0

Maintain an accumulated array of denominators and an exact remaining fraction. The usual greedy algorithm can require a denominator larger than Int.MaxValue, even for an input with Int components. The following implementation uses arbitrary-precision integers internally. If that representational limit is reached, it returns the always-valid alternative consisting of num copies of

1/ d e n

. Repeated denominators are permitted by the given Egyptian fraction representation.

def fromRat(num: Int, den: Int): Array[Int] = {
  require(0 <= num && num < den)
  val start = Reduce(num, den)
  var n = BigInt(start._1)
  var d = BigInt(start._2)
  var e = Array.empty[Int]
  while (n > 0) {
    val q = (d + n - 1) / n
    if (!q.isValidInt) return Array.fill(num)(den)
    e = e :+ q.toInt
    val nextN = n * q - d
    val nextD = d * q
    val g = nextN.gcd(nextD)
    n = nextN / g
    d = nextD / g
  }
  e
}

The loop invariant is

d > 0

0 \leq n < d

, all entries of e are positive, and

\sum_{0 \leq j < e . l e n g t h} \frac{1}{e ( j )} + \frac{n}{d} = \frac{n u m}{d e n} .

(1)

Appending

q

and replacing the residual by

(n q - d) / (d q)

preserves this equality; division by the greatest common divisor preserves the residual's value. The loop variant is

n

, by the proof in part (b). If nextN is zero, its greatest common divisor with nextD is nextD, giving residual

0/1

. On normal exit the residual is zero and the returned array has exactly the required value. On the early-return branch, num copies of

1/ d e n

have that same value directly; the partial greedy Egyptian fraction expansion is discarded. num=0 returns an empty array.

The fallback is a correctness provision for the fixed result type, not an efficiency claim: a large repeated-term array can be impractical. An array of arbitrary-precision integers would retain the greedy Egyptian fraction expansion without this fallback. Allocation, as with any output-producing program, requires enough available memory. The BigInt remainder, greatest common divisor and checked conversion operations are documented in ^[ref].

d

 0  0

Solution

 0  0

An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only Reduce on every intermediate value. First define an exact helper:

def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
  var n = BigInt(0)
  var d = BigInt(1)
  var i = 0
  while (i < e.length) {
    require(e(i) > 0)
    val x = BigInt(e(i))
    val g = d.gcd(x)
    val nextN = n * (x / g) + d / g
    val nextD = d * (x / g)
    val h = nextN.gcd(nextD)
    n = nextN / h
    d = nextD / h
    i += 1
  }
  (n, d)
}

def toRat(e: Array[Int]): (Int, Int) = {
  val result = toRatExact(e)
  require(result._1.isValidInt && result._2.isValidInt,
          "Reduced result does not fit (Int, Int)")
  (result._1.toInt, result._2.toInt)
}

The loop invariant is

0 \leq i \leq e . l e n g t h

n \geq 0

d > 0

g cd (n, d) = 1

, and

\frac{n}{d} = \sum_{0 \leq j < i} \frac{1}{e ( j )} .

(1)

Writing

g = g cd (d, x)

, the fraction for the extended prefix has numerator

n (x / g) + d / g

and denominator

d (x / g)

. These are the nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is

e . l e n g t h - i

. At exit the helper returns the exact sum in lowest terms, including

(0, 1)

for the empty array.

There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits (Int, Int). For example, the sum

1/46337 + 1/46349

92686/2147673613

in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.^[ref]

e

 0  0

Solution

 0  0

Print separators before all but the first term, so there is neither a leading nor a trailing plus sign:

def printRat(num: Int, den: Int): Unit = {
  print(num.toString + "/" + den.toString)
}

def printEgypt(e: Array[Int]): Unit = {
  if (e.isEmpty) print("0")
  var i = 0
  while (i < e.length) {
    if (i > 0) print(" + ")
    print("1/" + e(i).toString)
    i += 1
  }
}

The loop invariant says that exactly the first

i

unit fractions have been printed in order, separated by + , with no trailing separator. The loop variant is

e . l e n g t h - i

. The empty array is displayed as zero. Since

5/7 - 1/2 = 3/14

and

3/14 - 1/5 = 1/70

, the output is 5/7 = 1/2 + 1/5 + 1/70. The source's earlier example with middle denominator

4

and final denominator

70

contains the arithmetic typo; its final printing example is correct. Indeed

1/2 + 1/4 > 5/7

, so no positive final term could repair that particular prefix. The printing routine reports the generated terms rather than imposing a particular expansion.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

 Ancestors (10)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1

 Discussion (0)  Subscribe (1)

 Discussion (0)