这篇比较短。以后短博文会越来越多。之前那种一篇一两千字的博文写着有点累

Pseudo Random Number Generator (PRNG) 常见算法 - 线性同余生成器： \[ s_0=\texttt{seed} \]

\[ s_{i+1}\equiv a\cdot s_i + b \mod m \]

其中，\(i \in \mathbb{N}, a,b,m\in\mathbb{Z}\)。

例如，ANSI C 中，rand() 函数便是使用这种方法实现的（\(s_0=12345\)，\(a=1103515245\)，\(b=s_0\)，\(m=2^{31}\)）

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
27
28
29
30
/* glibc/stdlib/rand.c, glibc/stdlib/random.c, and glibc/stdlib/random_r.c
 * LICENSE File: https://raw.githubusercontent.com/lattera/glibc/master/LICENSES
 * 仅供学术研究交流使用
 */

int rand(void)
{
    return (int) __random ();
}

long int __random (void)
{
  int32_t retval;
  __libc_lock_lock (lock);
  (void) __random_r (&unsafe_state, &retval);
  __libc_lock_unlock (lock);
  return retval;
}

int __random_r (struct random_data *buf, int32_t *result)
{
  // ...
  if (buf->rand_type == TYPE_0)
    {
      // Here it is!!!
      int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;
      // ...
    }
  // ...
}

需要注意的是，合格的 PRNG 应当具有良好的均匀分布性，这意味着 \(\\{s_i\\}\) 在分布上应非常接近真随机数。使用卡方检验（Chi-Square Distribution Test）可以验证 PRNG 的随机性，理论上讲得到的分布值 \(D\in[0,1)\) 应当尽可能接近 0.5，然而往往 \(D\) 在 0.35 以上、0.65 以下就已经是很不错的结果了。

Python 可以直接使用 scipy.stats 包里的 chisquare 函数来计算卡方分布值。

这里有一个 PRNG 的样例：令 \(\texttt{seed} = 2997991993\)，\(a=46771\)，\(b=359\)，\(m=2^{8}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
seed, modulo = 2997991993, 256
a, b = 46771, 359
exists = [seed % modulo]
index = -1
result = []

def rand():
    global index
    index += 1
    exists.append((a * exists[index] + b) % modulo)
    return exists[index]

for i in range(0, 10):
    result.append(rand())

hex_form = list(map(lambda num: hex(num)[2:].zfill(2), result));
print("<hex [{}]>".format(" ".join(hex_form)))

# we got <hex [39 42 8d fe 01 1a 95 96 49 72]>

然而这样做会导致每次运行得到的随机数序列都是一样的。比方说，如果老师想使用这种算法通过抽号来指定学生回答问题，那么每次 ta 都只能抽到同一名同学——这显然是不合理的，还容易产生“抽号黑幕”的误会。

所以，常见的避免这种办法的做法是取变化的 \(\tt seed​\) ——例如，使用当前的 UNIX 时间戳，或是从 /dev/random 读入定长字节后再转化为数字：

1
2
3
4
with open("/dev/random", "rb") as f:
    seed = int(f.read(4).hex(), 16)

# seed == 4142487213

这样一来，最终的输出就确实很随机了。

实际上，这里存在一个逻辑问题：/dev/random 是系统收集用户操作（鼠标滑动、键盘敲击）作为种子生成出来的伪随机数。换言之，最终在使用上，我们的 PRNG 依赖了另外一个 PRNG。那么为什么我们不直接使用 /dev/random 作为随机数生成器呢？

如果改用 UNIX 时间戳来作为 \(\tt seed\) 则无此顾虑。毕竟我们只需要 \(\tt seed\) 是一个变化的数字，而不一定要求 \(\tt seed\) 也是个随机数。

来源：https://blog.jiejiss.com/