<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 11/27/24 22:57, Pierre Abbat wrote:</div>
<div class="moz-cite-prefix"><span style="white-space: pre-wrap">
</span></div>
<blockquote type="cite" cite="mid:69067711.3F2A3RajZp@puma">
<pre wrap="" class="moz-quote-pre">How would you pick random numbers from 1 to k, where k is not a power of 2, to
minimize wastage of random bits?
</pre>
</blockquote>
<p>You will need:</p>
<p>Register R containing bits from a random source and Register C
the same size as R which records the number of random options that
can be discriminated among by the bits in R. Both R and C should
be big enough to record the size of the largest set you want to
choose between (eg, if you want to choose among 65536 options, R
and C should be at least 16 bits). <br>
</p>
<p><br>
</p>
<p>Start by initializing R with one "random" bit and initializing C
to the value 2. <br>
</p>
<p><br>
</p>
<p>Whenever you append a new randombit 'r' from the random source,
do <br>
</p>
<p>R = R*2 + r and C = C*2. <br>
</p>
<p><br>
</p>
<p>Whenever you make a choice between K options,</p>
<p>R = R mod K and C = C div K.<br>
</p>
<p><br>
</p>
<p>After initializing once, you can use R and C to generate as many
"random" choices as needed in any set of ranges, whenever enough
bits have been appended that R exceeds the range currently being
chosen. The final wastage is equal to one less than the logarithm
mod 2 of the final value of C. If the minimum number of bits has
been appended, wastage is either one or zero no matter how many
range choices have been made or what size the ranges were.<br>
</p>
<p>Bear</p>
<p><br>
</p>
<p><br>
</p>
</body>
</html>