根据随机比特流产生随机浮点值 [英] Generating random floating-point values based on random bit stream

问题描述

给定一个随机源（随机比特流的生成），我怎么产生一个给定的范围内均匀分布的随机浮点值？

Given a random source (a generator of random bit stream), how do I generate a uniformly distributed random floating-point value in a given range?

假设我的随机源看起来是这样的：

Assume that my random source looks something like:

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

和我想要实现

double GetRandomVal(double fMin, double fMax);

注：

• 在我不想要的结果precision被限制（例如，只有5位数字）。
• 在严格的均匀分布是必须
• 在我没有要求引用现有的库。我想为知道如何从头开始实现它。
• 对于伪code / code，C ++是最AP preciated

• I don't want the result precision to be limited (for example only 5 digits).
• Strict uniform distribution is a must
• I'm not asking for a reference to an existing library. I want to know how to implement it from scratch.
• For pseudo-code / code, C++ would be most appreciated

推荐答案

我不认为我会永远确信你确实需要，但它很有趣写。

I don't think I'll ever be convinced that you actually need this, but it was fun to write.

#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));
  }
}

这篇关于根据随机比特流产生随机浮点值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！