C++ 中的线性同余生成器

Question

我写了一个简单的程序（试图实际实现线性同余生成器），但我不太确定它能正常工作。

我想使用我的生成器从 [0,1] 生成 250 个数字。但是，似乎我得到的不是随机数，而是相等的值..

如何改进/我做错了什么？

代码如下：

#include <iostream>
#include <cmath>

static const double A = 0.001342;
static const double C = 0.00025194;
static const double RAND_MAX = 1.0;

double rand()
{
    static double prev = 0;
    prev = A * prev + fmod(C, RAND_MAX);
    return prev;
}

int main(int argc, char **argv)
{
    for(int i=0; i<6; i++)
    std::cout << rand() << "\n";
    return 0;
}

并且输出：

0.00025194
0.000252278
0.000252279
0.000252279
0.000252279
0.000252279

切换到 int 而不是 double，但是会得到一些不错的结果：

#include <iostream>
#include <cmath>

static const int A = 5;
static const int C = 3;
static const int RAND_MAX = 8;

double rand()
{
    static int prev = 1;
    prev = A * prev + (C % RAND_MAX);
    return prev;
}

int main(int argc, char **argv)
{
    for(int i=0; i<100; i++)
    std::cout << rand() << "\n";
    return 0;
}

输出：

8
43
218
1093
5468
27343
136718
683593
3.41797e+06
1.70898e+07
8.54492e+07
4.27246e+08
2.13623e+09
2.09122e+09
1.86615e+09
7.40836e+08
-5.90786e+08
1.34104e+09
...

但我需要它来生成大于或等于 0 且小于或等于 1 的随机双数:(

Answer 1

不是程序，是选号。

prev 一开始等于零，所以第一个数字变成 C.

然后，prev等于C，这使得prev A*C + C。但是，A*C 太小了，当将它作为浮点数添加到前一个时，有效数字被移出，剩下的就是之前的内容。

您可以在 What Every Computer Scientist Should Know About Floating-Point Arithmetic 上阅读更多内容。

Answer 2

首先，不要对 LCG 使用浮点运算。浮点本质上是不精确的，并且可能导致不良行为，例如定点收敛或交错的短子循环。使用整数运算，数论可以告诉您哪些参数可以保证实现完整循环，即，0 和 M-1 之间的每个值（其中 M 是您的模数）将达到。全周期参数要求见Wikipedia article on LCGs，常用参数见table。

其次，你误解了LCG公式。应该是：

prev = (A * prev + C) % M;

第三，根据您当前选择的参数，您不会运行参与其中，但通常您的中间计算应该使用 long 来避免溢出。 % 运算会将答案带回 int，但如果您坚持使用 int 算术，则乘法可能无法产生数学上正确的值，从而确保完整的周期长度和适当的分布行为。

C++ 中的线性同余生成器

Linear congruential generator in C++

c++

random

generator