特殊的简单随机数发生器

2021-12-17 00:00:00 algorithm math c c++

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

How to create a function, which on every call generates a random integer number? This number must be most random as possible (according to uniform distribution). It is only allowed to use one static variable and at most 3 elementary steps, where each step consists of only one basic arithmetic operation of arity 1 or 2.

示例:

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

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

Basic arithmetic operations are +,-,%,and, not, xor, or, left shift, right shift, multiplication and division. Of course, no rand(), random() or similar stuff is allowed.

推荐答案

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

Linear congruential generators are one of the oldest and simplest methods:

int seed = 123456789;

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

只需要一些基本算术运算的指令,这就是你所需要的.

Only a few instruction with basic arithmetic operations, that's all you need.

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

Mind that this algorithm works fine only if a, c and m are chosen in a particular way!

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

To guarantee the longest possible period of this sequence, c and m should be coprime, a???1 should be divisible by all prime factors of m, and also for 4 if m is divisible by 4.

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

Some examples of parameters are shown on Wikipedia: for example ANSI C for some compilers proposes m?=?2?31, a?=?1103515245 and c?=?12345.

相关文章