StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Your solution is correct, if somewhat inefficient and with more duplicated logic. Here is a Python implementation of the same algorithm in a cleaner form.</p> <pre><code>def g (): while True: a = f() if a != f(): return a </code></pre> <p>If f() is expensive you'd want to get more sophisticated with using the match/mismatch information to try to return with fewer calls to it. Here is the most efficient possible solution.</p> <pre><code>def g (): lower = 0.0 upper = 1.0 while True: if 0.5 < lower: return 1 elif upper < 0.5: return 0 else: middle = 0.25 * lower + 0.75 * upper if 0 == f(): lower = middle else: upper = middle </code></pre> <p>This takes about 2.6 calls to <code>g()</code> on average.</p> <p>The way that it works is this. We're trying to pick a random number from 0 to 1, but we happen to stop as soon as we know whether the number is 0 or 1. We start knowing that the number is in the interval (0, 1). 3/4 of the numbers are in the bottom 3/4 of the interval, and 1/4 are in the top 1/4 of the interval. We decide which based on a call to <code>f(x)</code>. This means that we are now in a smaller interval.</p> <p>If we wash, rinse, and repeat enough times we can determine our finite number as precisely as possible, and will have an absolutely equal probability of winding up in any region of the original interval. In particular we have an even probability of winding up bigger than or less than 0.5.</p> <p>If you wanted you could repeat the idea to generate an endless stream of bits one by one. This is, in fact, provably the most efficient way of generating such a stream, and is the source of the idea of <em>entropy</em> in information theory.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload