Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 1 / c / Solution 2026-10-31
View more
Propagate each carry into the next position, lengthening the array if necessary:
procedure Normal(var n: number)
    i := 0
    while i < len(n) do
        carry := floor(n[i] / base)
        n[i] := n[i] - carry*base
        if carry != 0 then
            if i+1 = len(n) then
                assert carry > 0
                Lengthen(n)
            n[i+1] := n[i+1] + carry
        i := i+1
The integer division identity gives a normalized remainder in . The local rewrite preserves value because a carry at position contributes exactly what was removed at position . The loop invariant is that the represented value is fixed and every position below i is normalized. Under the stated nonnegative-digit assumption all carries are nonnegative. Carries eventually stop beyond the finite radix expansion of the represented integer; scanning any spare allocated zeros then terminates.
This implementation also accepts signed temporary coefficients when their total represented value is nonnegative, using floor division rather than truncation toward zero. A negative carry out of the final position would make the entire represented value negative, since the already normalized lower part is smaller than the next radix power. Thus the assertion cannot fail for a nonnegative represented value. This extended carry normalization of a digit array also makes the arithmetic routines below robust to such temporary representations.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 1 / d / Solution 2026-10-31
View more
Start with a one-cell, possibly unnormalized representation, then carry:
function MakeNum(t: integer): number
    require t >= 0
    new(result, 1)
    result[0] := t
    Normal(result)
    return result
Before normalization its represented value is exactly t. Carry normalization of a digit array preserves that value and grows storage when needed. Zero returns a valid nonempty representation containing zero. A negative input is outside this nonnegative-number abstraction.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 1 / e / Solution 2026-10-31
View more
Add corresponding coefficients, treating missing coefficients as zero:
function Add(a, b: number): number
    L := max(len(a), len(b))
    new(result, L)
    for i := 0 to L-1 do
        result[i] := 0
        if i < len(a) then result[i] := result[i] + a[i]
        if i < len(b) then result[i] := result[i] + b[i]
    Normal(result)
    return result
By the digit-array integer representation, the raw result has value . Carry normalization of a digit array produces a normalized result, including any final carry. Both input arrays remain unchanged, so the operation also works when a and b alias each other.
Read the full article