均匀分布的位序列 [英] Uniformly distributed bit sequence
问题描述
假设您有一个常规数字生成器，它能够生成均匀分布的随机 32 位数字.假设您正在寻找一种方法来生成位的伪随机序列，其中 1(即设置位)以预定义的概率出现在序列中.
Suppose you have a regular number generator which is able to produce uniformly distributed random 32 bit numbers. And suppose you look for a way to generate a pseudo-random sequence of bits where ones (i.e., the set bits) appear in the sequence with predefined probability.
产生这种序列的一种天真的方法是在每个位级别上运行数字生成器，但是对于小概率(例如序列中的 0.01 或 1% 的位的大部分位为零)来说，它的效率非常低.平均只会设置一百分之一.另一方面，即使概率如此低，也有可能遇到超出 8、16、32、64 位的连续序列的长子序列.
A naive way of producing such sequence would be running number generator on per bit level but it's terribly inefficient for small probabilities like 0.01 or 1% of bits in the sequence most of the bits will be zero. On average just one bit in a hundred would be set. On the other hand even with such low probability there's a chance to encounter a long sub-sequence of consecutive ones that extends beyond the 8, 16, 32, 64 bits.
问题是如何使用常规 PRNG 有效地生成这样的序列.
The question is how to produce such sequence efficiently using regular PRNG.
编辑
Peter O. 建议的 JavaScript 中理性伯努利变量采样的玩具实现:
A toy implementation of rational Bernoulli variable sampling in javascript suggested by Peter O.:
// Based on
// https://arxiv.org/abs/1304.1916
// https://arxiv.org/pdf/1304.1916.pdf (page 21, figure 6)
class Xor128 {
constructor(x, y, z, w) {
this.x = x;
this.y = y;
this.z = z;
this.w = w;
}
prev() {
var t = this.w ^ this.z ^ (this.z >>> 19);
t ^= t >>> 8;
t ^= t >>> 16;
this.w = this.z;
this.z = this.y;
this.y = this.x;
t ^= t << 11;
t ^= t << 22;
this.x = t;
return this.w;
}
curr() {
return this.w;
}
next() {
var t = this.x ^ (this.x << 11);
this.x = this.y;
this.y = this.z;
this.z = this.w;
return this.w = this.w ^ (this.w >>> 19) ^ (t ^ (t >>> 8));
}
}
function* flip(xor128) {
while (true) {
var value = xor128.next();
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
yield value & 1; value >>>= 1;
}
}
function* bernoulli(flip, k, n) {
var b;
var v = k
for (const bit of flip) {
v <<= 1;
if (v >= n) {
v -= n;
b = 1;
} else {
b = 0;
}
if (bit === 1) {
yield b;
v = k;
}
}
}
var xor128 = new Xor128(1, 2, 3, 4);
var z = 0, o = 0;
var then = Date.now();
for (const value of bernoulli(flip(xor128), 5, 1000)) {
if (value === 0) {
z++;
} else {
o++;
}
if (Date.now() - then > 1000) {
console.log(`${z} ${o}`);
}
}
// Pieces of code to test out xor128:
//
// for (let index = 0; index < 100; index++) {
// console.log(xor128.curr())
// xor128.next();
// }
// console.log('-----------------------------------')
// for (let index = 0; index < 100; index++) {
// xor128.prev();
// console.log(xor128.curr())
// }
另一个编辑
下面的代码是用 C# 实现的，每秒产生 9120 万比特，打包成 UInt32 数据类型(MacBookPro 2019 Core I9 2.4 Ghz).我认为在 C 中可能会超过 1 亿位，而且感觉有可能进一步利用二进制算法来并行生成所有 32 位的随机数，一些循环展开或者 SIMD 不确定，无论如何这里是代码:
The code below is implemented in C# produces 91.2 million bits per second packed into UInt32 data type (MacBookPro 2019 Core I9 2.4 Ghz). I think in C it'd be possible to get over 100 million bits, also it feels like it is possible to further utilize binary arithmetic to generate all 32 bits of random number in parallel, some loop unrolling or maybe SIMD not sure, anyway here's the code:
public class Bernoulli
{
public UInt32 X { get; set; }
public UInt32 Y { get; set; }
public UInt32 Z { get; set; }
public UInt32 W { get; set; }
public Bernoulli()
: this(Guid.NewGuid())
{
}
public Bernoulli(Guid guid)
{
var index = 0;
var bytes = guid.ToByteArray();
X = (UInt32)((bytes[index++] << 24) | (bytes[index++] << 16) | (bytes[index++] << 8) | bytes[index++]);
Y = (UInt32)((bytes[index++] << 24) | (bytes[index++] << 16) | (bytes[index++] << 8) | bytes[index++]);
Z = (UInt32)((bytes[index++] << 24) | (bytes[index++] << 16) | (bytes[index++] << 8) | bytes[index++]);
W = (UInt32)((bytes[index++] << 24) | (bytes[index++] << 16) | (bytes[index++] << 8) | bytes[index++]);
}
public Bernoulli(UInt32 x, UInt32 y, UInt32 z, UInt32 w)
{
X = x;
Y = y;
Z = z;
W = w;
}
UInt64 bits = 0;
UInt32 bitsCount = 0;
public UInt32 Next(UInt32 k, UInt32 n)
{
UInt32 b;
var c = 0;
var v = k;
var r = 0u;
// ------------------------
do
{
while (bitsCount <= 32)
{
b = X ^ (X << 11);
X = Y;
Y = Z;
Z = W;
bits <<= 32;
bits |= ((UInt64)(W = W ^ (W >> 19) ^ (b ^ (b >> 8))));
bitsCount += 32;
}
while (c < 32 && 0 < bitsCount)
{
v <<= 1;
// Two lines of code below is a two step optimization:
// First we optimize the following statement:
//
// if (v >= n)
// {
// v -= n;
// b = 1;
// }
// else
// {
// b = 0;
// }
//
// into the following:
//
// var b = v < n ? 0u : 1u;
// v -= b * n
//
// thus reducing branching, but we would like also to omit
// multiplication, which we can do through:
b = v < n ? 0u : 0xFFFFFFFFu;
v -= b & n;
if ((bits & 1) == 1)
{
r |= b & 1;
r <<= 1;
v = k;
c++;
}
bits >>= 1;
bitsCount--;
}
} while (c < 32);
return r;
}
}
推荐答案
这个问题可以重新表述为:
This problem can be restated as:
- 在区间 [0, N] 中生成一个随机整数.
- 如果整数为 0，则输出 1，否则输出 0.
有多种方法可以生成从随机位开始的范围内的随机整数溪流.其中，J. Lumbroso 展示了在给定随机比特流的情况下解决此问题的最佳方法("Optimal Discrete Uniform Generation from硬币翻转和应用"，2013 年).(但是，该论文的附录 B 也指出了您直接问题的解决方案:以给定的概率生成 0 或 1.)其他方法包括有效地生成范围内的随机数" 以及全新的算法，"快速加载骰子滚轮".
There are various ways to generate random integers in a range from a random bit stream. Of these, J. Lumbroso showed an optimal way to solve this problem given a random bit stream ("Optimal Discrete Uniform Generation from Coin Flips, and Applications", 2013). (However, Appendix B of that paper also points out a solution to your direct problem: generating 0 or 1 with a given probability.) Other ways include those mentioned in "Efficiently Generating a Random Number in a Range" as well as a brand-new algorithm, the "Fast Loaded Dice Roller".
这篇关于均匀分布的位序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
