快速C随机布尔生成器 [英] Fast C random boolean generator

问题描述

我对在C语言中生成快速随机布尔值(或等效地为Bernoulli(0.5)随机变量)感兴趣.当然，如果具有快速随机生成器且具有良好的统计行为，则问题为对随机Bernoulli(0.5)进行采样"很容易解决:在(0,1)中均匀采样x，如果x<0.5则返回1，否则返回0.

I'm interested in generating fast random booleans (or equivalently a Bernoulli(0.5) random variable) in C. Of course if one has a fast random generator with a decent statistical behaviour the problem "sample a random Bernoulli(0.5)" is easily solved: sample x uniformly in (0,1) and return 1 if x<0.5, 0 otherwise.

假设速度是最重要的，现在我有两个问题/注意事项:

Suppose speed is the most important thing, now I have two questions/considerations:

1. 许多随机双精度生成器首先在某个范围[0,M]中均匀地生成一个整数m，然后简单地返回除法m/M.只是检查m < M/2(这里的M/2是固定的，所以我们要保存一个除法)是否更快?

1. Many random doubles generators first generate an integer m uniformly in a certain range [0,M] and then simply return the division m/M. Wouldn't it be faster just to check whether m < M/2 (here M/2 is fixed, so we are saving one division)

1. 有没有更快的方法呢?最后，我们在这里要求减少统计属性的方式:我们可能仍然对很长一段时间感兴趣，例如，我们不在乎分布的均匀性(只要大约50％值在范围的前半部分).

推荐答案

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

Extracting say the last bit of a random number can wreak havoc as linear congruential generators can alternate between odd and even numbers¹. A scheme like clock() & 1 would also have ghastly correlation plains.

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

Consider a solution based on the quick and dirty generator of Donald Kunth: for uint32_t I, sequence

I = 1664525 * I + 1013904223;

和2 * I < I是产生布尔图形的条件.在这里，我依靠I的环绕行为，该行为应该发生一半的时间，并且避免了潜在的昂贵划分.

and 2 * I < I is the conditional yielding the Boolean drawing. Here I'm relying on the wrap-around behaviour of I which should occur half the time, and a potentially expensive division is avoided.

测试I <= 0x7FFFFFFF的浮华性较低，但仍可能会更快，但是中点的硬编码并不完全令人满意.

Testing I <= 0x7FFFFFFF is less flashy and might be faster still, but the hardcoding of the midpoint is not entirely satisfactory.

¹ 我在这里介绍的发电机可以.

¹ The generator I present here does.

这篇关于快速C随机布尔生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！