有哪些模拟随机数的算法(随机数大家都会用)
有哪些模拟随机数的算法(随机数大家都会用)
2024-11-25 06:10:45  作者:逍謡偉  网址:https://m.xinb2b.cn/tech/gnm312297.html

今天我们来和大家聊聊随机数

大家如果学过编程对于随机数应该都不陌生,应该或多或少都用到过。再不济我们每周的抽奖都是用随机数抽出来的,我们用随机数的时候,往往都会加一个前缀,说它是伪随机数,那么这个伪随机数的伪字该怎么解释,什么又是真随机数呢?

真伪随机数

目前学界划分真伪随机数的方式非常简单,一句话就能说明白,凡是用一定的算法使用程序生成的都是伪随机数,通过物理现象产生的随机数才是真随机数。也就是说计算学家们已经证明了仅仅依靠算法是无法生成真随机数的,也可以认为这是一个NP问题。

算法生成的都是伪随机数的证明太过复杂我们可以不去深究,但是什么又叫做物理现象产生的随机数呢?其实也很简单,举个很简单的例子就是抛硬币和掷骰子。当然物理现象不止这些,比如还有电子元件的噪音、元素的衰变等等。

真假随机数之间的最大差别在哪里?其实就在是否可以预测上。计算机算法得出的各种随机数之所以是伪随机数是因为它们的结果都是可以预测的,只要我们知道算法和起始状态以及各种参数,就可以预测下一次随机出来的结果。而真随机数则无法预测,就是纯粹随机的。

但问题来了,抛硬币和掷骰子这些物理现象又是真的随机吗?如果我们知道了硬币的起始状态以及抛掷的角度和力度,是不是可以预测硬币抛掷的结果呢?进一步我们是否可以假设,如果我们能知道所有例子的所有状态,是否所有所谓的随机数都是可以预测的呢?但根据量子力学的测不准原理,我们知道我们无法同时知道粒子的位置和动量,不仅说明了我们无法预测,也说明了我们无法假设预测。

所以某种程度上来说物理现象是不是就是真随机,这就成了一个哲学问题。但至少在计算机领域当中,这个问题是明确的,算法得出的都是伪随机数,只有通过物理现象得出的才是真随机数。

在计算机系统当中,伪随机数都是有周期的,只要我们持续的次数足够多,就可以看到这种周期。而真随机数则不存在这种周期,有一位前辈做过一个随机数可视化实验,也就是把随机数得到的结果做成图片。我们可以直观地对比一下,这是真随机数可视化之后的图片:


看起来像不像是以前的电视收不到信号的时候显示的内容?我们再来看看通过算法生成的伪随机数可视化之后的结果:


对比一下还是挺明显的,明显可以看出来伪随机数是有规律的,这个规律体现出来就是图像当中的纹理。如果大家想要获取真随机数,可以访问random.org这个网站,它是免费的,我们可以人为设置上下限来获取指定范围内的随机数。

对比过真伪随机数之后,我们再来看看现在计算机系统当中常用的伪随机数生成算法的原理。

平方取中法

我们首先介绍的是平方取中法,这个方法非常简单粗暴,是用来产生四位随机数的。

具体的逻辑是怎样的呢?首先我们需要一个随机种子,比如2333,我们把这个随机种子进行平方,得到5442889。这个数一共有6位,我们给它左边填充一个0变成05442889,最后取出它的中间四位是4428,这就是我们随机得到的结果。当我们下次再计算随机数的时候,随机数的种子就成了4428。

这个算法的作者是大名鼎鼎的计算机之父冯诺依曼,自从他确定了计算机体系结构之后一直沿用至今。他当时推崇这一算法的原因很简单,计算方便,速度快,也容易排查错误。它认为如果真的设计一个复杂的算法来生成看起来比较好的随机数,可能隐藏的bug比解决的问题还要多。

seed=2333defrandom():globalseedseed=seed**2returnint(str(seed)[1:5])

我写了代码实际运行了一下,结果看起来其实没有那么不靠谱。


LCG算法

冯诺依曼的随机数算法虽然看起来简单,但是非常草率,在很多场合下是显然不能使用的。所以人们又想出了新的算法,这个算法也很简单,看起来英文缩写高大上,其实翻译过来是线性同余法。也就是利用ax b mod c来生成随机数。

最后返回的结果是上述式子计算之后的结果,abc三个数都是我们选定的参数。当下一次随机的时候,就将上次的结果作为新的种子进行计算。我们写出它的递推公式就是:


这个算法一眼就看明白了,它的核心完全在于abc这三个参数的选择。如果选的不好就不能实现随机数的效果,这里我给大家分享一个业内常用的选择,a=25214903917,b=11,c=2^48。这些数不是拍脑袋随便选的,而是计算学家们算出来的。实际上Java JDK当中Random的类采用的就是这样的算法

seed=2deflcg():globalseedseed=(25214903917*seed)&((1<<48)-1)returnseed

这种算法实现方式也非常简单,并且得到的效果也不错。如果要增加随机性,我们还可以在输出结果上做一些优化,比如进行位移或者是调换二进制位的顺序等等。但是这种算法也有缺点,就是它的计算方式是固定的,只是随机种子未知。只要愿意,我们是可以通过得到的随机结果去反推这些参数的

这并不是一个复杂的算法,因此LCG算法得到的随机数不能应用在一些高安全级别的应用上,否则可能会有安全隐患。

梅森旋转算法

LCG算法实现的伪随机数效果还不错,但是周期不够长,很容易被黑客推算出随机种子。后来两个日本学者又研究提出了新的伪随机数算法,在这个算法当中用到了梅森素数,所以称为梅森旋转算法

简单介绍一下梅森素数,梅森素数的意思是形如2^n - 1 的素数。利用梅森素数的性质可以设计出周期长度为梅森素数长度的随机数周期。比如目前Python、C 11等语言当中用的随机数计算包都是用的这种算法。目前常用的版本周期是2^19937 - 1,这是一个巨大的天文数字。

梅森旋转算法的实现原理非常复杂,网上的资料也不多,我看过一些都不是非常好懂。这里就不介绍了,大家感兴趣可以去了解看看。但我个人觉得意义不大,因为实在是用不到,面试也完全不会考。

虽然梅森旋转算法的周期非常非常长,但是仍不是安全的随机数算法,仍然有可能会被黑客破解。只不过和LCG算法相比,被破解的概率以及难度增加了许多。

大家可能很好奇,什么样的算法才是安全的呢?其实业内的安全算法其实挺取巧的,一般的常用方法就是利用一个数学界的难题来设计一个算法。比如RSA加密算法,利用的就是大整数因式分解的问题。这样的问题业内除了暴力计算没有好方法,而暴力计算的复杂度非常非常高,根本不可能在有限时间内有解,自然这个就是一个安全的算法了。如果某位黑客有能力设计出破解的算法来,他根本也不用破解啥,只要把解法发表成论文,自然可以名利双收。

你看随机数这么一个常见的功能下面居然隐藏了这么深的科学原理,而且更加震惊的是以我们人类如此厉害的文明,居然连随机一个数都做不到。不知道大家看到这里又有何种感受呢?

今天的文章就到这里,衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话,请来一个三连支持吧~(点赞、关注、转发

本文始发于公众号:TechFlow,求个关注

  • 挂面做法好吃简单(做挂面的方法)
  • 2024-11-25做挂面的方法取一整颗的大蒜,剥掉外皮,清洗干净,然后剁成蒜头碎,备用将买来的葱清洗干净,切掉根部,然后将葱切成葱花,备用在锅里放入适量的水,待水烧开以后,将面条放入锅中,然后再次将水煮开,将面条煮熟,然后捞出滤干。
  • 电动车新国标真的要到了吗(关于新国标电动车)
  • 2024-11-25关于新国标电动车近两年时间“新国标”这个词汇频繁出现在我们的视野中,而且可以明显地感觉道路上对电动车的管制也愈来愈严格,不少用户也因此或多或少收到过交警叔叔的问候,那么到底什么是新国标呢?下面胖编就简单地给大家普及一。
  • 永春香业产值(传统篾香产业的电气化之路)
  • 2024-11-25传统篾香产业的电气化之路11月13日,工人在福建省永春县达埔镇的一家制香公司晒香新华社记者宋为伟摄福建省永春县达埔镇是全国主要篾香生产基地之一,近年来,该县积极推进传统制香工艺电气化,传统企业联合供电部门共同参与电气化制香机。
  • 古董局中局李现电影(春节档预售明日开启)
  • 2024-11-25春节档预售明日开启1月20日周四,全国共排31.4万场,观影人次约112.8万根据初步统计产出票房4170万#穿过寒冬拥抱你#860万,累计8.44亿;#误杀2#612万,累计10.36亿;#李茂扮太子#550万,累计。
  • 72岁许冠杰香港街头(香港歌神许冠杰72岁生日)
  • 2024-11-25香港歌神许冠杰72岁生日本文编辑剧透社:年年未经授权严禁转载,发现抄袭者将进行全网投诉今天是有香港“歌神”之称的许冠杰(Sam)72岁的生日许家在9月份有三位寿星,大哥许冠文和长子许怀欣都是9月生日许冠文今年78岁,许怀欣4。
  • 广安市附近旅游景区推荐(广安十大乡村旅游点位发布)
  • 2024-11-25广安十大乡村旅游点位发布人间四月天,正是踏青春游好时节如果你还不知道出发去哪,不妨跟着小编,一起走遍广安的乡野村落,伴着春日暖阳观美景、品美食、住民宿,感受乡村生活的美好与舒适!1.白坪-飞龙乡村旅游度假区国家4A级旅游景区。
  • 老鼠是财神的说法(俗语夏至逢老鼠)
  • 2024-11-25俗语夏至逢老鼠夏至来了,就在今天!依据天文历法计算后得出的结果,2021年夏至交节的日子是6月21日,也就是今天具体的时刻为11点32分0秒,从现在开始到今年的夏至完成交节满打满算也只有区区2个多小时的时间了夏至是。
  • 暮白首容婳扮演者(容婳扮演者资料)
  • 2024-11-25容婳扮演者资料暮白首容婳扮演者是张慧雯张慧雯,1993年9月13日出生于江西省鹰潭市,中国内地影视女演员,毕业于北京舞蹈学院2010级本科民族民间舞专业2014年,张慧雯因出演张艺谋执导的电影《归来》而获得第九届亚。
  • 登高望远后面句子接什么(登高望远)
  • 2024-11-25登高望远2022.10.21,因疫情期间不能远行,就近山上转转黄龙山路鸿门寺向北,经黄龙洞上山顶,这一带山上原有日本鬼子炮楼十三座,此处山顶是九号炮楼遗址今年山顶修建了健身步道,在部分炮楼遗址修建了仿炮楼亭子。
  • 油根染花好不好(植物染羊毛线蓝)
  • 2024-11-25植物染羊毛线蓝又到一年中最寒冷的季节,想起了毛线这两年染得少了,翻看旧照,又看见5年前为客户做的段染毛线,颜色不少,先发两个颜色供欣赏:羊毛线属于天然蛋白质纤维,用化学合成染料染色实在是糟蹋了只有用天然染料染色才是。
  • 网上买的热水器能退吗(南宁一男子购买热水器后申请退款)
  • 2024-11-25南宁一男子购买热水器后申请退款去年底,南宁的蒋先生在苏宁易购江南万达店购买了一款6000多元的热水器但他发现该热水器在苏宁其他门店的价格更便宜,便申请了退款,商家也同意了可是如今已经快一个月了,钱却迟迟未到账1月26日,苏宁易购江。
  • 蒙娜丽莎的画像到底发现了什么(蒙娜丽莎里藏了惊天秘密)
  • 2024-11-25蒙娜丽莎里藏了惊天秘密谈到西方经典艺术,文艺复兴是个高亮的关键词整个西方艺术的大厦,便是建立在文艺复兴的基础之上;整个现代文明的宽广大河,发源于文艺复兴的怀疑和探索精神文艺复兴,已成为西方艺术的代名词“文艺复兴”这场在15。