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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.49694401025772095, "perplexity": 368.91434880567357}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-43/segments/1508187821017.9/warc/CC-MAIN-20171017091309-20171017111309-00608.warc.gz"}