提綱

0. 背景介紹

1. 什么是隨機(jī)數(shù)生成算法

2. 最簡(jiǎn)單的隨機(jī)數(shù)生成算法

3. 接下來(lái)的研究

零 - 背景介紹

比如吧, 最近面試就發(fā)現(xiàn), 一個(gè)比較問(wèn)題, 這個(gè)問(wèn)題就是, 比如你問(wèn)面試的人, php 數(shù)組轉(zhuǎn) json, 怎么磚.

對(duì)方就會(huì)說(shuō), echo(json_encode($data)), 這么簡(jiǎn)單都不會(huì), 根本不是寫了 25 年 php 的大神, 對(duì)不對(duì).

那么如果我按照面試?yán)碚摻又鴨?wèn)下一個(gè)問(wèn)題, 那么對(duì)方八成會(huì)啞火, 那么我下一個(gè)問(wèn)題問(wèn)的必然就是.

"請(qǐng)自行實(shí)現(xiàn)一個(gè) json 解析器, 并闡述其原理, 并附上性能評(píng)估指標(biāo)".

這個(gè)問(wèn)題一出, 基本上百分之八十所謂的市面上的工程師就啞火了, 甚至有很多人說(shuō)不清楚各種 Tree 的區(qū)別, 以及甚至有人不知道去哪里找 json 數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn). 比如我這樣的偽裝成大佬的 PHP 乘務(wù)員, 搜了一個(gè)小時(shí)百度才找到, 原來(lái) json 標(biāo)準(zhǔn)在這里 https://www.json.org/json-en.html.

同時(shí)你隨便找人問(wèn), 百分之八十的人不知道 RFC 文檔是什么, 五成的人不知道 github 是干嘛的.

這就是現(xiàn)在世面上的人才分布了, 雖然說(shuō)是正態(tài)分布, 不過(guò)略有擔(dān)心.

所以我今天就像到一個(gè)話題, 那就是越是基礎(chǔ)的東西, 其實(shí)理解起來(lái)越困難, 比如我們經(jīng)常用到的隨機(jī)數(shù)生成.

我們直接去調(diào)個(gè)函數(shù), 調(diào)個(gè)包, 想要幾位的隨機(jī)書, 就出來(lái)了, 但是其中的算法鮮為人知, 讓自己涉及一個(gè)隨機(jī)書生成算法, 更是困難.

為什么呢? 因?yàn)楝F(xiàn)在學(xué)界沒(méi)有真正的隨機(jī)數(shù)生成算法, 全部都是偽隨機(jī)的算法, 那么就是說(shuō), 所有的數(shù)其實(shí)都不是平均分布在整個(gè)區(qū)間的, 是有一定的規(guī)律的, 這些生成的數(shù)字, 都在一個(gè)序列里, 這個(gè)序列的長(zhǎng)短, 決定了重復(fù)的周期.

隨機(jī)數(shù)其實(shí)非常重要, 并且應(yīng)用廣泛, 最重要的是, 在信息安全領(lǐng)域, 密碼學(xué)領(lǐng)域, 有廣泛的應(yīng)用, 不過(guò)說(shuō)的都很寬泛和空洞, 沒(méi)辦法細(xì)說(shuō), 因?yàn)槲覍?duì)這個(gè)東西理解也不深刻, 大家可以等我讀 10 本密碼學(xué)書之后, 然后等我的應(yīng)用數(shù)學(xué)專業(yè)的學(xué)位考下來(lái)了, 再給大家解釋一下, 為什么隨機(jī)數(shù)生成算法如此重要.

一 - 什么是隨機(jī)數(shù)生成算法

下面這段來(lái)自 chatGPT, 我也不多說(shuō)了, 大致意思大家都能理解. 只是現(xiàn)在計(jì)算機(jī)上還無(wú)法實(shí)現(xiàn)真正的隨機(jī)數(shù)生成算法, 當(dāng)然單純就算法層面而言.

比如說(shuō)使用了一些自然界中的數(shù)據(jù), 放射性元素的衰變, 以及各種氣壓, 氣溫等等, 那都不是真正的隨機(jī).

為啥呢? 因?yàn)樗柚送獠康臇|西, 一個(gè)純粹的算法, 應(yīng)該是一個(gè)完備的隨機(jī)數(shù)生成算法, 不需要使用外部的東西.

不過(guò)這都是我自己理解的, 我找到了一些資料解釋為什么現(xiàn)在還沒(méi)有真正的隨機(jī)數(shù)生成算法. 很多解釋都是說(shuō)計(jì)算機(jī)只能執(zhí)行計(jì)算過(guò)程, 沒(méi)辦法進(jìn)行 "think(思考)".

那么是否說(shuō)以后可以使用 AI 的算法來(lái)生成隨機(jī)數(shù)了呢?

如果我要本地部署一個(gè)隨機(jī)數(shù)生成算法, 是否需要花好幾萬(wàn)買英偉達(dá)的最貴最新的顯卡, 推理三個(gè)小時(shí), 耗費(fèi) 200 元電費(fèi), 就為了生成一個(gè) 2 位的隨機(jī)數(shù)呢?

這都是需要考慮得事情呀!

隨機(jī)數(shù)生成算法是一種計(jì)算方法，可以生成一系列看似隨機(jī)的數(shù)字。這些算法用于需要隨機(jī)性的各種應(yīng)用程序，例如加密、模擬和游戲。

隨機(jī)數(shù)生成器有幾種不同類型，包括：

偽隨機(jī)數(shù)生成器（PRNG）：這些算法生成一個(gè)數(shù)字流，看起來(lái)很隨機(jī)，但實(shí)際上由一個(gè)稱為種子的固定初始值決定。PRNG是確定性的，意味著它們始終會(huì)使用相同的種子產(chǎn)生相同的數(shù)字序列。

真隨機(jī)數(shù)生成器（TRNG）：這些算法使用物理過(guò)程（如大氣噪聲或放射性衰變）生成真正的隨機(jī)數(shù)。TRNG是非確定性的，意味著每次使用時(shí)都會(huì)產(chǎn)生一個(gè)新的隨機(jī)數(shù)序列。

加密安全隨機(jī)數(shù)生成器（CSPRNG）：這些算法旨在為加密應(yīng)用程序提供高質(zhì)量的隨機(jī)數(shù)。它們使用來(lái)自PRNG和TRNG的技術(shù)組合來(lái)生成既不可預(yù)測(cè)又具有統(tǒng)計(jì)隨機(jī)性的隨機(jī)數(shù)。

選擇使用哪種類型的算法取決于應(yīng)用程序的特定要求。

常見(jiàn)的偽隨機(jī)數(shù)生成算法大概有下面的幾種

1. 線性同余法：這是最常見(jiàn)的隨機(jī)數(shù)生成算法之一。公式為Xn+1 = (aXn + c) mod m，其中a、c、m和X0是任意給定的常數(shù)，Xn是當(dāng)前的隨機(jī)數(shù)，Xn+1是下一個(gè)隨機(jī)數(shù)。

2. 梅森旋轉(zhuǎn)算法（Mersenne Twister）：這個(gè)算法可以生成高質(zhì)量的隨機(jī)數(shù)，并且周期非常長(zhǎng)。它采用了大量的位運(yùn)算和移位操作，具有高效率和較好的隨機(jī)性。

3. 哈希算法：這個(gè)算法將輸入的數(shù)據(jù)通過(guò)哈希函數(shù)轉(zhuǎn)換為一段固定長(zhǎng)度的隨機(jī)數(shù)字串。由于哈希函數(shù)的特性，輸出結(jié)果與輸入數(shù)據(jù)之間的關(guān)系非常復(fù)雜，因此可以生成高質(zhì)量的隨機(jī)數(shù)。

4. 遞推算法：這個(gè)算法利用已知的前幾個(gè)隨機(jī)數(shù)通過(guò)某種遞推公式來(lái)計(jì)算下一個(gè)隨機(jī)數(shù)。遞推算法的隨機(jī)性取決于初始值和遞推公式的選擇

二 最簡(jiǎn)單的隨機(jī)數(shù)生成算法

上面列舉了一些隨機(jī)數(shù)的生成算法, 但是都不夠簡(jiǎn)單, 我這里為了說(shuō)明例子, 所以就選取了由馮諾依曼大神再 1949 年提出的一個(gè)非常簡(jiǎn)單的, 在埃尼阿克上運(yùn)行的一個(gè)隨機(jī)數(shù)生成算法.

這個(gè)算法就是 平方取中法（Middle-square method).

就和它的名字一樣, 這個(gè)算法和平方有關(guān), 具體的算法非常簡(jiǎn)單, 甚至不需要描述直接上代碼大家也能看懂.

甚至比冒泡排序還簡(jiǎn)單.

具體的邏輯就是, 比如要生成一個(gè) 2 位的隨機(jī)數(shù), 那么我們需要先選取一個(gè)種子, 比如 25, 然后給 25 求平方, 如果求得的數(shù)的位數(shù), 不滿足 2m (m為要生產(chǎn)的數(shù)的位數(shù), 這里是 2), 那么在數(shù)的左側(cè)補(bǔ)零, 然后取生成的數(shù)的中間的兩位作為生成的隨機(jī)數(shù), 并且保存起來(lái), 作為下一次計(jì)算的種子.

這就是整個(gè)的算法過(guò)程, 整個(gè)計(jì)算過(guò)程, 只有一個(gè)乘法, 而乘法在 cpu 上其實(shí)是加法, 所以整個(gè)的算法的計(jì)算效率, 集中在要生成的數(shù)有多大上.

因?yàn)橐傻臄?shù)的位數(shù)越多, 那么乘法就越耗時(shí), 不過(guò)證題的算法效率是可以接受的.?

這個(gè)算法的問(wèn)題在于很容易出現(xiàn)循環(huán), 所以沒(méi)有得到廣泛的應(yīng)用. 本來(lái)打算貼一段代碼, 但是邏輯太簡(jiǎn)單, 就不貼代碼了.

三 接下來(lái)的技術(shù)研究

其實(shí)我對(duì)諾伊曼的這段算法的闡述不夠好, 為啥呢? 因?yàn)槲覜](méi)有辦法瞬間想到這個(gè) loop, 也就是隨機(jī)數(shù)的分布循環(huán)到底是什么樣的概率, 以及如何去優(yōu)化, 這些我都沒(méi)有想到.

我雖然把算法給說(shuō)出來(lái)了, 因?yàn)樗惴ū旧肀容^簡(jiǎn)單, 但是就隨機(jī)數(shù)本身, 其實(shí)所有隨機(jī)數(shù)都在一個(gè)序列里, 這個(gè)序列就是某個(gè)函數(shù)上的取值.

所以這些算法根本不能算上隨機(jī)算法, 甚至偽隨機(jī)都有現(xiàn)勉強(qiáng).

在統(tǒng)計(jì)學(xué)上更是站不住腳的, 所以這個(gè)算法作為菜鳥學(xué)算法的入門還是不錯(cuò)的, 大概著名的隨機(jī)數(shù)的生成算法有十來(lái)種.

我們可以做一個(gè)專題, 專門從科普加少量數(shù)學(xué)理論的角度去研究這些算法. 同時(shí)隨機(jī)數(shù)的分布應(yīng)該是均勻的.

那么我們還可以通過(guò)散點(diǎn)圖的形式去研究不同算法隨機(jī)數(shù)的分布, 其實(shí)如果可以看到很短的 loop, 那么這種算法就比較不好了.

今天就寫到這里吧, 加油!