The Objective
Build a random number generator whose range is \$\left[0,1\right) \cap \mathbb{Q} .\$
This is, build a random number generator that can produce any value that's:
at least \$0 \,;\$
not \$1\$ or greater; and
expressible as the ratio of two integers.
What's the fuss?
This RNG is weird. Its range is nowhere connected, but is dense in the interval!
The probability mass function
We define an ordering for all values that the RNG can return, such that each return value \$ x\$ can be associated with an index \$ i .\$ Then, the probability of returning \$x_i\$ should be \$P\left(x_i\right) = {\left(\frac{1}{2}\right)}^{i} .\$ Since $$ \sum\limits_{i=1}^{\infty}{{\left(\frac{1}{2}\right)}^{i}} = 1 \,, $$ this yields a total probability of \$1 ,\$ where the numbers earlier in the ordering are significantly more likely than numbers later in the ordering.
The ordering is:
Start with the first value, \$ \frac{0}{1}.\$
Increment the numerator.
If the numerator equals the denominator, then:
reset the numerator to \$ 0 ;\$ and
increment the denominator.
Add the value to the ordering if it's not equivalent to a value already in the ordering.
- For example, \$\frac{2}{4}\$ is constructed after \$\frac{1}{2} ,\$ so it's not added to the ordering.
Go back to Step (2).
For example, the first few values and their corresponding probabilities are: $$ \begin{array}{r|c|c|c|c|c|c|c|c|c|c} \textbf{Index}~\left(i\right) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \cdots \\\hline \textbf{Value}~\left(x\right) & \frac{0}{1} & \frac{1}{2} & \frac{1}{3} & \frac{2}{3} & \frac{1}{4} & \frac{3}{4} & \frac{1}{5} & \frac{2}{5} & \frac{3}{5} & \frac{4}{5} & \cdots \\\hline \textbf{Probability}~\left(P\right) & \frac{1}{ 2} & \frac{1}{ 4} & \frac{1}{ 8} & \frac{1}{ 16} & \frac{1}{ 32} & \frac{1}{ 64} & \frac{1}{ 128} & \frac{1}{ 256} & \frac{1}{ 512} & \frac{1}{1024} & \cdots \end{array} _{\large{.}} $$
Rules
There is no input. The RNG outputs a number upon invocation.
You must use rational number arithmetic. In particular,
X
must be represented as a rational number. If your language doesn't natively support it, use a pair of integers. For example, in Haskell,Rational
is a valid type.As long as the numerator and the denominator are distinguishable, the output format doesn't matter.
As this is a code-golf, the shortest code in bytes wins.
X
, not just an examples from which we are supposed to infer that. See Things to avoid when writing challenges. \$\endgroup\$(2^100)/(2^100+3)
and(2^100+1)/(2^100+3)
are hardly distinguishable through single- or double-precision FP. \$\endgroup\$uint64
, there is a value above which integer numbers are indistinguishable. Usingfloat
instead ofuint64
simply moves down the threshold from2^64
to2^53
\$\endgroup\$