Анализ линейного конгруэнтного генератора неверен?

Таким образом, в попытке лучше понять реализацию 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 меньше, чем фактическая разница. Я делаю что-то явно неправильно?

0

Решение

Разница между новыми семенами действительно 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).

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]