Converting a stream of binary digits to a stream of base \(n\) digits
James Coglan asked on twitter:
https://twitter.com/jcoglan/status/212163174626115584
https://twitter.com/jcoglan/status/212163325579108353
So you have an infinite stream of uniform random binary digits, and want to use it to produce an infinite stream of uniform random base \(n\) digits.
The obvious really easy way to do it is to find the smallest \(k\) such that \(2^k>=n\), and generate numbers in the range \(0 \dots 2^k-1\).
If the number you generate is less than \(n\), yield it, otherwise chuck it away.
This works, but has the problem that you might go a long time before you generate a number that you don’t throw away.
So what can we do with the numbers that are thrown away?
Subtract \(n\) from them, and use them as a stream of infinite base \((2^k-n)\) digits.
You can then do the same trick of generating enough of those digits until you can generate numbers greater than or equal to \(n\). Numbers less than \(n\) are yielded; otherwise, the trick is repeated yet again!