TAOCP 3.2.1.1 Exercise 9

Section 3.2.1.1: Choice of Modulus

Exercise 9. ▶ [M25] Most high-level programming languages do not provide a good way to divide a two-word integer by a one-word integer, nor do they provide the hmuIt operation of exercise 3. The purpose of this exercise is to find a reasonable way to cope with such limitations when we wish to evaluate $ax \bmod m$ for variable $x$ and for constants $0 < a < m$.

a) Prove that if $q = \lfloor m/a \rfloor$, we have $a(x - (x \bmod q)) \equiv \lfloor x/q \rfloor(m - (m \bmod a))$. b) Use the identity of (a) to evaluate $ax \bmod m$ without computing any numbers that exceed $m$ in absolute value, assuming that $a^2 \le m$.

Verified: yes
Solve time: 1m30s

---

Solution

Let

$$ q=\left\lfloor \frac{m}{a}\right\rfloor , \qquad r=m\bmod a, $$

so that

$$ m=aq+r,\qquad 0\le r<a. $$

Also write

$$ x=q\left\lfloor \frac{x}{q}\right\rfloor +(x\bmod q). $$

(a)

Since

$$ x-(x\bmod q)=q\left\lfloor \frac{x}{q}\right\rfloor , $$

we have

$$ a\bigl(x-(x\bmod q)\bigr) =a q\left\lfloor \frac{x}{q}\right\rfloor . $$

From $m=aq+r$,

$$ aq=m-r=m-(m\bmod a). $$

Therefore

$$ a\bigl(x-(x\bmod q)\bigr) = \left\lfloor \frac{x}{q}\right\rfloor \bigl(m-(m\bmod a)\bigr). $$

Hence

$$ a\bigl(x-(x\bmod q)\bigr) \equiv \left\lfloor \frac{x}{q}\right\rfloor \bigl(m-(m\bmod a)\bigr) \pmod m. $$

This proves the stated identity.

(b)

Let

$$ x=q\left\lfloor \frac{x}{q}\right\rfloor +(x\bmod q). $$

Using part (a),

$$ \begin{aligned} ax &= a(x\bmod q) +a\bigl(x-(x\bmod q)\bigr)\ &\equiv a(x\bmod q) +\left\lfloor \frac{x}{q}\right\rfloor \bigl(m-(m\bmod a)\bigr) \pmod m. \end{aligned} $$

Since the second term contains a factor $m$,

$$ ax \equiv a(x\bmod q) -\left\lfloor \frac{x}{q}\right\rfloor (m\bmod a) \pmod m. $$

Define

$$ t=a(x\bmod q)-\left\lfloor \frac{x}{q}\right\rfloor (m\bmod a). $$

Then

$$ ax\bmod m=t\bmod m. $$

It remains to show that no intermediate quantity exceeds $m$ in absolute value when $a^{2}\le m$.

Because

$$ q=\left\lfloor \frac{m}{a}\right\rfloor \ge a, $$

we have

$$ 0\le x\bmod q<q, $$

hence

$$ 0\le a(x\bmod q)<aq\le m. $$

Also,

$$ 0\le \left\lfloor \frac{x}{q}\right\rfloor \le \left\lfloor \frac{m-1}{q}\right\rfloor . $$

Since $q\ge a$,

$$ \left\lfloor \frac{m-1}{q}\right\rfloor < \frac{m}{q} \le \frac{m}{m/a} =a. $$

Thus

$$ \left\lfloor \frac{x}{q}\right\rfloor < a, $$

and because $0\le m\bmod a<a$,

$$ 0\le \left\lfloor \frac{x}{q}\right\rfloor (m\bmod a) < a^{2} \le m. $$

Therefore both products

$$ a(x\bmod q), \qquad \left\lfloor \frac{x}{q}\right\rfloor (m\bmod a) $$

are strictly less than $m$. Their difference $t$ satisfies

$$ -m<t<m. $$

Consequently every quantity formed during the computation has absolute value at most $m$.

The desired procedure is therefore:

$$ \begin{array}{l} q\leftarrow \left\lfloor m/a\right\rfloor,\[4pt] r\leftarrow m\bmod a,\[4pt] t\leftarrow a(x\bmod q)-r\left\lfloor x/q\right\rfloor,\[4pt] \text{if }t<0\text{, set }t\leftarrow t+m. \end{array} $$

Since $-m<t<m$, a single addition of $m$ suffices when $t<0$. The final value $t$ is equal to $ax\bmod m$.

Thus

$$ \boxed{,ax\bmod m = a(x\bmod q) -(m\bmod a)\left\lfloor \frac{x}{q}\right\rfloor \pmod m,\qquad q=\left\lfloor \frac{m}{a}\right\rfloor,} $$

and this computation never requires numbers whose absolute value exceeds $m$ when $a^{2}\le m$. ∎