問題描述

如何創(chuàng)建一個(gè)函數(shù)，每次調(diào)用都會(huì)生成一個(gè)隨機(jī)整數(shù)?這個(gè)數(shù)字必須盡可能隨機(jī)(根據(jù)均勻分布).只允許使用一個(gè)靜態(tài)變量，最多 3 個(gè)基本步驟，其中每個(gè)步驟僅包含 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;
}

基本算術(shù)運(yùn)算有+、-、%、and、not、xor、or、左移、右移、乘除.當(dāng)然，不允許使用 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.

推薦答案

線性同余生成器是最古老、最簡(jiǎn)單的方法之一:

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

int seed = 123456789;

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

只需要一些基本算術(shù)運(yùn)算的指令，這就是你所需要的.

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

請(qǐng)注意，只有在以特定方式選擇 a、c 和 m 時(shí)，此算法才能正常工作！

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

為了保證這個(gè)序列的最長(zhǎng)可能周期，c 和 m 應(yīng)該是互質(zhì)的，a-1 應(yīng)該可以被所有質(zhì)數(shù)整除m 的因數(shù)，如果 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.

維基百科上顯示了一些參數(shù)示例:例如某些編譯器的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.

這篇關(guān)于特殊的簡(jiǎn)單隨機(jī)數(shù)發(fā)生器的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！