第七章 随机数(Random Number)

1 简介

随机数(Random Number)是一个重要的数学概念，它广泛的应用于计算机各个领域之中。例如：在计算机密码学(Computer Cryptography)中，一些算法使用随机数来生成密钥(Private Key)；在计算机建模(Modeling and Simulation)中，一些算法利用随机数来对数据进行抽样(Sampling)；快速排序算法(Quicksort Algorithm)在每一次迭代完成之后，可能会随机地选择下一个pivot。

在计算机领域内，随机数的概念比较容易理解。给定一个集合，每次从这个集合中取出一个元素，取出之后，再将这个元素放回该集合。按照如此方式重复操作，如果取出的元素符合以下两个条件，则我们可以认为每次取出的元素为随机数。

1. 在每次取出元素之前，不能确定下一次取出的是哪个元素。即，每次取出的元素具有随机性。
2. 经过大量的取出和放回操作之后，集合内所有元素的取出次数大约相同。

抛硬币是一个很好的例子。正面朝上和反面朝上是两种可能出现的结果。因此，抛硬币的结果是一个包含两个元素的集合。在每次抛出之前，我们无法预知抛出之后的结果，因此，抛硬币满足上述的第一个条件。当抛硬币的次数逐步增加后，正面朝上的次数和反面朝上的次数大略相同。这满足上述的第二个条件。

2 伪随机数(Pseudo Random Number)

虽然随机数的概念容易被人们理解和接受，但是，在计算机领域中，生成随机数是一个非常困难的问题。至今为止，计算机系统尚不能生成一个真正的随机数。

2.1 为什么计算机不能生成真正的随机数呢？

为什么计算机不能生成真正的随机数呢？这是因为随机数的概念与计算机的设计理念是完全相反的。计算机系统的一个本质特点是确定性(Deterministic)。即，在相同的运行环境下，使用相同的输入、运行相同的算法，得到的结果必然相同。这个特性又被称为可重复性(Repeatability)。然而，我们对照上述的随机性的两个条件来看，计算机系统不满足条件一，因为下一次取出的元素是确定的，可重复的。

2.2 计算机如何生成随机数呢？

因为计算机不能生成真正的随机数；由计算机生成的随机数被称为伪随机数(Pseudo Random Number)。既然，计算机自身具有确定性，那么，计算机如何生成随机数呢？

生成随机数的设备(Device)或者算法(Algorithm)被称为随机数生成器(Random Number Generator)。随机数生成器大致可分为两类：

1. 硬件随机数生成器(Hardware Random Number Generator)。硬件随机数生成器通过借助"外部环境因素"引入随机性(Randomness)。硬件随机数生成器能够感知外界环境的变化，将其融入随机数生成过程之中。常见的外部环境因素包括环境噪音数据(Environmental Noise)，温度(Thermal Noise)，电磁辐射(Atmospheric Noise)，晶振(Crystal oscillator)等。
2. 软件随机数生成器(Software Random Number Generator)。软件随机数生成器又常被称为软件随机数生成算法。这些算法定义了一系列生成随机数的规则和过程。这些算法需要使用一个种子(Seed)来触发随机数的生成。通常情况下，种子(Seed)可以是一个任意的整数，种子不必是随机生成的。但是，种子的取值至关重要，因为，使用相同的种子生成出的随机序列是相同的。虽然不是真正的随机数，良好的软件伪随机数生成器所表达的随机性已非常接近于真正的随机数，已经能够满足绝大多数应用的需求。

我们使用一个简单的软件随机数生成算法来解释随机数生成过程以及种子的使用方式。平方取中法(Middle-Square Method)是由冯·诺伊曼于1946年提出的。其方法工作如下：

1. 取任意一个整数作为种子。假设种子为n位整数。
2. 求种子的平方。
3. 若种子的平方未达到2n位整数，则使用前缀0补足位数。
4. 取2n位结果的中间n位为下一轮计算的种子。以此类推。

我们用下面的例子来解释平方取中法的工作过程。

1. 第一轮：假设种子N₁=1111，是一个四位整数。
2. 种子的平方为1111 x 1111 = 1234321。
3. 1234321是一个7位整数。因为它不足8位，所以，补一个前缀0至8位，结果为01234321。
4. 取01234321的中间四位2343作为下一轮的种子。
5. 第二轮：种子N₂=2342，是一个四位整数。
6. 种子的平方为2343 x 2343 = 5489649。
7. 5489649是一个7位整数。因为它不足8位，所以，补一个前缀0至8位，结果为05489649。
8. 取05489649的中间四位4896作为下一轮的种子。
9. 以此类推，获得伪随机数序列。

平方取中法有许多缺陷。其中，最明显的一个弱点是它的周期很短，容易出现重复序列。因此，人们发明了更多更好的伪随机数生成算法。

小水滴提供了在线随机数生成工具，欢迎大家使用。

3 结语

本章介绍了随机数的基本概念，以及在计算机系统中伪随机数的生成原理。总而言之，计算机系统很难生成真正的随机数。对于绝大多数计算机系统而言，伪随机数已经足够满足应用需求。