Arbitrary-precision integer Created 2026-10-20 Updated 2026-11-05
View more
An arbitrary-precision integer stores an integer using a variable number of machine words. Unlike a fixed-width integer, it grows when more binary digits are needed. The sign and a finite sequence of base- digits represent its exact value.
For example, the integer requires hundreds of bits but no rounding. Arbitrary-precision integer arithmetic operates on these representations; it is distinct from approximate floating-point arithmetic. Memory and computation still impose practical bounds, so arbitrary precision does not mean infinite available storage.
Read the full article
Big-integer multiplication Created 2026-10-20 Updated 2026-11-05
View more
Big-integer multiplication multiplies arbitrary-precision integers represented by arrays of digits. For and , first compute the coefficient sums , then propagate carries in base . Thus the main step is a convolution followed by carry handling.
The school method needs digit multiplications for two -digit inputs. Karatsuba multiplication splits each input into two halves and uses three recursive products instead of four, giving arithmetic work under the usual digit model. For larger inputs, transform-based methods accelerate the convolution. Which method is fastest depends on input size and implementation overhead.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 7 / d / Solution 2026-10-31
View more
Use a programming closure whose private variable holds the next Fibonacci number. Use arbitrary-precision integers to enumerate all terms exactly:
def fibonacci(): Iter[BigInt] = {
  var following = BigInt(1)
  val step: BigInt => BigInt = (current: BigInt) => {
    val result = following
    following = current + following
    result
  }
  new FunIter[BigInt](BigInt(0), step)
}
At the cell containing , the private state immediately before computing its successor is following = F_(i+1). The successor returns that value and sets following to , preserving the recursion invariant. The resulting sequence starts
(1)
Each successor is computed once by the memoized implementation in part (c); interleaved copies see the same already generated successor instead of independently advancing shared programming closure state. Replacing BigInt by Int and the two initial values by 0,1 gives exactly the hinted Int => Int implementation, but eventually incurs integer overflow, so it does not enumerate all mathematical Fibonacci numbers.
An alternative avoiding mutable programming closure state represents the current and next Fibonacci numbers by a pair and uses the pure function with initial state ; a projecting iterator returns the first component. The closure construction above meets the suggested one-number interface directly.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 7 / c / i / Solution 2026-10-25
View more
Compare areas before and after each completed setter call. Widen before multiplication so all products of two Int dimensions are represented exactly:
class LoggedResizableFrame(h: Int, w: Int) extends ResizableFrame(h, w) {
  private var increases = BigInt(0)

  private def actualArea: Long = height.toLong * width.toLong

  override def height_=(h: Int): Unit = {
    val before = actualArea
    super.height_=(h)
    if (actualArea > before) increases += 1
  }

  override def width_=(w: Int): Unit = {
    val before = actualArea
    super.width_=(w)
    if (actualArea > before) increases += 1
  }

  def getIncreases: BigInt = increases
}
The history invariant is that increases counts exactly the completed dimension updates whose new area strictly exceeds their immediately preceding area. The constructor's starting area is a baseline, not an increase. Each overriding setter invokes the superclass setter once and increments precisely when its comparison succeeds. Equal-area changes do not count. The comparison is on area, not merely on which dimension increased; this also handles zero or signed dimensions without adding an unstated input restriction. An arbitrary-precision integer avoids eventual counter overflow.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 8 / d / Solution 2026-10-25
View more
Inside the supplied MainFrame, after both buttons and the label are defined, add:
private var clickCount = BigInt(0)
listenTo(button1, button2)
reactions += {
  case ButtonClicked(source) if (source eq button1) || (source eq button2) =>
    clickCount += 1
    label.text = "Total button clicks: " + clickCount.toString
}
The invariant is that clickCount equals the total number of handled click events from the two buttons. It starts at zero; each matching event increments it exactly once and refreshes the label. The buttons' existing self-listeners can still change their own text independently. Listening to both publishers is necessary: their listenTo(this) calls subscribe each button to itself, not the frame to both buttons. Updating the label is not another button click, so it does not recursively increment the counter. An arbitrary-precision integer keeps the count exact without a lifetime overflow bound.[ref]
The supplied layout already contains the label, so no additional component is needed. Before any click it retains its initial zero-click message; afterwards it displays the cumulative count across both buttons.
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 / 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