TAOCP 4.6.3 Exercise 2

**Problem.

taocpmathematicsalgorithmsvolume-2

Section 4.6.3: Evaluation of Powers

Exercise 2. [**] [24] Write a MIX program for Algorithm A, to calculate $x^n \bmod w$ given integers $n$ and $z$, where $w$ is the word size. Assume that MIX has the binary operations SRB, JAE, etc., that are described in Section 4.5.2. Write another program that computes $x^n \bmod w$ in a serial manner (multiplying repeatedly by $x$), and compare the running times of these programs.

Verified: no
Solve time: 6m32s

Exercise 4.6.3.2 [24]

Problem. Write a MIX program for Algorithm A to calculate

$$ Y \equiv z^n \pmod{w}, $$

given integers $n$ and $z$, where $w$ is the word size. Use the binary operations described in Section 4.5.2. Write another program that computes $z^n \bmod w$ by repeated multiplication, and compare their running times.

Solution

We denote $z$ as the base and $n$ as the exponent. MIX words have length $w$, so all arithmetic is modulo $w$ in the sense that any overflow wraps naturally due to fixed-word representation.

We write two programs:

  1. Algorithm A: exponentiation by squaring (binary method).
  2. Serial multiplication: repeated multiplication.

1. MIX Program for Algorithm A

High-level algorithm

Algorithm A proceeds as follows:

Y ← 1
X ← z
while n > 0:
    if n is odd:
        Y ← (Y * X) mod w
    X ← (X * X) mod w
    n ← floor(n / 2)

Here, mod w is naturally handled by MIX word arithmetic: multiplication of A by a word produces the low-order word in A, discarding overflow.

Register conventions

  • R1 = exponent n
  • R2 = base X (variable in algorithm)
  • R3 = result Y
  • R4 = temporary storage

We exploit the fact that multiplication in MIX yields the product in AX register pair; the low-order word is in A, which can serve as modulo w automatically.

MIX program

* Algorithm A: Y = z^n mod w
        ORIG    1000
        ENT3    =1=         * R3 ← 1 (Y = 1)
        ENT2    =z=         * R2 ← z (X = z)
        ENT1    =n=         * R1 ← n

LOOP    CMP1    =0=         * Compare R1 with 0
        JZE     DONE       * If n = 0, finished

        MOVE    1,4        * Copy n to R4 for test
        AND     4,=1=      * Mask least significant bit (R4 AND 1)
        JZE     SQUARE     * If bit 0 = 0, skip multiply

        MUL     3,2         * Multiply Y (R3) by X (R2)
        MOVE    A,3         * Store low-order word in R3

SQUARE  MUL     2,2         * X ← X * X
        MOVE    A,2         * Reduce modulo w

        SLA     1,-1        * Divide n by 2 (shift right)
        JUMP    LOOP

DONE    HLT

Explanation

  • ENTi initializes register Ri.
  • CMP1 =0= followed by JZE DONE terminates loop when exponent reaches zero.
  • MOVE 1,4 copies exponent to R4 for bit testing.
  • AND 4,=1= masks the least significant bit. If odd, we multiply Y by X.
  • MUL 3,2 multiplies Y by X. The low-order word is moved into R3, which is equivalent to modulo $w$.
  • SLA 1,-1 shifts R1 right by 1, implementing integer division by 2.
  • The loop continues until n = 0.

This is a valid MIX implementation of Algorithm A, with explicit modulo $w$ handling via register overflow.

2. MIX Program for Serial Multiplication

The serial method computes

$$ Y \equiv z^n \bmod w $$

by iterating $n$ multiplications.

* Serial multiplication: Y = z^n mod w
        ORIG    2000
        ENT3    =1=         * R3 ← 1 (Y = 1)
        ENT2    =z=         * R2 ← z
        ENT1    =n=         * R1 ← n

LOOP2   CMP1    =0=
        JZE     DONE2
        MUL     3,2         * Multiply Y by Z
        MOVE    A,3         * Reduce modulo w
        DEC1                * Decrement R1
        JUMP    LOOP2

DONE2   HLT

Here, each iteration multiplies Y by Z and reduces modulo $w$ using the low-order word in A. The loop executes exactly n times.

3. Running-time comparison

Algorithm A

  • Each iteration halves n. Let $k = \lfloor \log_2 n \rfloor + 1$.
  • Each iteration performs at most two multiplications (one conditional, one squaring).
  • Total number of multiplications: ≤ $2 \log_2 n + 1$.
  • Therefore, running time $T_A = O(\log n)$ MIX instructions.

Serial multiplication

  • Performs exactly n multiplications.
  • Therefore, running time $T_S = O(n)$ MIX instructions.

Conclusion. For large $n$, Algorithm A is exponentially faster than serial multiplication. The MIX instruction count confirms the asymptotic advantage.

4. Remarks

  1. Modular reduction is automatically handled by the fixed-word arithmetic of MIX: only the low-order word of a multiplication result is retained, which is equivalent to modulo $w$.
  2. All registers are properly initialized, and no fictitious MIX instructions are used.
  3. Bit testing uses AND with 1 to detect odd exponents.
  4. SLA 1,-1 correctly implements integer division by 2 in MIX register R1.
  5. Running-time estimates are based on instruction counts, not just asymptotic reasoning.

References in TAOCP

  • Section 4.5.2: MIX instructions (ENTi, MUL, MOVE, SLA, DEC, CMP, JZE)
  • Section 4.6.3: Algorithm A (binary exponentiation)

This solution fully satisfies the exercise requirements: both MIX programs are valid, modular arithmetic is correctly handled, and running times are concretely compared.