中间平方法 Middle-square method
"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."
--John Von Neumann.
世界上第一台计算机是 1945 年制造的 ENIAC. 现代计算机之父冯诺依曼 John Von Neumann 在它的基础上改进成为真正意义上的现代计算机.
而在这个时候, 计算机刚刚起步的时候, 冯诺依曼就说了这么一句话, 如果谁想用数学方法生成随机数字, 那么他一定是落入了原罪.
冯诺依曼是博弈论的创始人, 在量子力学方面也很有成就, 在他开启计算机时代之初, 就指明了真随机不可能依靠数学和计算机方法实现.
但为了计算机的制造, 冯诺依曼发明了一个很粗糙的伪随机 PRNG 方法: 中间平方法.
给定一个六位数作为种子, 比如 675248, 那么先把它平方, 比如得到 455959861504, 然后再掐头去尾取中间 6 个数字, 把它当做随机数结果, 如图中的 959861. 当然这个计算流程可以继续重复下去, 就能得到一些列随机六位数.
Python 代码如下:
- seed_number = int(input("请输入一个六位数:"))
- 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} 步之后出现重复数字{number}.")
对于 6 位数来说, 一般在数百次之后就会发生重复循环. 这随机方法真的很粗糙.
威尔的 PRNG
20 世纪 30 年代兴起的普林斯顿高等研究院 IAS 可以说是自然科学的圣地, 爱因斯坦, 计算机理论先驱哥德尔, 原子弹之父奥本海默, 现代计算机之父冯诺依曼, 日本数学家小平邦彦和华裔物理学家杨振宁, 李政道都曾在此学习或工作.
冯诺依曼是个犹太人, 原本居住匈牙利, 然而由于希特勒的统治影响, 他来到了美国. 而把他介绍到普林斯顿的正是另一位伟大的科学家赫尔曼. 威尔 Hermann Weyl.
威尔这次又改进了冯诺依曼的中间平方随机程序.
这是一段 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());
- }
- }
双箭头在这里是移位操作,<<相当于乘以 2 的 32 次方,>>则是除以 2 的 32 次方.
这里的思路是每次都把种子 x 平方, 并且加上一个 w, 而且 w 每次都增大 s, 这里 s 是个很大十六进制数字, 它足以超过 2 的 32 次方.
注意 x,w,s 都是 uint64, 是 64 位的, 而 msws()返回的是 uint32 位数字, 实际上这相当于对大数字进行截取成为小数字, 本质是和冯诺依曼截取平方数字的中间部分是一个道理.
用 0x 开头表示是 16 进制, 即不是 0 到 9 之后进 1 位, 而是 0...9abcdef 再进一位, 共 0 到 f 十六个数字.
运行后会输出一串随机的数字.
看上去还不错, 这个可能是目前最快的伪随机程序算法, 因为它只有加法, 乘法和移位操作.
来源: http://www.jianshu.com/p/5beb807cf25b