小编o90*_*000的帖子

通常,随机数发生器返回比特流,对于该比特流,在每个位置观察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相同的性能.

编辑3月5日

谢谢大家的建议,我收到了很多有趣的想法和建议.以下是最重要的:

• 更改问题要求,使p的分辨率为1/256而不是1/200.这允许更有效地使用比特,并且还提供更多优化机会.我想我可以做出这个改变.
• 使用算术编码有效地消耗来自无偏生成器的位.通过上述分辨率的变化,这变得更容易.
• 一些人认为PRNG非常快,因此使用算术编码实际上可能会因为引入的开销而使代码变慢.相反,我应该总是消耗最坏情况下的位数并优化该代码.请参阅下面的基准.
• @rici建议使用SIMD.这是个好主意,只有在我们总是消耗固定数量的位时才有效.

基准(无算术解码)

注意:正如你们许多人建议的那样,我将分辨率从1/200更改为1/256.

我写了几个朴素方法的实现,只需要8个随机无偏位并生成1个偏置位:

• 没有SIMD
• 使用Agner Fog的vectorclass库的SIMD,正如@rici所建议的那样
• 使用内在函数的SIMD

我使用两个无偏的伪随机数生成器:

• xorshift128plus
• 来自Agner Fog图书馆的Ranvec1(Mersenne Twister-like).

我还测量了无偏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 …