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.

[gist id=2911970 file=basestream.py]

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