通常,随机数发生器返回比特流,对于该比特流,在每个位置观察0或1的概率相等(即50%).让我们称之为无偏见的PRNG.
我需要生成一串具有以下属性的伪随机位:在每个位置看到1的概率是p(即看到0的概率是1-p).参数p是0到1之间的实数; 在我的问题中,它的分辨率为0.5%,即它可以取值0%,0.5%,1%,1.5%,......,99.5%,100%.
请注意,p是概率而不是精确分数.在n比特流中设置为1的实际比特数必须遵循二项分布B(n,p).
有一种天真的方法可以使用无偏PRNG来生成每个比特的值(伪代码):
generate_biased_stream(n, p):
result = []
for i in 1 to n:
if random_uniform(0, 1) < p:
result.append(1)
else:
result.append(0)
return result
这种实现比生成无偏流的实现要慢得多,因为它每个位调用一次随机数生成器函数; 而无偏流生成器每字大小调用一次(例如,它可以通过一次调用生成32或64个随机位).
我想要更快的实现,即使它稍微牺牲了随机性.想到的一个想法是预先计算查找表:对于p的200个可能值中的每一个,使用较慢的算法计算C 8位值并将它们保存在表中.然后快速算法将随机选择其中一个以生成8个偏斜位.
包络计算的背面,以查看需要多少内存:C应至少为256(可能的8位值的数量),可能更多以避免采样效果; 比方说,1024也许数量应具体取决于p各不相同,但让我们保持它的简单,说平均为1024由于是p的200个值=>总内存为200 KB.这不错,可能适合L2缓存(256 KB).我仍然需要对它进行评估,以确定是否存在引入偏差的采样效应,在这种情况下,必须增加C.
该解决方案的不足之处是,它可以一次生成只有8位,甚至有大量的工作,而一个不带偏见PRNG可以生成64只有几个算术指令一次.
我想知道是否有一种更快的方法,基于位操作而不是查找表.例如,直接修改随机数生成代码以为每个位引入偏差.这将实现与无偏PRNG相同的性能.
谢谢大家的建议,我收到了很多有趣的想法和建议.以下是最重要的:
注意:正如你们许多人建议的那样,我将分辨率从1/200更改为1/256.
我写了几个朴素方法的实现,只需要8个随机无偏位并生成1个偏置位:
我使用两个无偏的伪随机数生成器:
我还测量了无偏PRNG的速度以进行比较.结果如下:
RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)
Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 16.081 …Apple已将大多数(但不是全部)OpenSSL API标记为MacOS 10.7中的"已弃用".Apple是否有任何声明解释他们为何从OpenSSL转向Common Crypto？
考虑一种算法来测试在特定次数的尝试之后从一组N个唯一数字中挑选某个数字的概率(例如,N = 2,轮盘中的概率是什么(没有0),它需要X尝试黑赢？)
对此的正确分布是pow(1-1/N,X-1)*(1/N).
但是,当我使用以下代码对其进行测试时,在X = 31处始终存在深沟,独立于N,并且独立于种子.
这是一个内在的缺陷,由于PRNG的实施细节在使用中无法防止,这是一个真正的错误,还是我忽略了一些明显的东西？
// C
#include <sys/times.h>
#include <math.h>
#include <stdio.h>
int array[101];
void main(){
int nsamples=10000000;
double breakVal,diffVal;
int i,cnt;
// seed, but doesn't change anything
struct tms time;
srandom(times(&time));
// sample
for(i=0;i<nsamples;i++){
cnt=1;
do{
if((random()%36)==0) // break if 0 is chosen
break;
cnt++;
}while(cnt<100);
array[cnt]++;
}
// show distribution
for(i=1;i<100;i++){
breakVal=array[i]/(double)nsamples; // normalize
diffVal=breakVal-pow(1-1/36.,i-1)*1/36.; // difference to expected value
printf("%d %.12g %.12g\n",i,breakVal,diffVal);
}
}
使用libc6软件包2.15-0ubuntu20和Intel Core i5-2500 SandyBridge测试了最新的Xubuntu 12.10,但几年前我在一台较旧的Ubuntu机器上发现了这一点.
我也在Windows 7上使用Unity3D/Mono进行了测试(虽然不确定哪个Mono版本),这里使用System.Random时,X = 55时沟渠发生,而Unity内置的Unity.Random没有可见的沟渠(至少没有)对于X …
在[0,n)中选择随机数的一种常用方法是采用rand()模n的结果:rand() % n.但是,即使可用rand()实现返回的结果完全一致,当n = n均匀分配时,结果[0,n]数的均匀性是否应该存在问题？例如假设为2,n为2.然后,在3个可能的输出中:0,1和2,当我们使用模n时,我们分别得到0,1和0 .因此输出将根本不是均匀的.RAND_MAX + 1RAND_MAXrand()
这在实践中是一个真正的问题吗？选择[0,n]中的随机数是一种更好的方法,从rand()输出中均匀推导出来,最好没有任何浮点运算？