TAOCP 7.1.3 Exercise 26

Let $i$ be the index, $0 \le i < 12\cdot 10^6$, and write q = \left\lfloor \frac{i}{12} \right\rfloor,\qquad r = i - 12q,\qquad 0 \le r < 12.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 26. [22] Suppose we want random access to a table of 12 million items of 5-bit data. We could pack 12 such items into one 64-bit word, thereby fitting the table into 8 megabytes of memory. But random access then seems to require division by 12, which is rather slow; we might therefore prefer to let each item occupy a full byte, thus using 12 megabytes altogether.

Show, however, that there's a memory-efficient approach that avoids division.

Verified: yes
Solve time: 2m18s

Let $i$ be the index, $0 \le i < 12\cdot 10^6$, and write

$$ q = \left\lfloor \frac{i}{12} \right\rfloor,\qquad r = i - 12q,\qquad 0 \le r < 12. $$

We avoid division by 12 by replacing it with multiplication by a fixed reciprocal.

1. Choice of scaling constant

Fix an integer $k$ such that

$$ 2^k > 12\cdot 10^6. $$

(For example, $k=24$ since $2^{24}=16{,}777{,}216$.)

Define

$$ m = \left\lfloor \frac{2^k}{12} \right\rfloor. $$

Then

$$ m \le \frac{2^k}{12} < m+1. $$

Define the approximate quotient

$$ q_0 = \left\lfloor \frac{i m}{2^k} \right\rfloor, \qquad r_0 = i - 12 q_0. $$

All operations used are multiplication by a constant, shifts, subtraction, and comparison.

2. Key approximation lemma (corrected)

We compare

$$ \frac{i m}{2^k} \quad \text{and} \quad \frac{i}{12}. $$

From $m \le 2^k/12 < m+1$, multiply by $i/2^k$:

$$ \frac{i m}{2^k} \le \frac{i}{12} < \frac{i(m+1)}{2^k}. $$

For the upper bound,

$$ \frac{i(m+1)}{2^k} = \frac{i m}{2^k} + \frac{i}{2^k} < \frac{i m}{2^k} + 1, $$

because $i < 2^k$.

Thus we obtain the crucial sandwich:

$$ \frac{i m}{2^k} \le \frac{i}{12} < \frac{i m}{2^k} + 1. $$

Rewriting,

$$ 0 \le \frac{i}{12} - \frac{i m}{2^k} < 1. $$

So the approximation error is strictly less than 1.

3. Consequence for quotients

Let

$$ y = \frac{i}{12},\qquad y' = \frac{i m}{2^k}. $$

Then

$$ y' \le y < y' + 1. $$

This implies the standard floor relation:

$$ q_0 = \lfloor y' \rfloor \in {q,, q-1}. $$

Indeed:

  • Since $y < y' + 1$, we cannot be off by more than 1 upward.
  • Since $y' \le y$, the approximation never overshoots $y$.

Hence the computed quotient differs from the true quotient by at most 1.

4. One-step correction

Compute

$$ r_0 = i - 12 q_0. $$

  • If $q_0 = q$, then $r_0 = r$ and $0 \le r_0 < 12$.
  • If $q_0 = q-1$, then

$$ r_0 = i - 12(q-1) = 12 + r, $$

so $12 \le r_0 < 24$.

Therefore a single correction suffices:

$$ \text{if } r_0 \ge 12 \text{ then } q_0 \leftarrow q_0 + 1,\quad r_0 \leftarrow r_0 - 12. $$

After this step,

$$ q_0 = \left\lfloor \frac{i}{12} \right\rfloor,\qquad r_0 = i - 12q_0,\qquad 0 \le r_0 < 12. $$

5. Memory access

Each word contains 12 packed 5-bit fields. The final access is:

  • locate word $Q_{q_0}$,
  • extract the $r_0$-th 5-bit field using shift and mask operations.

No division by 12 is ever performed. Only:

  • multiplication by constant $m$,
  • shift by $k$,
  • addition, subtraction,
  • comparison,

are required.

Conclusion

The algorithm correctly replaces division by 12 with a fixed multiplication and shift, producing a quotient that differs by at most 1, and correcting it with a single conditional adjustment. This yields fully constant-time random access with more compact memory usage and no division operation.