The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth

CHAPTER THREE

RANDOM NUMBERS

3.2.1.1. Choice of modulus

[12]

Consider MMIX as an example. We can compute y mod m by putting y and m in registers and dividing y by m using the instruction ‘DIV t,y,m’; y mod m will then appear in register rR. But division is a comparatively slow operation, and it can be avoided if we take m to be a value that is especially convenient, such as the word size of our computer.

Let w be the computer’s word size, namely 2^e on an e-bit binary computer. The result of an addition and multiplication is usually given modulo w. Thus, the following program computes the quantity (aX + c) mod w efficiently:

MULU	x,x,a	X ← aX mod w.		(1)
ADDU	x,x,c	X ← (X + c) mod w.

The result appears in register x. The code uses arithmetic ...