An optimal algorithm for bounded random integers
I&#x27;m a bit confused about this method.<p>So the standard argument against such a procedure is that if you generate N random bits, each of {0,1}^N bitstrings is equiprobable and therefore no mapping of {0,1}^N to {0..U-1} can map an equal number of bitstrings to each output.<p>A priori the method seems to work around this by conditionally sampling more bits, so that your domain is not one of fixed-length bitstrings. But then there is this paragraph:<p>&gt; More intriguing still, this algorithm can be made unconditional by removing the early out, so that every value computed requires word size + 64 bits from the stream, which breaks the loop-carried dependency for fast generators, unlocking vectorization and parallelization where it was previously impossible. This is an especially powerful advantage when paired with bitstream generators that allow skip-ahead such as counter-based generators or PCG.<p>But now we are mapping {0, 1}^N into {0..U-1} right? So this mapping ought not be uniform? In fact I&#x27;m not sure why the early-termination method even works, because for a fixed U we know the maximum depth of the generated-bitstring-tree, so we can just pad it with imaginary random bits to arrive at the contradiction that U does not divide 2^N.<p>I imagine I missed something, what is it?<p>EDIT: thinking about it more, if you sample finitely many bits then each possible output has a probability that is a dyadic rational (fractions of the form a&#x2F;2^k) which does not include all integer reciprocals.