特殊的简单随机数生成器 [英] Special simple random number generator

问题描述

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

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;
}

基本算术运算是+，-，％和，而不是xor，或左移，右移，乘法和除法.当然，不允许使用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.

一些参数示例在Wikipedia上显示:例如，某些编译器的ANSI C建议 m =2³¹， a = 1103515245和 c = 12345.

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

这篇关于特殊的简单随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！