特殊的简单随机数发生器

Question

如何创建一个函数,在每个调用中生成一个随机整数？该数字必须尽可能最随机(根据均匀分布).它只允许使用一个静态变量和最多3个基本步骤,其中每个步骤仅包含arity 1或2的一个基本算术运算.

例:

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

基本算术运算是+, - ,%,而不是xor,或左移,右移,乘法和除法.当然,不允许使用rand(),random()或类似的东西.

Answer 1

线性同余生成器是最古老和最简单的方法之一:

int seed = 123456789;

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

只需要几条带基本算术运算的指令,这就是你所需要的.

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

为了保证这个序列的最长可能周期,c和m应该是互质的,a  - 1应该可以被m的所有素因子整除,并且如果m可以被4整除则也是4.

维基百科上显示了一些参数示例:例如,某些编译器的ANSI C建议m =2³¹ ,a = 1103515245和c = 12345.

我尝试了这个算法,提出了m,a和c的值.对于任何种子,它会生成交替的奇数和偶数.如果我做随机%2来生成随机的标志序列,我只是得到了1,0,1,0,1,0等等. (3认同)
@psihodelia - 什么是'int seed = 123456789;' 然后？ (2认同)
最古老、最简单且绝对是最糟糕的之一。 (2认同)
我是间接来到这里的,所以对于未来的读者,我想补充一点,这与rand()的参考实现非常接近. (2认同)
LCG 生成的低阶比特质量很差。只返回高位。使用 64 位整数，您可以将顶部 32 位与底部 32 位进行异或，从而大幅提高质量。LCG 的名声不好正是因为人们使用低阶位。例如，如果放弃低位，128 位 LCG 将通过 Practrand 测试套件。 (2认同)

Answer 2

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}