C中随机数生成器背后的逻辑

  • 本文关键字:背后 随机数生成器 c
  • 更新时间 :
  • 英文 :


可能的重复:
随机数生成器是如何工作的?

C编译器如何决定在随机数生成函数中下一个应该生成哪个数?例如,它总是在给定范围内生成一个新的随机数。这是怎么做到的?

它通过保留一些状态并在每次调用函数时修改状态来生成下一个数字。这样的函数被称为伪随机数生成器创建PRNG的一种旧方法是线性同余生成器,这很简单:

static int rand_state;
int rand(void)
{
rand_state = (rand_state * 1103515245 + 12345) & 0x7fffffff;
return rand_state;
}

正如你所看到的,如果你知道上一个数字,这个方法可以让你预测序列中的下一个数字。还有更复杂的方法。

已经为特定目的设计了各种类型的伪随机数生成器。有些安全的PRNG速度很慢,但即使你知道它们是如何工作的,也很难预测,还有像Mersenne Twister这样的大型PRNG,它们具有良好的分布特性,因此对编写蒙特卡罗模拟非常有用。

根据经验,线性同余生成器足以编写游戏(怪物造成多大伤害),但不足以编写模拟。研究人员为他们的项目选择了糟糕的PRNG,这是一段丰富多彩的历史;因此,他们的模拟结果令人怀疑。

它不是一个编译器,而是一个C库,它具有生成伪随机(不是真正的随机!)数的函数。

通常使用线性同余生成器。

好吧,C编译器不接受这个决定。下一个随机数取决于算法。生成随机数不是一件容易的事。看看

  • http://www.math.utah.edu/~pa/Random.html
  • http://computer.howstuffworks.com/question697.htm
  • http://en.wikipedia.org/wiki/Random_number_generation

这取决于所讨论的伪随机数生成器(PRNG)的具体实现。有很多变体在使用中。

一个常见的例子是线性同余生成元族(LCG)。这些由递推关系定义:

 nbsp;Xn+1<-aXn+c(mod m)

因此,来自PRNG的每个新样本仅由前一个样本以及常数a、c和m确定。注意,如本文所述,a、c、m的选择至关重要。

LCG非常简单高效。它们通常用于标准库提供的随机数生成器。然而,它们具有较差的统计特性,并且为了获得更好的随机性,更先进的PRNG是优选的。

在stackoverflow中有很多关于这方面的问题。这里有一些。你可以从中获得帮助。

rand()的实现

c 中的Rand函数

Rand实施

这实际上是一个很大的话题。一些关键事项:

  • 随机数的生成是在运行时完成的,而不是在编译时
  • 提供随机性的策略在很大程度上取决于(或应该取决于)应用程序。例如,如果您只需要在给定范围内均匀分布的一系列值,则会使用线性同余生成器等解决方案。如果您的应用程序与安全性/密码学相关,那么您将需要更强的特性,即您的值既随机分布,又不可预测
  • 一个主要的挑战是获得"真实"的随机性,你可以用它来种子你的伪随机生成器(它将真实的随机性"拉伸"成任意数量的可用随机性)。一种常见的技术是使用一些不可预测的系统状态(例如,对鼠标的位置或按键定时进行采样),然后使用伪随机生成器为整个系统提供随机性

最新更新