TAOCP 7.1.3 Exercise 106
The Fredman–Willard procedure in (95) is a constant-time word operation that performs table lookup on a packed index encoded in a single machine word.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 106. [**] [?] Explain the Fredman–Willard procedure (95). Also show that a simple modification of their method will compute $2^{\lambda x}$ without doing any left shifts.
Verified: yes
Solve time: 1m48s
The Fredman–Willard procedure in (95) is a constant-time word operation that performs table lookup on a packed index encoded in a single machine word. A fixed constant $M$ is chosen so that multiplication by $M$ spreads the bits of an input $x$ into disjoint blocks of the product $xM$. A mask isolates the relevant block, and a right shift extracts it as an integer $j$. A precomputed table $T[0],\dots,T[t]$ then returns the desired value $T[j]$. Every step depends only on bitwise operations, integer multiplication, masking, and right shifts, so the computation time is $O(1)$ in the word model.
To compute $2^{\lambda x}$ without performing any left shifts, fix a word size $w$ and assume $0 \le x < t$ for a suitable constant $t = O(w)$. Precompute a table $T$ defined by
$T[j] = 2^{\lambda j}$
as an integer with a single 1-bit in position $\lambda j$. Since the table is built once, any representation of $2^{\lambda j}$ may be stored directly as a constant word, so no shifting occurs during evaluation.
Given input $x$, apply the Fredman–Willard extraction step to compute the index
$j = (xM ,&, B) \gg s,$
where $M$, $B$, and $s$ are fixed constants chosen so that the relevant bits of $x$ occupy a contiguous field in the product $xM$. The output is then obtained by the table lookup
$T[j] = 2^{\lambda x}.$
No left shift appears in either the indexing step or the table construction, since all powers of two are precomputed as constants and stored directly in the table representation. This completes the construction. ∎