一尘不染

特殊的简单随机数生成器

algorithm

如何创建一个函数,该函数在每次调用时都会生成一个随机整数?此数字必须尽可能是最大随机数(根据均匀分布)。它仅允许使用一个静态变量和至多3元步骤,其中每个步骤仅由一个基本的算术运算的元数
1或2。

例:

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

基本的算术运算是+,-,%和非,或,或,左移,右移,乘法和除法。当然,不允许使用rand(),random()或类似内容。


阅读 467

收藏
2020-07-28

共1个答案

一尘不染

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

int seed = 123456789;

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

您只需要几条基本的算术指令即可。

请注意,只有 以特定方式选择 acm时 ,该算法才能正常工作!

为了保证该序列的最大可能周期, cm 应该是互质的, a − 1应该可以被 m 的所有素数整除,如果 m 被4 整除,则 a
− 1应该可以整除。

参数的一些示例在Wikipedia上显示:例如,对于某些编译器,ANSI
C提出 m = 2³¹ , a = 1103515245和 c = 12345。

2020-07-28