TAOCP 3.2.1.1 Exercise 6

Section 3.2.1.1: Choice of Modulus

Exercise 6. ▶ [**] $[28]$ The previous exercise suggests that subtraction mod $m$ is easier to perform than addition mod $m$. Discuss sequences generated by the rule

$$X_{n+1} = (a X_n - c) \bmod m.$$

Are these sequences essentially different from linear congruential sequences as defined in the text? Are they more suited to efficient computer calculation?

Verified: yes
Solve time: 2m36s

---

Solution

Consider the recurrence

$$ X_{n+1} \equiv aX_n-c \pmod m. $$

We compare it with the ordinary linear congruential generator

$$ Y_{n+1} \equiv aY_n+c \pmod m. $$

Define a new sequence by

$$ Y_n \equiv -X_n \pmod m. $$

Since the map

$$ x \mapsto -x \pmod m $$

is a permutation of the residue classes modulo $m$, it is a bijection.

Now

$$ Y_{n+1} \equiv -X_{n+1} \equiv -(aX_n-c) \equiv a(-X_n)+c \equiv aY_n+c \pmod m. $$

Thus the sequence ${Y_n}$ satisfies the standard linear congruential recurrence

$$ Y_{n+1}\equiv aY_n+c\pmod m. $$

Conversely, if ${Y_n}$ satisfies this recurrence, then $X_n\equiv -Y_n\pmod m$ satisfies

$$ X_{n+1}\equiv aX_n-c\pmod m. $$

Therefore the two forms are equivalent under the bijective change of variables

$$ X_n \leftrightarrow -X_n \pmod m. $$

It follows that sequences generated by

$$ X_{n+1}=(aX_n-c)\bmod m $$

are not essentially different from ordinary linear congruential sequences. The correspondence is one-to-one, so cycle lengths, period structure, distribution properties, and any other properties depending only on the sequence of residue classes are preserved. The subtraction form merely relabels each state $x$ as $-x \pmod m$.

As for computation, Exercise 5 shows that when $m$ is smaller than the machine word size, subtraction modulo $m$ can be performed very conveniently. Given $0\le x,y<m$, the quantity

$$ (x-y)\bmod m $$

can be obtained by an ordinary subtraction followed, if necessary, by the addition of $m$. This may require slightly less work than modular addition, where one must detect and correct overflow beyond $m$.

Hence the recurrence

$$ X_{n+1}=(aX_n-c)\bmod m $$

may be marginally more convenient to implement on certain machines. However, this is only an implementation advantage. Mathematically it defines exactly the same class of generators as the standard linear congruential method. ∎