歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識(shí)】
人工智能通識(shí)-2019年3月專題匯總
中間平方法Middle-square method
“Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
——John Von Neumann.
世界上第一臺(tái)計(jì)算機(jī)是1945年制造的ENIAC∥嚎恚現(xiàn)代計(jì)算機(jī)之父馮諾依曼John Von Neumann在它的基礎(chǔ)上改進(jìn)成為真正意義上的現(xiàn)代計(jì)算機(jī)。
而在這個(gè)時(shí)候力麸，計(jì)算機(jī)剛剛起步的時(shí)候捏雌，馮諾依曼就說了這么一句話互婿，如果誰想用數(shù)學(xué)方法生成隨機(jī)數(shù)字，那么他一定是落入了原罪。
馮諾依曼是博弈論的創(chuàng)始人洽腺，在量子力學(xué)方面也很有成就鹏往，在他開啟計(jì)算機(jī)時(shí)代之初淡诗，就指明了真隨機(jī)不可能依靠數(shù)學(xué)和計(jì)算機(jī)方法實(shí)現(xiàn)。
但為了計(jì)算機(jī)的制造伊履，馮諾依曼發(fā)明了一個(gè)很粗糙的偽隨機(jī)PRNG方法:中間平方法韩容。
給定一個(gè)六位數(shù)作為種子，比如675248唐瀑，那么先把它平方群凶，比如得到455959861504，然后再掐頭去尾取中間6個(gè)數(shù)字哄辣，把它當(dāng)做隨機(jī)數(shù)結(jié)果请梢，如圖中的959861。當(dāng)然這個(gè)計(jì)算流程可以繼續(xù)重復(fù)下去力穗，就能得到一些列隨機(jī)六位數(shù)毅弧。
Python代碼如下：
seed_number = int(input("請(qǐng)輸入一個(gè)六位數(shù)："))
number = seed_number
already_seen = set()
counter = 0
while number not in already_seen:
counter += 1
already_seen.add(number)
number = int(str(number * number).zfill(12)[3:9])
print(f"#{counter}: {number}")
print(f"開始于{seed_number}, 共{counter}步之后出現(xiàn)重復(fù)數(shù)字{number}.")
對(duì)于6位數(shù)來說，一般在數(shù)百次之后就會(huì)發(fā)生重復(fù)循環(huán)当窗。這隨機(jī)方法真的很粗糙够坐。
威爾的PRNG
20世紀(jì)30年代興起的普林斯頓高等研究院IAS可以說是自然科學(xué)的圣地，愛因斯坦超全、計(jì)算機(jī)理論先驅(qū)哥德爾咆霜、原子彈之父奧本海默、現(xiàn)代計(jì)算機(jī)之父馮諾依曼嘶朱，日本數(shù)學(xué)家小平邦彥和華裔物理學(xué)家楊振寧蛾坯、李政道都曾在此學(xué)習(xí)或工作。
馮諾依曼是個(gè)猶太人疏遏，原本居住匈牙利脉课，然而由于希特勒的統(tǒng)治影響救军，他來到了美國(guó)。而把他介紹到普林斯頓的正是另一位偉大的科學(xué)家赫爾曼·威爾Hermann Weyl倘零。
威爾這次又改進(jìn)了馮諾依曼的中間平方隨機(jī)程序唱遭。
這是一段C++代碼：
#include <stdint.h>
#include <stdio.h>
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws() {
x *= x;
x += (w += s);
return x = (x>>32) | (x<<32);
}
int main(){
for(int i=0;i<10;i++){
printf("%d\n",msws());
}
}
雙箭頭在這里是移位操作，<<相當(dāng)于乘以2的32次方呈驶，>>則是除以2的32次方拷泽。
這里的思路是每次都把種子x平方，并且加上一個(gè)w袖瞻，而且w每次都增大s司致，這里s是個(gè)很大十六進(jìn)制數(shù)字，它足以超過2的32次方聋迎。
注意x,w,s都是uint64脂矫，是64位的，而msws()返回的是uint32位數(shù)字霉晕，實(shí)際上這相當(dāng)于對(duì)大數(shù)字進(jìn)行截取成為小數(shù)字庭再，本質(zhì)是和馮諾依曼截取平方數(shù)字的中間部分是一個(gè)道理。
用0x開頭表示是16進(jìn)制牺堰，即不是0到9之后進(jìn)1位拄轻，而是0...9abcdef再進(jìn)一位，共0到f十六個(gè)數(shù)字萌焰。
運(yùn)行后會(huì)輸出一串隨機(jī)的數(shù)字哺眯。
看上去還不錯(cuò)，這個(gè)可能是目前最快的偽隨機(jī)程序算法扒俯，因?yàn)樗挥屑臃套俊⒊朔ê鸵莆徊僮鳌?/p>
歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識(shí)】
每個(gè)人的智能新時(shí)代
如果您發(fā)現(xiàn)文章錯(cuò)誤，請(qǐng)不吝留言指正撼玄；
如果您覺得有用夺姑，請(qǐng)點(diǎn)喜歡；
如果您覺得很有用掌猛，歡迎轉(zhuǎn)載~
END
