James Coglan asked on twitter:

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!

Example

Here’s an example, generating base $5$ digits:

The smallest power of $2$ greater than $5$ is $2^3 = 8$. So take digits from the binary stream three at a time.

There are three unusable numbers we can generate: $5,6,7$. So subtract $5$ from those, giving $0,1$ or $2$, and treat them as digits from a stream of base $3$ digits.

The smallest power of $3$ greater than $5$ is $3^2 = 9$, so take digits from that stream two at a time. Numbers $5,6,7,8$ from that range can’t be used, so subtract $5$ from them, giving $0,1,2$ or $3$, and treat them as base $4$ digits.

The smallest power of $4$ greater than $5$ is $4^2 = 16$, so take digits from that stream two at a time. The offcasts from that stream should be considered as base $16-5 = 11$ digits. $11$ is bigger than $5$ already, so take digits from that stream one at a time.

The offcasts from the base $11$ stream look like base $6$ digits. There’s only one unusable number from that range — $5$ — which doesn’t give you any information, so stop being clever at that point and throw away those numbers.

Now, let’s use the binary stream $110101011111001$

My first three digits give $\operatorname{rand}(0\dots2^3) = 110_2 = 4+2+0 = 6.$ That’s not a base $5$ digit, so add $6-5 = 1$ to the stream of base $3$ digits.

My next three digits give $\operatorname{rand}(0\dots2^3) = 101_2 = 4+0+1 = 5.$ Again, that isn’t a base 5 digit, so add $5-5 = 0$ to the stream of base $3$ digits.

We now have two base 3 digits, $1$ and $0$, which means it yields $\operatorname{rand}(0\dots3^2) = 10_3 = 3+0 = 3$. That’s in the range we want, so yield it.

Now we need to take three more binary digits: $\operatorname{rand}(0\dots2^3) = 011_2 = 0+2+1 = 3.$ That’s in the range we want again, so yield it.

More binary: $\operatorname{rand}(0\dots2^3) = 111_2 = 4+2+1 = 7.$ Too big, so add $7-5 = 2$ to the base $3$ stream.

$\operatorname{rand}(0\dots2^3) = 001_2 = 1.$ That’s fine, so yield it.

At the moment, our stream of base $5$ digits is $[3,3,1]$ and we have a $2$ in the stream of base $3$ digits. We can keep generating numbers like this indefinitely, and we hardly ever throw information away. It would probably take a lot more steps to get to the point where we use the bigger accumulators.

Working code

I’ve written some Python code which implements the algorithm above to produce an infinite stream of digits of any base, from a stream of binary digits provided by Python’s random module.

The Python code has some debug lines in it – turn those on to get a narration of what it does.

I hope that answers your question, James!

I should mention that this method is based on the first bit of this page. I couldn’t think of the right words to use to find a proper crypto textbook on the subject, which must surely exist.