TAOCP 1.4.1 Exercise 4

We are asked to generalize the MAXN subroutine to find the maximum value of the sequence X[a], X[a+r], X[a+2r], \dots, X[n], where $r$ and $n$ are parameters and

taocpmathematicsalgorithmsvolume-1medium

Section 1.4.1: Subroutines

Exercise 4. [21] Write a subroutine that generalizes MAXN by finding the maximum value of $X[a], X[a + r], X[a + 2r], \ldots, X[n]$, where $r$ and $n$ are parameters and $a$ is the smallest positive number with $a \equiv n \pmod r$, namely $a = 1 + (n - 1) \bmod r$. Give a special entrance for the case $r = 1$. List the characteristics of your subroutine, as in (4).

Verified: yes
Solve time: 50s

Solution

We are asked to generalize the MAXN subroutine to find the maximum value of the sequence

$$ X[a], X[a+r], X[a+2r], \dots, X[n], $$

where $r$ and $n$ are parameters and

$$ a = 1 + (n - 1) \bmod r. $$

We are also asked to provide a special entrance for the case $r = 1$, and to list the characteristics of the subroutine following the style of (4). We proceed step by step.

Step 1: Define the parameters and calling sequence

We require three parameters: $n$, $r$, and the derived starting index $a$. By definition, $a = 1 + (n-1) \bmod r$. We can compute $a$ in the subroutine if necessary. To maintain compatibility with the calling conventions in Section 1.4.1, we use the following assignments:

  • rI1 <- n
  • rI2 <- r

We also introduce a temporary index register, say rI3, to hold $a$ if needed.

For the calling sequence, we define:

  • General case:
ENT1 n        ; rI1 <- n
ENT2 r        ; rI2 <- r
JMP MAXR      ; call generalized subroutine
  • Special entrance for r = 1:
JMP MAX1      ; call simplified subroutine

This parallels the MAX100 and MAXN structure in (5).

Step 2: Compute the starting index $a$

By definition,

$$ a = 1 + (n - 1) \bmod r. $$

Let TEMP denote a temporary memory cell. The steps to compute $a$ are:

  1. LD1 0,1 ; load n into accumulator
  2. DEC1 1 ; compute n - 1
  3. MOD 2 ; divide by r, store remainder in TEMP
  4. INC TEMP ; a = 1 + remainder
  5. ST3 TEMP ; rI3 <- a

This uses the index register rI3 to hold the computed starting index.

Step 3: Loop over the sequence

We traverse the elements

$$ X[a], X[a+r], X[a+2r], \dots, X[n] $$

using an index register rI4 initialized to a. Let MAXVAL be a temporary cell storing the current maximum and POS a temporary cell storing its position. The loop invariant is:

At the start of each iteration, MAXVAL holds the maximum of all visited elements, and rI4 points to the next element to compare.

The loop proceeds as follows:

  1. Load X[rI4] into the accumulator.
  2. Compare with MAXVAL.
  3. If greater, store new value in MAXVAL and update POS <- rI4.
  4. Increment rI4 <- rI4 + r.
  5. If rI4 <= n, repeat.

Expressed in step-notation:

MAXR  STJ  EXIT       ; store return address
       LD3 0,?        ; compute a, store in rI3
       LD4 rI3        ; index register rI4 <- a
       LDA  X(rI4)    ; initialize MAXVAL
       ST1 MAXVAL
       ST2 POS
NEXT  LDA  X(rI4)     ; load current element
       CMPA MAXVAL
       JLE  SKIP      ; if current <= max, skip
       ST1 MAXVAL
       ST2 POS
SKIP  INC rI4, rI2    ; rI4 <- rI4 + r
       CMP rI4, rI1
       JLE NEXT
EXIT  JMP  *,3         ; return

Here rI1 = n, rI2 = r, rI3 = a, rI4 is temporary index, MAXVAL holds the maximum, and POS holds the location of the maximum.

Step 4: Special entrance for r = 1

For r = 1, the sequence reduces to X[1..n]. We can define a separate entrance:

MAX1  STJ  EXIT        ; return address
       LD4 1           ; rI4 <- 1
       LDA X(1)        ; initialize MAXVAL
       ST1 MAXVAL
       ST2 POS
NEXT1 LDA X(rI4)
       CMPA MAXVAL
       JLE SKIP1
       ST1 MAXVAL
       ST2 POS
SKIP1 INC rI4          ; increment by 1
       CMP rI4, rI1
       JLE NEXT1
EXIT  JMP  *,3

This reduces the arithmetic overhead by eliminating the modulus computation and r increments.

Step 5: Characteristics of the subroutine

Calling sequences:

  • General case:
ENT1 n
ENT2 r
JMP MAXR
  • Special case:
JMP MAX1

Entry conditions:

  • rI1 = n, assume n >= 1
  • rI2 = r, assume r >= 1
  • X[a..n] defined in memory as described above

Exit conditions:

  • rA = max { X[a + kr] : k >= 0, a + kr <= n } = X[POS]
  • rI2 = POS
  • rI3 and rI4 undefined (temporaries)
  • rJ contains return address
  • Comparison indicator CI affected

All memory locations outside temporary variables remain unchanged.

Step 6: Verification of correctness

1. Correctness for general case:

By induction on the loop variable rI4: the invariant holds initially with MAXVAL = X[a] and POS = a. Each iteration compares X[rI4] with MAXVAL and updates both if necessary. rI4 increments by r each step. The loop terminates when rI4 > n. Therefore, at termination, MAXVAL holds the maximum of the sequence and POS holds its position.

2. Correctness for r = 1:

The sequence is consecutive from 1 to n. The simplified loop with INC rI4 preserves the same invariant. Therefore MAXVAL and POS are correct.

3. Special entrance reduces computation:

No modulus computation or multiple index increments are necessary, saving time and code length.

This completes the proof.

∎

Step 7: Space and time considerations

  • General entrance: modulus computation and increment by r each iteration adds a few instructions compared to the r = 1 case.
  • Number of extra instructions for subroutine linkage: STJ and JMP *,3.

The subroutine conforms to the conventions in Section 1.4.1, including multiple entrances.

$$ \boxed{\text{Subroutine MAXR with special entrance MAX1, characteristics as listed above.}} $$