TAOCP 6.4 Exercise 6
In MIX arithmetic, the instruction `DIV d` interprets the concatenation $AX$ as a single signed integer formed with $A$ as the high-order word and $X$ as the low-order word.
Exercise 6. [15] [15] Would it be wise to change the first two instructions of (3) to LDA K; ENTX 0?
Verified: no
Solve time: 2m14s
Solution
In MIX arithmetic, the instruction DIV d interprets the concatenation $AX$ as a single signed integer formed with $A$ as the high-order word and $X$ as the low-order word. The effect of DIV d is to divide this double-length quantity by $d$, producing a quotient in $A$ and a remainder in $X$.
In the original sequence (3), the first two instructions
$$ \text{LDX } K, \quad \text{ENTA } 0 $$
initialize
$$ A = 0, \quad X = K, $$
so the combined value is
$$ AX = 0 \cdot w + K = K. $$
Thus the subsequent DIV =1009= computes $K \bmod 1009$ in register $X$, which is the intended hash value.
Replacing these two instructions by
$$ \text{LDA } K, \quad \text{ENTX } 0 $$
produces
$$ A = K, \quad X = 0, $$
so the combined dividend becomes
$$ AX = K \cdot w + 0 = K w. $$
The value fed into DIV =1009= is therefore multiplied by the word radix $w$ before reduction modulo $1009$.
The resulting remainder satisfies
$$ (Kw) \bmod 1009 \neq K \bmod 1009 $$
in general, since the multiplication by $w$ is not neutral modulo $1009$ unless $w \equiv 1 \pmod{1009}$. In MIX, $w = 100$, so
$$ Kw \equiv 100K \pmod{1009}, $$
which induces a systematic permutation of residue classes rather than preserving the original mapping.
Since hashing in (3) relies on the direct congruence class of $K$ modulo $1009$, replacing the initialization alters the hash function from $K \mapsto K \bmod 1009$ to $K \mapsto 100K \bmod 1009$, which changes collision structure and distribution.
Therefore the modified initialization does not compute the same hash function and is not appropriate for the intended method. This completes the proof. ∎