特殊的简单随机数发生器

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

例:

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

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

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

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

几乎没有基本算术运算的指令,这就是你所需要的。

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

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

维基百科中显示了一些值的示例:例如,某些编译器的ANSI C建议m = 2^32a = 1103515245c = 12345

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

种子不能为0.来源: http : //www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

维基中的其他信息: https : //en.wikipedia.org/wiki/Xorshift

你可能会看看这个 。 它远不是一个“完美的”随机数发生器,但它确实满足了你的要求,就我所见。

在这里,您可以找到有关随机数生成的一些其他信息。

如果我写man rand ,我可以阅读一个可能的例子,在POSIX.1-2001中给出,用于实现rand()和srand()。 见例如这里 。 如果您需要更复杂的东西,请查看GNU Scientific Library ; 您当然可以下载代码并查看实现。

Boost有一个非常好的随机数字库,并且源代码可用,因此您可以尝试查看并使用您需要的内容(即剪切和粘贴)。

这是一个在整个int范围内均匀分布的函数:

 int rand() { static int random = 0; return random++; } 

我用这个

 SUBROUTINE GNA(iiseed) USE Variaveis parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.) INTEGER :: iiseed iiseed = ib + ia*iiseed if (iiseed.lt.0) iiseed = (iiseed+m) + m RndNum = iiseed*r231 END SUBROUTINE GNA 

在不花费更多计算时间的情况下,可以实现随机性的大的增益,为随机数生成器在程序中进行的每次调用创建随机数生成器。

这是一个非常好的技巧!