线性同余发生器的分析是错误的？

Question

因此，为了更好地理解 MSVC++ 对 rand 的实现，我重新实现了它并试图更好地理解它（我想一般来说还有 LCG）。

我的实现（几乎完全匹配 MSVC++ 的）如下：

// vc++ impl. of random
// Xn+1 = (aXn + i) mod m
// a = 214013, i = 2531011, m = 32768
unsigned int seed = 0;
unsigned int random()
{
    seed = seed * 214013L + 2531011L;
    // return (seed/(1<<16)) % 32768; (equiv to below)
    return seed>>16 & 0x7FFF;
}

为了找出 2 个种子新生成的种子之间的差异，我认为它只是 (214013*h) % 2^32，其中 h 是 2 个初始种子之间的差异。使用相同的逻辑，我计算出 2 个随机生成的数字之间的差异，初始种子为 x，下一个种子为 x+h，我将这个不同的种子除以 2^16（或移位它正确的 16 位），并去掉了最高有效位。

除了在某些情况下，例如当 x = 100 和 h = 5000 时，此生成的值似乎是正确的。

完整代码如下：

#include <iostream>
#include <cstdlib>

// vc++ impl. of random
// Xn+1 = (aXn + i) mod m
// a = 214013, i = 2531011, m = 32768
unsigned int seed = 0;
unsigned int random()
{
    seed = seed * 214013L + 2531011L;
    return seed>>16 & 0x7FFF;
}

int main()
{
    // f(x) = (214013x + 2531011) mod 2^32 [LCG]
    // g(x) = floor(f(x)/2^16) mod 2^15 [RND]
    // h(x) = f(x + h) - f(x) ?= 214013*h mod 2^32
    // j(x) = g(x + h) - g(x) ?= 214013*h/2^16 mod 2^15

    // x: initial seed
    // h: displaecment to next seed (next seed: x + h)
    // a, b: first and second randomly generated values using C rand
    // c, d: first and second randomly generated values using random
    // newSeedA, newSeedB: seed generated from LCG after x and x + h respectively
    // diffExp: experimental difference in random values
    // diffCalc: calculated/theoretical difference in random vlaues
    unsigned int x = 100, h = 50000;
    unsigned int a, b, c, d;
    unsigned int newSeedA, newSeedB;
    int diffExp, diffCalc;

    srand(x);
    seed = x;
    a = rand();
    c = random();
    newSeedA = seed;

    srand(x + h);
    seed = x + h;
    b = rand();
    d = random();
    newSeedB = seed;

    diffExp = (d - c) % 32768;
    diffCalc = (214013*h)>>16 & 0x7FFF;


    std::cout << "RANDOM VALUES\n";
    std::cout << "  VC++ rand: " << a << ", " << b << "\n";
    std::cout << "Custom rand: " << c << ", " << d << "\n";
    std::cout << "\n";

    std::cout << "DIFFERENCE IN SEED\n";
    std::cout << "Experimental Difference: " << (newSeedB - newSeedA) << "\n";
    std::cout << "  Calculated Difference: " << (static_cast<unsigned int>(214013)*h) << "\n";
    std::cout << "\n";

    std::cout << "DIFFERENCE IN VALUES\n";
    std::cout << "Experimental Difference: " << diffExp << "\n";
    std::cout << "  Calculated Difference: " << diffCalc << "\n";
    std::cout << "\n";
    return 0;
}

然而，对于这些值，2 个随机生成的值之间的估计差值比实际差值小 1。我做错了什么吗？

Answer 1

新种子的区别确实是214013*h。

这给出了种子 s 和 s + 214013*h，生成的随机输出之间的差异将是（在简化之前）diff = ((s + 214013*h >> 16) & 0x7fff) - ((s >> 16) & 0x7fff)。那么问题本质上是，这个表达式是否独立于 s.

不是。例如，即使取 h = 1，diff 也可以是 3（例如 s = 0）或 4（例如 s = 0x0000bc03）。

线性同余发生器的分析是错误的？

Analysis of Linear congruential generator is wrong?

c++

random

lcg

modular-arithmetic