TAOCP 7.1.3 Exercise 218
Let $d \ge 3$ be fixed.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 218. ▶ [M30] [M30] (Hans Petter Selasky, 2009.) For fixed d ≥3, design an algorithm to compute a · xy mod 2d, given integers a, x, and y, where x is odd, using O(d) additions and bitwise operations together with a single multiplication by y.
Verified: yes
Solve time: 1m18s
Setup
Let $d \ge 3$ be fixed. Let $x,y,a$ be nonnegative integers, and assume $x$ is odd. The task is to compute
$a \cdot x y \bmod 2^d.$
The expression $xy$ denotes ordinary integer multiplication. Thus the goal is to compute the product of three integers modulo $2^d$, with the constraint that only one general integer multiplication (by $y$) is allowed, and the remaining work must use $O(d)$ additions and bitwise operations.
Since reduction modulo $2^d$ depends only on the lowest $d$ bits, all intermediate values may be truncated to $d$ bits using bitwise masking.
Solution
First compute the intermediate product
$t = x \cdot y.$
This uses the single permitted multiplication by $y$.
The desired result is then
$a \cdot t \bmod 2^d.$
Write the binary expansion of $t$ as
$t = \sum_{k=0}^{d-1} t_k 2^k,$
where each $t_k \in {0,1}$ denotes the $k$th bit of $t$ modulo $2^d$. Since reduction modulo $2^d$ discards higher bits, only these $d$ bits are relevant.
Using distributivity of multiplication over addition,
$a \cdot t = \sum_{k=0}^{d-1} t_k (a \cdot 2^k).$
Each term $a \cdot 2^k$ is obtained by a left shift:
$a \cdot 2^k = a \ll k.$
Hence
$a \cdot t \bmod 2^d = \left( \sum_{k=0}^{d-1} t_k (a \ll k) \right) \bmod 2^d.$
The computation proceeds by initializing an accumulator $s \leftarrow 0$ and processing bits of $t$ from $k=0$ to $d-1$.
For each $k$, compute the bit $t_k$ using bitwise operations:
$t_k = (t \gg k) ,&, 1.$
If $t_k = 1$, perform the update
$s \leftarrow (s + (a \ll k)) ,&, (2^d - 1).$
Each update uses one addition and a constant number of bitwise operations.
After processing all $d$ bit positions,
$s = a \cdot t \bmod 2^d.$
Thus the final output is $s$.
Verification
The decomposition of $t$ into bits is valid because every integer has a unique binary representation. Truncation modulo $2^d$ removes all contributions from terms $2^k$ with $k \ge d$, so restricting to $k < d$ preserves the value modulo $2^d$.
For each $k$, the identity
a \ll k & \text{if } t_k = 1,\ 0 & \text{if } t_k = 0 \end{cases}$$ follows directly from the definition of binary digits. The accumulator maintains the invariant after processing index $k$ that it equals $$\sum_{j=0}^{k} t_j (a \ll j) \bmod 2^d,$$ because each update adds exactly the contribution of the next bit and all arithmetic is reduced modulo $2^d$ after each step. Since there are exactly $d$ bit positions and each iteration uses one addition and $O(1)$ bitwise operations, the total work is $O(d)$ additions and bitwise operations after the single multiplication $t = x \cdot y$. This completes the proof. ∎ --- ## Notes The restriction to modulus $2^d$ is essential, since it ensures that shifting and masking implement exact modular reduction without carries propagating beyond $d$ bits. The method is a classical “bit-sliced multiplication,” where one operand is expanded into a sum of shifted copies and accumulation is performed digitwise in base $2$.