随机数大家都会用，但是你知道生成随机数的算法吗？( 二 )
这个算法的作者是大名鼎鼎的计算机之父冯诺依曼 ， 自从他确定了计算机体系结构之后一直沿用至今 。 他当时推崇这一算法的原因很简单 ， 计算方便 ， 速度快 ， 也容易排查错误 。 它认为如果真的设计一个复杂的算法来生成看起来比较好的随机数 ， 可能隐藏的bug比解决的问题还要多 。
seed = 2333def random: global seed seed = seed ** 2 return int(str(seed)[1:5])我写了代码实际运行了一下 ， 结果看起来其实没有那么不靠谱 。
文章插图
文章插图
LCG算法冯诺依曼的随机数算法虽然看起来简单 ， 但是非常草率 ， 在很多场合下是显然不能使用的 。 所以人们又想出了新的算法 ， 这个算法也很简单 ， 看起来英文缩写高大上 ， 其实翻译过来是线性同余法 。 也就是利用来生成随机数 。
最后返回的结果是上述式子计算之后的结果 ， abc三个数都是我们选定的参数 。 当下一次随机的时候 ， 就将上次的结果作为新的种子进行计算 。 我们写出它的递推公式就是：
这个算法一眼就看明白了 ， 它的核心完全在于abc这三个参数的选择 。 如果选的不好就不能实现随机数的效果 ， 这里我给大家分享一个业内常用的选择 ， a=25214903917 ， b=11 ， c= 。 这些数不是拍脑袋随便选的 ， 而是计算学家们算出来的 。 实际上Java JDK当中Random的类采用的就是这样的算法 。
seed = 2def lcg: global seed seed = (25214903917 * seed) & ((1 << 48) - 1) return seed这种算法实现方式也非常简单 ， 并且得到的效果也不错 。 如果要增加随机性 ， 我们还可以在输出结果上做一些优化 ， 比如进行位移或者是调换二进制位的顺序等等 。 但是这种算法也有缺点 ， 就是它的计算方式是固定的 ， 只是随机种子未知 。 只要愿意 ， 我们是可以通过得到的随机结果去反推这些参数的 。
这并不是一个复杂的算法 ， 因此LCG算法得到的随机数不能应用在一些高安全级别的应用上 ， 否则可能会有安全隐患 。
文章插图
梅森旋转算法LCG算法实现的伪随机数效果还不错 ， 但是周期不够长 ， 很容易被黑客推算出随机种子 。 后来两个日本学者又研究提出了新的伪随机数算法 ， 在这个算法当中用到了梅森素数 ， 所以称为梅森旋转算法 。
简单介绍一下梅森素数 ， 梅森素数的意思是形如的素数 。 利用梅森素数的性质可以设计出周期长度为梅森素数长度的随机数周期 。 比如目前Python、C++11等语言当中用的随机数计算包都是用的这种算法 。 目前常用的版本周期是 ， 这是一个巨大的天文数字 。
梅森旋转算法的实现原理非常复杂 ， 网上的资料也不多 ， 我看过一些都不是非常好懂 。 这里就不介绍了 ， 大家感兴趣可以去了解看看 。 但我个人觉得意义不大 ， 因为实在是用不到 ， 面试也完全不会考 。
虽然梅森旋转算法的周期非常非常长 ， 但是仍不是安全的随机数算法 ， 仍然有可能会被黑客破解 。 只不过和LCG算法相比 ， 被破解的概率以及难度增加了许多 。
大家可能很好奇 ， 什么样的算法才是安全的呢？其实业内的安全算法其实挺取巧的 ， 一般的常用方法就是利用一个数学界的难题来设计一个算法 。 比如RSA加密算法 ， 利用的就是大整数因式分解的问题 。 这样的问题业内除了暴力计算没有好方法 ， 而暴力计算的复杂度非常非常高 ， 根本不可能在有限时间内有解 ， 自然这个就是一个安全的算法了 。 如果某位黑客有能力设计出破解的算法来 ， 他根本也不用破解啥 ， 只要把解法发表成论文 ， 自然可以名利双收 。
推荐阅读
- 印专家：中国不可怕，可怕的是它都已经领跑6G了各国还在争5G
- 谷歌“跨年夜”Doodle带大家一起倒计时
- 小姐姐们的心头好，这些手机为啥这么受欢迎
- 实体店一箱牛奶50元，为何网上只卖25元
- 笔记本保养有妙招！学会这几招笔记本再战三年
- 觉得自己听力一天不如一天？会是耳机惹得祸吗
- 除了 Markdown 编辑器，你还需要会用程序来处理它
- 详解工程师不可不会的LRU缓存淘汰算法
- 你真的会用iPhone吗？14个iOS实用技巧，你未必都知道
- 小米11取消附赠充电器？响应环保的理由，大家会接受吗？