关于随机整数生成的准则（C）

Question

我是运行一堆需要随机数的物理模拟。我在 C++ 中使用标准 rand() 函数。

所以它是这样工作的：首先我预先计算了一组 1/(1+exp(a)) 形式的概率，用于一组不同的 a。它们是 double 类型，由 math 库中的 exp 函数返回，然后事情必须以这些概率发生，只有两个，所以我生成一个随机数数均匀分布在 0 和 1 之间，并与那些预先计算的概率进行比较。为此，我使用了：

double p = double(rand()%101)/100.0;

所以我得到了介于 0 和 1 之间的随机值。这并没有产生正确的物理结果。我试过这个：

double p = double(rand()%1000001)/1000000.0;

这奏效了。我真的不明白为什么，所以我想要一些关于如何做的标准。我的直觉告诉我，如果我这样做

double p = double(rand()%(N+1))/double(N);

N 足够大，使得最小除法 (1/N) 远小于最小概率 1/1+exp(a) 那么我将得到真实的随机数。

虽然我想明白为什么。

Answer 1

rand() returns 0 到 RAND_MAX 之间的随机数。

因此你需要这个：

double p = double(rand() % RAND_MAX) / double(RAND_MAX);

还有运行这个片段，你会明白：

  int i;

  for (i = 1; i < 30; i++)
  {
      int rnd = rand();
      double p0 = double(rnd % 101) / 100.0;
      double p1 = double(rnd % 1000001) / 1000000.0;
      printf ("%d\t%f\t%f\n", rnd, p0, p1);
  }

  for (i = 1; i < 30; i++)
  {
      int rnd = rand();
      double p0 = double(rnd) / double(RAND_MAX);
      printf ("%d\t%f\n", rnd, p0);
  }

Answer 2

您有多个问题。

rand() 一点也不随机。在几乎所有的操作系统上，它 returns 分布不均，数字偏差严重。实际上很难找到一个好的随机数生成器，但我可以向您保证 rand() 将是您能找到的最差的随机数生成器之一。
rand() % N 给出了有偏分布。想想鸽巢原理。我们简化一下，假设rand returns numbers [0,7) 而你的N是6。0到5映射到0到5，6映射到0，7映射到1，也就是说0和1是两次很有可能出来。
在除法之前将数字转换为双倍不会消除 2 的偏差，它只会使其不那么明显。无论您进行何种转换，鸽笼原理都适用。
将分布良好的随机数从整数转换为 float/double 比看起来要难。简单除法忽略了浮点数学运算的问题。

1我帮不了你太多，你需要做研究。在网上四处寻找随机数库。如果你想要非常随机和不可预测的东西，你需要寻找加密随机库。如果您想要一个可重复但良好的随机数 Mersenne Twister 应该足够好。但是你需要在这里做研究。

对于 2 和 3 有标准解决方案。您正在将一个集合从 M 个元素映射到 N 个元素，并且 rand % N 仅当 N < M 且 N 和 M 共享质因数时才有效。由于在大多数系统上 M 将是 2 的幂，这意味着 N 也必须是 2 的幂。所以假设 M 是 2 的幂，算法是：找到最近的大于或等于 N 的 2 的幂，我们称它为 P。生成 randomness_source() % P。如果数字高于 N，则将其丢弃并重试。这是执行此操作的唯一安全方法。比你我更聪明的人已经在这个问题上花费了很多年，没有更好的方法来消除偏见。

对于4，你可以忽略这个问题而直接除法，在绝大多数情况下这应该足够好了。如果你真的想研究这个问题，我已经做了一些工作并发布了代码 on github. 在那里我将介绍一些关于浮点数如何工作以及它如何与生成随机数相关的基本原理。

Answer 3

// produces pseudorandom bits.  These are NOT crypto quality bits.  Has the same underlying unpredictability as uncooked
// rand() output.  It buffers rand() bits to produce a more convenient zero-to-the-argument range including negative
// arguments, corrects for the toward-zero bias of the modular construction I'd be using otherwise, eliminates the
// RAND_MAX range limitation, (use INT64_MAX instead) and effectively obscures biases and sequence telltales due to
// annoyingly bad rand libraries.  It does not correct these biases; anyone tracking the arguments and outputs has
// enough information to reconstruct the rand() output and detect them.  But it makes the relationships drastically more complicated.

// needs stdint, stdlib.

int64_t privaterandom(int64_t range, int reset){
    static uint64_t state = 0;
    int64_t retval;
    if (reset != 0){
       srand((unsigned int)range);
       state = (uint64_t)range;
    }
    if (range == 0) return (0);
    if (range < 0) return -privaterandom(-range, 0);
    if (range > UINT64_MAX/0xFFFFFFFF){
       retval = (privaterandom(range/0xFFFFFFFF, 0) * 0xFFFFFFFF); // order of operations matters
       return (retval + privaterandom(0xFFFFFFFF, 0));
    }
    while (state < UINT64_MAX / 0xFF){
       state *= RAND_MAX;
       state += rand();
    }
    retval = (state % range);
    // makes "pigeonhole" bias alternate unpredictably between toward-even and toward-odd
    if ((state/range > (state - (retval) )/ range) && state % 2 == 0) retval++; 
    state /= range;
    return retval;
}
int64_t Random(int64_t range){ return (privaterandom(range, 0));}
int64_t Random_Init(int64_t seed){return (privaterandom(seed, 1));}

关于随机整数生成的准则（C）

About a criteria for random integers number generation (C)

c

random