基于随机比特流生成随机浮点值

Question

给定随机源(随机比特流的生成器),如何在给定范围内生成均匀分布的随机浮点值？

假设我的随机源看起来像:

unsigned int GetRandomBits(char* pBuf, int nLen);

我想实施

double GetRandomVal(double fMin, double fMax);

笔记:

• 我不希望限制结果精度(例如只有5位数).
• 严格的统一分配是必须的
• 我不是要求提供对现有库的引用.我想知道如何从头开始实现它.
• 对于伪代码/代码,C++将是最受欢迎的

Answer 1

我不认为我真的会相信你真的需要这个,但写作很有趣.

#include <stdint.h>

#include <cmath>
#include <cstdio>

FILE* devurandom;

bool geometric(int x) {
  // returns true with probability min(2^-x, 1)
  if (x <= 0) return true;
  while (1) {
    uint8_t r;
    fread(&r, sizeof r, 1, devurandom);
    if (x < 8) {
      return (r & ((1 << x) - 1)) == 0;
    } else if (r != 0) {
      return false;
    }
    x -= 8;
  }
}

double uniform(double a, double b) {
  // requires IEEE doubles and 0.0 < a < b < inf and a normal
  // implicitly computes a uniform random real y in [a, b)
  // and returns the greatest double x such that x <= y
  union {
    double f;
    uint64_t u;
  } convert;
  convert.f = a;
  uint64_t a_bits = convert.u;
  convert.f = b;
  uint64_t b_bits = convert.u;
  uint64_t mask = b_bits - a_bits;
  mask |= mask >> 1;
  mask |= mask >> 2;
  mask |= mask >> 4;
  mask |= mask >> 8;
  mask |= mask >> 16;
  mask |= mask >> 32;
  int b_exp;
  frexp(b, &b_exp);
  while (1) {
    // sample uniform x_bits in [a_bits, b_bits)
    uint64_t x_bits;
    fread(&x_bits, sizeof x_bits, 1, devurandom);
    x_bits &= mask;
    x_bits += a_bits;
    if (x_bits >= b_bits) continue;
    double x;
    convert.u = x_bits;
    x = convert.f;
    // accept x with probability proportional to 2^x_exp
    int x_exp;
    frexp(x, &x_exp);
    if (geometric(b_exp - x_exp)) return x;
  }
}

int main() {
  devurandom = fopen("/dev/urandom", "r");
  for (int i = 0; i < 100000; ++i) {
    printf("%.17g\n", uniform(1.0 - 1e-15, 1.0 + 1e-15));
  }
}

Answer 2

这是一种做法.

IEEE Std 754双格式如下:

[s][     e     ][                          f                         ]

其中s是符号位(1位),e是偏置指数(11位),f是小数(52位).

请注意,在小端机器上,内存中的布局会有所不同.

对于0 <e <2047,表示的数字是

(-1)**(s)   *  2**(e – 1023)  *  (1.f)

通过将s设置为0,e到1023以及从比特流中选择f到52个随机位,您将在区间[1.0,2.0]中获得随机加倍.这个区间是独特的,因为它包含2**52个双打,并且这些双精度是等距的.如果然后从构造的double中减去1.0,则在区间[0.0,1.0]中得到一个随机双精度数.而且,保持等距的属性.从那里你应该能够根据需要进行缩放和翻译.