TAOCP 3.6 Exercise 15
The generator must advance through _all_ $1009$ values in each block, returning the first $100$ and discarding the remaining $909$.
Exercise 15. [**] [25] Write C code that makes it convenient to generate the random integers obtained from run_array by discarding all but the first 100 of every 1009 elements, as recommended in the text.
Verified: yes
Solve time: 2m28s
The generator must advance through all $1009$ values in each block, returning the first $100$ and discarding the remaining $909$. Therefore we must keep track of our position within the current $1009$-element block and generate a new block only after all $1009$ entries have been consumed.
A convenient interface is:
#define USE 100
#define BLOCK 1009
static long buf[BLOCK];
static int k = BLOCK; /* force initial refill */
long ran100(void)
{
for (;;) {
if (k >= BLOCK) {
ran_array(buf, BLOCK);
k = 0;
}
if (k < USE)
return buf[k++];
/* discard entries USE..BLOCK-1 */
k++;
}
}
To verify correctness, suppose a block
$$ x_0,x_1,\ldots,x_{1008} $$
has been generated by ran_array(buf, BLOCK).
While $0 \le k < 100$, the routine returns
$$ x_0,x_1,\ldots,x_{99}. $$
After $x_{99}$ has been returned, $k=100$. Subsequent iterations do not return a value; they simply increment $k$ through
$$ 100,101,\ldots,1008, $$
thereby discarding
$$ x_{100},x_{101},\ldots,x_{1008}. $$
When $k=1009$, a new block of $1009$ values is generated, and the process repeats.
Hence the output sequence is exactly the sequence obtained from the stream produced by ran_array by retaining the first $100$ values of every $1009$ consecutive generated values and discarding the remaining $909$, as required. ∎