Allocate a fresh array and copy every digit:
function CopyNum(n: number): number
    new(result, len(n))
    for i := 0 to len(n)-1 do
        result[i] := n[i]
    return result
Every coefficient in the digit-array integer representation is unchanged, so the value is unchanged. The new array shares no storage with n; assigning one pointer to the other would instead create reference aliasing. Since the entries are integers, copying the entries also gives the required deep copy of this representation.
The pointer argument must be passed by reference, because it is replaced:
procedure Lengthen(var n: number)
    old := n
    L := len(old)
    new(result, 2*L)
    for i := 0 to L-1 do
        result[i] := old[i]
    for i := L to 2*L-1 do
        result[i] := 0
    n := result
The low-order coefficients are preserved and the newly allocated high-order coefficients are zero, so the digit-array integer representation has the same value. The allocation remains nonempty because . Neither allocation nor an uninitialized high-order cell may be assumed to contain zero. Any other reference to the old array still denotes that old array; the code does not free storage through an alias.
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.
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.
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.
Use schoolbook multiplication on the digit coefficients:
function Mul(a, b: number): number
    new(result, len(a)+len(b))
    for k := 0 to len(result)-1 do
        result[k] := 0
    for i := 0 to len(a)-1 do
        for j := 0 to len(b)-1 do
            result[i+j] := result[i+j] + a[i]*b[j]
    Normal(result)
    return result
This is discrete convolution of the digit arrays. Expanding the product shows
(1)
before normalization. Normalization preserves the value and establishes the digit bounds. Allocating fresh storage makes input aliasing harmless. The convolution uses coefficient products for input lengths . Intermediate products and sums need sufficiently wide or arbitrary-precision arithmetic; fitting each normalized digit into a small integer does not alone prevent accumulator overflow.
Normalize a copy, skip high-order zero blocks, print the highest block ordinarily, and pad all remaining blocks:
procedure OutNum(n: number)
    z := CopyNum(n)
    Normal(z)
    i := len(z)-1
    while i > 0 and z[i] = 0 do
        i := i-1
    Out.Int(z[i])
    i := i-1
    while i >= 0 do
        place := base div 10
        while place > 0 do
            digit := (z[i] div place) mod 10
            Out.Char(character('0' + digit))
            place := place div 10
        i := i-1
Here Out.Int writes an ordinary unpadded decimal integer, and character('0' + digit) denotes its decimal digit character. Since for , the inner loop writes exactly characters per lower block. This power-of-ten digit-block formatting retains internal zeros: base- digits print as 12000004, not 1204. An all-zero array prints exactly 0. The caller's original array is preserved.

Ancestors (10)

  1. Imperative programming
  2. 2017
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version