c - 快速 C 随机 boolean 生成器

Question

我对在 C 中生成快速随机 boolean 值(或等效的伯努利(0.5)随机变量)感兴趣。当然，如果一个人有一个具有良好统计行为的快速随机生成器，那么问题“对随机伯努利(0.5)进行采样” ” 很容易解决:示例 x统一在(0,1)并返回1如果x<0.5 , 0否则。

假设速度是最重要的，现在我有两个问题/考虑因素:

1. 许多随机 double 生成器首先生成一个整数 m统一在一定范围内[0,M]然后简单地返回除法 m/M 。检查是否 m < M/2 不是更快吗？ (这里 M/2 是固定的，所以我们节省了一个分区)

2. 有没有更快的方法？最后，我们在这里要求更少的统计属性:我们可能仍然对很长一段时间感兴趣，但是，例如，我们不关心分布的均匀性(只要大约 50% 的分布)值位于范围的前半部分)。

Answer 1

提取随机数的最后一位可能会造成严重破坏，因为线性同余生成器可以在奇数和偶数之间交替¹。像 clock() & 1 这样的方案也会有可怕的相关平原。

---

考虑一个基于 Donald Kunth 的快速而肮脏的生成器的解决方案:for uint32_t I , 序列

I = 1664525 * I + 1013904223;

和2 * I < I是产生 boolean 图的条件。在这里，我依赖 I 的环绕行为这应该发生一半的时间，并且避免了潜在的昂贵的除法。

测试I <= 0x7FFFFFFF不那么华丽，并且可能更快，但是中点的硬编码并不完全令人满意。

---

¹ 我在这里展示的生成器可以。