非常基本的问题,但我似乎无法在 Google 上找到答案。标准 PRNG 将生成一系列随机位。我将如何使用它来生成一系列随机整数,这些随机整数在 [0, N) 范围内具有均匀的概率分布?此外,每个整数应使用(期望值)log_2(N) 位。
最佳答案
如果你想要一个介于 1 和 N 之间的随机数:
您计算将 N 转换为二进制数需要多少位。那是:
n_bits = ceiling(log_2(N))
其中 ceiling 是“向上舍入”操作。 (例如:天花板(3)= 3,天花板(3.7)= 4)
您选择随机二进制列表的前 n_bit 并将它们更改为十进制数。
如果您的十进制数大于 N,那么...您可以丢弃它并使用 n_bits 下一位再次尝试,直到它起作用为止。
N = 12 的例子:
n_bits = ceiling(log_2(12)) = 4
您取随机位序列的前 4 位,可能是“1011”
您将“1011”转换为十进制数,得到 13。高于 12,不好。所以:
取随机序列中接下来的 4 位,可能是“1110”。
将“1110”转换为小数,得到 7。行得通!
希望对您有所帮助。
关于algorithm - 从随机位序列生成随机整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25235171/