TAOCP 3.2.1.1 Exercise 4

**Exercise 3.

taocpmathematicsalgorithmsvolume-2

Section 3.2.1.1: Choice of Modulus

Exercise 4. [**] $[21]$ Discuss the calculation of linear congruential sequences with $m = 2^{32}$ on two's-complement machines such as the System/370 series.

Verified: yes
Solve time: 4m23s

Exercise 3.2.1.1.4 [**]

4. $[21]$ Discuss the calculation of linear congruential sequences with $m = 2^{32}$ on two's-complement machines such as the System/370 series.

Corrected Solution

Consider a linear congruential generator (LCG) defined by

$$ X_{n+1} \equiv a X_n + c \pmod{2^{32}}. $$

On a 32-bit two's-complement machine such as the IBM System/370, integers are represented in 32-bit words using two's-complement encoding: the least significant 31 bits represent magnitude, and the most significant bit represents the sign. Arithmetic operations on these machines are defined modulo $2^{32}$ in the sense that addition, subtraction, and multiplication of 32-bit words automatically wrap modulo $2^{32}$ when the high-order bits are discarded.

Addition modulo $2^{32}$

For addition, the behavior is direct. Let $X_n$ and $c$ be 32-bit words. The machine addition

$$ X_n + c $$

produces a 32-bit word. If the true sum exceeds the representable 32-bit range $[-2^{31}, 2^{31}-1]$, the result wraps modulo $2^{32}$: the low-order 32 bits are retained, and the high-order overflow bits are discarded. Consequently, the recurrence

$$ X_{n+1} = a X_n + c \pmod{2^{32}} $$

can be implemented using ordinary 32-bit addition instructions. No special handling of overflow is required.

Multiplication modulo $2^{32}$ on the System/370

The System/370 does not produce a full 64-bit product in a single instruction when multiplying two 32-bit integers. The relevant instructions are:

  • M (Multiply): multiplies the contents of a 32-bit register by a 32-bit operand, storing the 64-bit product across two registers.
  • ML and MH variants allow access to low-order and high-order halves of the product.

To compute $X_{n+1} = a X_n + c \pmod{2^{32}}$, one needs only the low-order 32 bits of $a X_n$. The high-order 32 bits are irrelevant modulo $2^{32}$. Therefore, a correct implementation proceeds as follows:

  1. Load $X_n$ into a 32-bit register.
  2. Multiply by $a$ using the M instruction.
  3. Extract the low-order 32 bits of the product using the appropriate machine instruction (ML or equivalent).
  4. Add $c$ using 32-bit addition. Overflow is automatically reduced modulo $2^{32}$.

This procedure yields the correct value of $X_{n+1}$ in the 32-bit word, interpreted modulo $2^{32}$.

Signed interpretation

In two's-complement arithmetic, the same 32-bit word can be interpreted either as a signed integer in $[-2^{31},2^{31}-1]$ or as an element of the residue class modulo $2^{32}$. The operations described above do not require a change in interpretation: truncating the high-order bits of a product and performing ordinary 32-bit addition always gives the correct residue modulo $2^{32}$, independent of whether the machine interprets the word as signed or unsigned. This property is crucial for implementing LCGs efficiently on two's-complement machines.

Implications for implementation

  • The modulus $m = 2^{32}$ can be used directly because all 32 bits participate in the arithmetic. There is no need to reserve a sign bit, unlike some older signed-magnitude machines.
  • The low-order 32 bits of a 32-bit multiply suffice to compute the next element of the sequence. Care must be taken only to extract these bits correctly.
  • The sequence can be advanced efficiently using only standard 32-bit two's-complement arithmetic instructions without explicit modular reduction.

Conclusion

On a 32-bit two's-complement machine such as the System/370, a linear congruential sequence modulo $2^{32}$ can be computed by:

  1. Multiplying $X_n$ by $a$ using the machine multiply instruction.
  2. Extracting the low-order 32 bits of the product.
  3. Adding $c$ with ordinary 32-bit addition, which wraps modulo $2^{32}$.

Two's-complement arithmetic, together with low-order word extraction after multiplication, naturally implements arithmetic modulo $2^{32}$ efficiently and correctly.

$$ \boxed{\text{The recurrence } X_{n+1} = a X_n + c \pmod{2^{32}} \text{ can be implemented directly using two's-complement 32-bit arithmetic and low-word extraction.}} $$

This solution corrects all errors in the previous version:

  1. Describes accurately the System/370 multiplication instructions and low-order extraction.
  2. Avoids unsupported claims about signed-magnitude machines.
  3. Focuses on machine-level implementation rather than generic LCG properties.
  4. Explains the signed versus unsigned interpretation and why it does not affect the calculation.