随机数生成器


类别：函子	组件类型：概念

描述

随机数生成器是一个函数对象，可用于生成随机整数序列。也就是说，如果f是一个随机数生成器，并且N是一个正整数，则f(N)将返回一个小于N且大于或等于0的整数。如果f被多次调用，且每次调用的参数值都为N，它将产生一个在范围内均匀分布的数字序列[1][0, N). [2]

细化自

一元函数

关联类型

参数类型	随机数生成器参数的类型。这必须是整数类型。
结果类型	调用随机数生成器时返回的类型。它必须与参数类型相同。

符号

`F`	是随机数生成器模型的类型。
`整数`	的的参数类型`F`.
`f`	类型为的对象`F`.
`N`	类型为的对象`整数`

定义

随机数生成器的域（即其参数的允许值集）是大于零且小于某个最大值的数字集。

随机数生成器的范围是小于随机数生成器参数的非负整数集。

有效表达式

除了一元函数中定义的之外，没有其他有效表达式。

表达式语义

名称	表达式	先决条件	语义	后置条件
函数调用	`f(N)`	`N`为正。	返回类型为的伪随机数`整数`. [2]	返回值小于`N`且大于或等于 0。

复杂度保证

不变式

均匀性	当`f`被多次调用，且每次调用的参数都为`N`时，范围内`[0, N)`的每个整数都会出现相同次数。

模型

注释

[1] 均匀分布意味着范围内[0, N)的所有数字出现的频率相同。或者换句话说，获得任何特定值的概率为1/N.

[2] 随机数生成器是一个非常微妙的话题：一个好的随机数生成器必须满足除了均匀分布之外的许多统计特性。请参阅 Knuth 的 3.4 节，了解随机序列的含义，以及 3.2 节中的一些可用于编写随机数生成器的算法。（D. E. Knuth，《计算机程序设计艺术。第 2 卷：半数值算法》，第三版。Addison-Wesley，1998。）

随机数生成器

描述

细化自

关联类型

符号

定义

有效表达式

表达式语义

复杂度保证

不变式

模型

注释

另请参阅