查看原文
其他

一张纸对折103次,我们的宇宙就放不下它了吗?

以下文章来源于数字北京科学中心 ,作者北京科学中心

不知道大家小的时候是不是都听过这样一个故事:


相传,国际象棋起源于古印度,是由一位名叫西萨·班·达依尔的宰相发明的。

当时的舍罕王打算重赏国际象棋的发明者,于是宰相在国王面前提出请求:“陛下,请您在这张棋盘的第一个小格内赏我1粒麦子;第二个小格内给2粒,第三格内给4粒……照这样下去,每一格都比前一个小格加一倍。陛下啊,把这样摆满棋盘上所有格(共64格)的麦粒,都赏给您的仆人吧!”


国王慷慨地答应了宰相的要求,计数麦粒的工作很快就开始了。一袋又一袋的麦子被扛到棋盘前,但是麦粒数一格接一格增长得越来越迅速,国王很快就发现,即使拿出全印度的小麦,也无法兑现他对宰相许下的诺言!


那么这位宰相到底要求国王赏赐给他多少粒麦子呢?用中学数学所学的方法就可以算出,共需18,446,744,073,709,551,615个麦粒!


这个数字究竟有多大呢?

根据麦粒的重量,近似估算的结果大约为两千多亿吨,而即使是农业现代化技术高速发展的现在,全世界小麦的年产量也不过数亿吨而已!


虽然这个故事的真假已经无从考证,但是由它透露出的数学的神奇与宏大,无疑震撼了我们的心灵,这一令人惊叹的结果背后究竟隐藏着怎样的原理呢?


接下来,就让我们一起进入到今天要介绍的重点——“指数爆炸”


1

宇宙中放不下的纸

为了更形象地体现这一现象的威力,人们还提出了许多“国王与麦粒”故事的“变体”。

例如,一张厚度为0.1mm的纸,通过不断对折使厚度成倍增加,对折51次后,其厚度便可达到2.25亿千米,约为火星与太阳的距离。
而当对折次数达到103次时,其厚度已经超过了930亿光年,这是目前可观测宇宙的直径,也就是说,可观测宇宙内已经放不下这张纸了!

纸的厚度与对折次数正好满足指数增长的规律,其增长速度如爆炸般惊人,相信大家也已经从上面的两个小故事中体会到“指数爆炸”的威力了。

当然,上文说的都只是纯数学上的计算,在实际实验操作并不可行。有人做过实验,一张纸对折7次以上就已经非常困难了。

现代指数的概念是数学家笛卡尔在1637年引入的,他为乘方数设计了专门的记号系统,即指数函数

所谓“指数爆炸”也并不是真正的爆炸,而是指计算过程中,指数函数值的“爆炸性”增长。

2

无所不在的“指数爆炸”

天文,测量,航海,计算机和其他实用数学的分支中,常用到指数函数和它的各种性质,尤其是计算机编程领域,我们在解决问题时,经常会用到指数函数及其相关函数。


这时就要格外注意了,因为一旦处理不好,该问题在解决过程中,我们需要计算的数字很可能会膨胀到难以计算的地步。


相反,如果“指数爆炸”这一数学现象能够得到合理的利用,也可以大大减少计算步骤,成为帮助我们解决问题的利器。


>>>>密码越长就越安全?

我们在注册新的账户或者进行密码修改时,密码设置那一栏的旁边经常会提示我们所设密码的安全程度。

随着密码长度和所含数字、字母、符号种类的增加,密码的安全系数也会越来越高,这背后蕴含的原理就可以利用我们前面提到的“指数爆炸”来解释。


我们现在所使用的密码,是使用俗称“密钥”的随机字节流来进行加密的。


在加密算法没有漏洞的情况下,要想破解密码就必须“一个一个”地进行尝试,即列出与密钥长度相同的字节流,与密码逐一进行比对,直到找到正确的密钥,这种密码破译法又被称为“暴力破解”。


那么密码的长度又是如何影响密码的安全性的呢?


我们假设密码全部由两种数字(1和0)来表示。如果密码的长度只有3位,那么正确的结果必定是下列8种情况之一:


000,001,010,100,011,101,110,111


最多尝试8次就能成功将其破解。


而密码每增加一位,其可能出现的排列组合的种类就会增加一倍,破解密码所需要尝试的次数也随之翻倍。


随着密码位数的增加,暴力破解最多需要尝试的次数如爆炸般增长,破解难度和成本飞速增大。


那么,这种利用“指数爆炸”增加密码安全性的方法效果究竟如何呢?


在这里,小编就给大家举一个比较直观的例子,如果我们要破解一串512位的密码,并且每一位只可能是0和1两个数字中的任一个,需要多久才能尝试遍每种可能呢?答案如下:

这个数字意味着:即便有一台现代超级计算机,并从宇宙诞生的那一刻起就开始解密,不停地尝试各种数字的组合一直到现在(公元2020年),它也无法列举完这串密钥所有可能的情况。


>>>>程序员必备算法:二分法查找

二分法查找是计算机科学里常用的算法,它能帮助人们在一组有序数组中迅速找出某一特定的元素,其基本过程可以总结为:


从数组的中间元素开始,如果中间元素恰好是所要查找的元素,则搜索过程结束。


如果要查找的元素大于或小于中间元素,则在数组大于或小于中间元素的那一半开始,而且同最初时一样,也从中间元素开始比较。


这种算法的好处是,每一次比较都能使搜索的范围缩小一半。这可以看作是“指数爆炸”的另一种应用。


例如,我们怎样才能快速地在下列9个从小到大排列的数中寻找出数字4呢?


1 ,3 ,4 ,6 ,7 ,8 ,10 ,13 ,14


可能有的小伙伴会说,从第一个数开始检查呗,如果第一个数不是4,就查看第二个数,还不是,就查第三个,以此类推总能找到4在哪里。


想想看,如果4在这列数的最后一位,这种方法岂不是要比较所有位置的数吗?这个计算量是很大的。


然而,如果用刚才介绍的二分法,每次都从中间开始找起,仅需3次比较就能找到4在哪里,大大提高了效率。

随着数组的扩大,这一方式的优势也逐渐显现出来,例如,只需要判断10次,就能在2047个数据中找到目标元素。


运算20次就能在2097151个数据中找出想要的结果;而比较30次时,所能搜寻的数据范围甚至变成了2147483647个!


数学作为人类思维表达形式的一种,反映了人们积极进取的意志,缜密周详的推理,以及对完美境界的追求,它与我们的生活息息相关,它的魅力也一直影响着我们。


这篇文章中为大家简要介绍的指数爆炸,不过是无数瑰丽景象的冰山一角,数学世界中还有更多美丽动人的风景等待我们去欣赏和发掘,如果你恰好也对它感兴趣的话,不如就一起来探索一下,看看数学还会给我们带来哪些出人意料又合乎逻辑的惊喜吧!


来源:数字北京科学中心

编辑:lwk


近期热门文章Top10

↓ 点击标题即可查看 ↓
1. 跳水曾经真能躲子弹,但是现在行不通了
2. “太长不看”让我们失去了什么?
3. 驻波,竟然还可以这么好看!
4. 手机输入法的派别之争,九宫格和全键盘究竟哪种更科学?
5. 你喜欢“白板黑字”还是“黑板白字”?
6. 子弹打不碎的玻璃,我能掰碎?
7. 震惊!零下二十度在室外方便,竟然发生了这种事......
8. 来认识一下世界上最著名的那只茶壶
9. 手机电池在冬天为什么那么不耐用
10. 作为顶级数学家是一种怎样的体验?
 点此查看以往全部热门文章 

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存