C++助教问题汇总2

周四实验课遇到的高频编程问题,简单汇总了一下。

随机数生成为什么要初始化种子

同学们看起来有两个疑惑:

  1. 为什么我要初始化种子?
  2. 为什么我又不能每次都初始化种子?

这要从(伪)随机数的原理,线性同余算法讲起。我先用一个简单的例子引入:

线性同余算法

用计算机展开1÷67的小数部分

1÷67的小数部分,看起来特别没有规律。
如果我每次截取小数点后面的3个数字,我们将得到:014,925,373,134,328,……。
看,如果我不告诉你这些数字的产生原理,是不是看起来我就像拥有了一个0~999的随机数发生器?

线性同余算法 (Linear congruential generator) 正是基于类似的原理。
照搬百度百科上的定义,设 $X_n$ 是产生的第 $n$ 的(伪)随机数,$a, b, c$ 为固定整数参数,则线性同余发生器(LCG)的定义如下,

$$
X_{n+1} = (a X_{n} + c) \ \rm{mod} \ m
$$

通过选取不同的参数 $a, b, c$, 这个伪随机序列 ${ X_n }$ 可以任意变换。如果你只能观测这个序列已产生的部分,不知道它的参数,也是不可能预测这个序列之后的部分的。

1÷67是有理数,小数部分必定有循环节

当然,线性同余算法也有缺陷,就是这个序列一定有周期,不过只要周期足够大,就可以不考虑这个问题。

随机种子 (Random Seed)

为了确保线性同余序列的周期足够大,或者说这个参数的质量足够优良,通常 $a$, $b$ 和 $m$ 是数学家找好以后写死在代码里的。下面是一个线性同余生成器的实现,其中$a=214013$, $b=2531011$, $m=32768$(截取的不是尾部1-15位,而是31到16位,略有差异无妨)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

unsigned long _next = 0;

unsigned int my_rand(void) {
_next = _next * 214013L + 2531011L;
return ((_next >> 16) & 0x7fff);
}

int main() {
for (int i = 0; i < 5; i++) {
cout << my_rand() << endl;
}
return 0;
}

运行结果是

1
2
3
4
5
38
7719
21238
2437
8855

但是,这个程序每次运行时给出的结果都是一样的。毕竟,运算方式都是固定在里面的,而初值也一直都是0。

因此,我们引入随机数种子的概念。它其实就是用不同的值对_next进行初始化,相当于在这个周期超长的伪随机序列上选取不同的起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

unsigned long _next = 0;

void my_srand(unsigned long seed) {
_next = seed;
}

unsigned int my_rand(void) {
_next = _next * 214013L + 2531011L;
return ((_next >> 16) & 0x7fff);
}

int main() {
for (int seed = 1; seed <= 5; seed++) {
my_srand(seed);
cout << "set seed " << seed << ": ";

for (int i = 0; i < 5; i++) {
cout << my_rand() << " -> ";
}
cout << "..." << endl;
}
return 0;
}

运行结果是

1
2
3
4
5
set seed 1: 41 -> 18467 -> 6334 -> 26500 -> 19169 -> ...
set seed 2: 45 -> 29216 -> 24198 -> 17795 -> 29484 -> ...
set seed 3: 48 -> 7196 -> 9294 -> 9091 -> 7031 -> ...
set seed 4: 51 -> 17945 -> 27159 -> 386 -> 17345 -> ...
set seed 5: 54 -> 28693 -> 12255 -> 24449 -> 27660 -> ...

现在告诉你,这份代码是对Windows上的C++随机数内部实现的严格复现(源代码写得更绕一些)。将my_srand()my_rand()换为srand()rand(),结果将是完全一致的(请动手试一试)!

是不是,原理也没那么复杂?

何时重置种子

回到那个问题

  1. 为什么我要初始化种子?
  2. 为什么我又不能每次都初始化种子?

线性同余生成器确保了每次调用rand()时总在一个伪随机序列环上取数,上一个数和下一个数看之间看不出关联性,但每次程序运行时都从该环的同一个位置开始行走,每次都将输出相同的随机数序列。因此,用时间作为种子,可以使得不同时间运行的同一份程序从该环的不同位置上开始行走。然而,如果在每次取随机数时都用时间赋种子,则随机数生成器退化成报时器。


感谢W的屁股蛋子!
封面来自小日子老师@Liduke的微博。


C++助教问题汇总2
http://example.com/2022/10/08/cpp_tutor_2/
作者
Lee++
发布于
2022年10月8日
许可协议