<!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 12/17/24 02:52, Jerry Leichter
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:F8F9C74B-15FF-4D4F-BD71-A00402D77A65@lrw.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<br>
<div dir="ltr">
<blockquote type="cite">…Whenever you append a new randombit 'r'
from the random source, do</blockquote>
</div>
<blockquote type="cite">
<div dir="ltr">
<p>R = R*2 + r and C = C*2</p>
<p>Whenever you make a choice between K options,</p>
<p>R = R mod K and C = C div K….</p>
</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">
<div><span
style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Something
is missing here. Probably multiple something’s.</span></div>
<div><span
style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br>
</span></div>
</span></blockquote>
<p>You are right. I responded to my own error above, but to clarify
a little more, I got the choice step wrong.</p>
<p>It's the choice, not the new value of R, that's R mod K. <br>
</p>
<p>The new value of R is R div K, and the new value of C is C div
K. </p>
<p>And obviously the choice must be taken before rather than after
adjusting the value of R.</p>
<p>A classic instance of hitting "send" before actually checking my
notebooks. Sorry about that.<br>
</p>
<p><br>
</p>
<p></p>
<p>There's a generalization of the entropy accumulator that allows
adding uniform choices of any size instead of just adding bits.
If you have a generator that generates "random" outputs uniformly
distributed from 0 to N, you would just multiply R and C by N,
rather than 2, before adding it to the accumulator. If you use
the generalized form you need to be sure of the uniformity of the
distribution first. <br>
</p>
<p>The entropy accumulator is a useful construction in that it
limits the "waste" of generated bits under a hard constant, no
matter how many uniformly-distributed random choices you need to
make. But it's rarely justified because most systems have
pseudorandom bit generators that are nearly free to operate.<br>
</p>
<p>Bear</p>
<p><br>
</p>
</body>
</html>