c++ - 特殊的简单随机数发生器

Question

如何创建一个函数，每次调用都会生成一个随机整数？该数字必须尽可能随机(根据 uniform distribution )。只允许使用一个静态变量和最多 3 个基本步骤，其中每个步骤只包含一个 arity 的基本算术运算。 1 或 2。

例子:

int myrandom(void){
  static int x;
  x = some_step1;
  x = some_step2;
  x = some_step3;
  return x;
}

基本的算术运算是+、-、%、and、not、xor、or、左移、右移、乘法和除法。当然，不允许使用 rand()、random() 或类似的东西。

Answer 1

Linear congruential generators 是最古老和最简单的方法之一:

int seed = 123456789;

int rand()
{
  seed = (a * seed + c) % m;
  return seed;
}

只有几 strip 有基本算术运算的指令，这就是你所需要的。

请注意，此算法只有在以特定方式选择 a、c 和 m 时才能正常工作!

为了保证这个序列的最长周期，c和m应该互素，a-1应该能被所有素数整除m 的因数，如果 m 能被 4 整除，也适用于 4。

Wikipedia 上显示了一些 examples of parameters:例如，某些编译器的 ANSI C 建议 m = 2³¹、a = 1103515245 和 c = 12345.