基于随机比特生成非2的幂范围随机数的最优算法探讨

一、存在更优的算法 #

原算法每次抽取10比特，若数值在0-999范围内就直接使用，否则丢弃重抽，平均消耗比特数约为10.24。可以通过利用拒绝采样的剩余随机信息来优化，大幅降低平均消耗的比特数：

• 当抽到的10比特值落在1000-1023之间时（共24种可能），不要直接丢弃这10比特，而是计算Y = X - 1000（Y的范围是0-23），这相当于保留了约4.58比特的有效随机信息；
• 接下来抽取6比特得到Z（范围0-63），组合成新的数值N = Y * 64 + Z，此时N的范围是0-1535；
  • 若N < 1000，直接输出N，累计消耗16比特；
  • 若N ≥ 1000，计算M = N - 1000（M的范围是0-535），保留M并继续抽取新的比特，重复上述组合、判断的过程。
    这种方法能让每次拒绝采样的随机信息都得到复用，平均消耗的比特数会非常接近生成1000种均匀结果的理论下限（约9.97比特），比原算法更高效。

二、不存在能保证消耗有限比特的算法 #

从数学和概率的角度来说，没有任何算法能绝对保证在有限比特内生成符合要求的随机数。因为随机过程本身具有概率性，哪怕优化后的算法效率极高，也存在极小的概率会一直遇到需要继续采样的情况（比如原算法一直抽到1000-1023，或者优化算法一直遇到组合值超过阈值的情况）——虽然这种无限循环的可能性趋近于0，但理论上无法完全排除，因此没法给出“一定只用有限比特就能完成”的保证。

内容的提问来源于stack exchange，提问作者fadedbee