随机数生成算法科普

大家好，欢迎来到IT知识分享网。

提纲

0. 背景介绍

1. 什么是随机数生成算法

2. 最简单的随机数生成算法

3. 接下来的研究

零 – 背景介绍

比如吧, 最近面试就发现, 一个比较问题, 这个问题就是, 比如你问面试的人, php 数组转 json, 怎么砖.

对方就会说, echo(json_encode($data)), 这么简单都不会, 根本不是写了 25 年 php 的大神, 对不对.

那么如果我按照面试理论接着问下一个问题, 那么对方八成会哑火, 那么我下一个问题问的必然就是.

“请自行实现一个 json 解析器, 并阐述其原理, 并附上性能评估指标”.

这个问题一出, 基本上百分之八十所谓的市面上的工程师就哑火了, 甚至有很多人说不清楚各种 Tree 的区别, 以及甚至有人不知道去哪里找 json 数据结构的标准. 比如我这样的伪装成大佬的 PHP 乘务员, 搜了一个小时百度才找到, 原来 json 标准在这里 https://www.json.org/json-en.html.

同时你随便找人问, 百分之八十的人不知道 RFC 文档是什么, 五成的人不知道 github 是干嘛的.

这就是现在世面上的人才分布了, 虽然说是正态分布, 不过略有担心.

所以我今天就像到一个话题, 那就是越是基础的东西, 其实理解起来越困难, 比如我们经常用到的随机数生成.

我们直接去调个函数, 调个包, 想要几位的随机书, 就出来了, 但是其中的算法鲜为人知, 让自己涉及一个随机书生成算法, 更是困难.

为什么呢? 因为现在学界没有真正的随机数生成算法, 全部都是伪随机的算法, 那么就是说, 所有的数其实都不是平均分布在整个区间的, 是有一定的规律的, 这些生成的数字, 都在一个序列里, 这个序列的长短, 决定了重复的周期.

随机数其实非常重要, 并且应用广泛, 最重要的是, 在信息安全领域, 密码学领域, 有广泛的应用, 不过说的都很宽泛和空洞, 没办法细说, 因为我对这个东西理解也不深刻, 大家可以等我读 10 本密码学书之后, 然后等我的应用数学专业的学位考下来了, 再给大家解释一下, 为什么随机数生成算法如此重要.

一 – 什么是随机数生成算法

下面这段来自 chatGPT, 我也不多说了, 大致意思大家都能理解. 只是现在计算机上还无法实现真正的随机数生成算法, 当然单纯就算法层面而言.

比如说使用了一些自然界中的数据, 放射性元素的衰变, 以及各种气压, 气温等等, 那都不是真正的随机.

为啥呢? 因为它借助了外部的东西, 一个纯粹的算法, 应该是一个完备的随机数生成算法, 不需要使用外部的东西.

不过这都是我自己理解的, 我找到了一些资料解释为什么现在还没有真正的随机数生成算法. 很多解释都是说计算机只能执行计算过程, 没办法进行 “think(思考)”.

那么是否说以后可以使用 AI 的算法来生成随机数了呢?

如果我要本地部署一个随机数生成算法, 是否需要花好几万买英伟达的最贵最新的显卡, 推理三个小时, 耗费 200 元电费, 就为了生成一个 2 位的随机数呢?

这都是需要考虑得事情呀!

随机数生成算法是一种计算方法，可以生成一系列看似随机的数字。这些算法用于需要随机性的各种应用程序，例如加密、模拟和游戏。

随机数生成器有几种不同类型，包括：

伪随机数生成器（PRNG）：这些算法生成一个数字流，看起来很随机，但实际上由一个称为种子的固定初始值决定。PRNG是确定性的，意味着它们始终会使用相同的种子产生相同的数字序列。

真随机数生成器（TRNG）：这些算法使用物理过程（如大气噪声或放射性衰变）生成真正的随机数。TRNG是非确定性的，意味着每次使用时都会产生一个新的随机数序列。

加密安全随机数生成器（CSPRNG）：这些算法旨在为加密应用程序提供高质量的随机数。它们使用来自PRNG和TRNG的技术组合来生成既不可预测又具有统计随机性的随机数。

选择使用哪种类型的算法取决于应用程序的特定要求。

常见的伪随机数生成算法大概有下面的几种

1. 线性同余法：这是最常见的随机数生成算法之一。公式为Xn+1 = (aXn + c) mod m，其中a、c、m和X0是任意给定的常数，Xn是当前的随机数，Xn+1是下一个随机数。

2. 梅森旋转算法（Mersenne Twister）：这个算法可以生成高质量的随机数，并且周期非常长。它采用了大量的位运算和移位操作，具有高效率和较好的随机性。

3. 哈希算法：这个算法将输入的数据通过哈希函数转换为一段固定长度的随机数字串。由于哈希函数的特性，输出结果与输入数据之间的关系非常复杂，因此可以生成高质量的随机数。

4. 递推算法：这个算法利用已知的前几个随机数通过某种递推公式来计算下一个随机数。递推算法的随机性取决于初始值和递推公式的选择

二 最简单的随机数生成算法

上面列举了一些随机数的生成算法, 但是都不够简单, 我这里为了说明例子, 所以就选取了由冯诺依曼大神再 1949 年提出的一个非常简单的, 在埃尼阿克上运行的一个随机数生成算法.

这个算法就是 平方取中法（Middle-square method).

就和它的名字一样, 这个算法和平方有关, 具体的算法非常简单, 甚至不需要描述直接上代码大家也能看懂.

甚至比冒泡排序还简单.

具体的逻辑就是, 比如要生成一个 2 位的随机数, 那么我们需要先选取一个种子, 比如 25, 然后给 25 求平方, 如果求得的数的位数, 不满足 2m (m为要生产的数的位数, 这里是 2), 那么在数的左侧补零, 然后取生成的数的中间的两位作为生成的随机数, 并且保存起来, 作为下一次计算的种子.

这就是整个的算法过程, 整个计算过程, 只有一个乘法, 而乘法在 cpu 上其实是加法, 所以整个的算法的计算效率, 集中在要生成的数有多大上.

因为要生成的数的位数越多, 那么乘法就越耗时, 不过证题的算法效率是可以接受的.

这个算法的问题在于很容易出现循环, 所以没有得到广泛的应用. 本来打算贴一段代码, 但是逻辑太简单, 就不贴代码了.

三 接下来的技术研究

其实我对诺伊曼的这段算法的阐述不够好, 为啥呢? 因为我没有办法瞬间想到这个 loop, 也就是随机数的分布循环到底是什么样的概率, 以及如何去优化, 这些我都没有想到.

我虽然把算法给说出来了, 因为算法本身比较简单, 但是就随机数本身, 其实所有随机数都在一个序列里, 这个序列就是某个函数上的取值.

所以这些算法根本不能算上随机算法, 甚至伪随机都有现勉强.

在统计学上更是站不住脚的, 所以这个算法作为菜鸟学算法的入门还是不错的, 大概著名的随机数的生成算法有十来种.

我们可以做一个专题, 专门从科普加少量数学理论的角度去研究这些算法. 同时随机数的分布应该是均匀的.

那么我们还可以通过散点图的形式去研究不同算法随机数的分布, 其实如果可以看到很短的 loop, 那么这种算法就比较不好了.

今天就写到这里吧, 加油!