Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / c / Solution 2026-10-25
View more
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 . 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 , , all entries of e are positive, and
(1)
Appending and replacing the residual by preserves this equality; division by the greatest common divisor preserves the residual's value. The loop variant is , by the proof in part (b). If nextN is zero, its greatest common divisor with nextD is nextD, giving residual . On normal exit the residual is zero and the returned array has exactly the required value. On the early-return branch, num copies of 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].
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / d / Solution 2026-10-25
View more
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 , , , , and
(1)
Writing , the fraction for the extended prefix has numerator and denominator . These are the nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is . At exit the helper returns the exact sum in lowest terms, including 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 is 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]
Read the full article