線形合同ジェネレータの解析が間違っていますか？

Question

したがって、randのMSVC++の実装をよりよく理解しようとすると、私はそれを再実装し、それをよく理解しようとしました（一般的には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だろう考え出し2つの初期種子。この同じロジックを使用して、最初の種がx、次の種がx+hとランダムに生成された2つの数字の差を計算しました。これを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）のいずれかになります。