看上去很傻其实很聪明 哪些看上去很先进的事物其实早就发明了?

凑个趣。截至写作时间为止,估计没有比这个更早的了。以下正文。

拜现代社会满街走的码农所赐,现在估计很多人都知道这么一段程序:
float Q_rsqrt( float number ){long i;float x2, y;const float threehalfs = 1.5F; x2 = number * 0.5F;y = number;i = * ( long * ) &y; // evil floating point bit level hackingi = 0x5f3759df - ( i >> 1 ); // what the fuck?y = * ( float * ) &i;y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y;}这是一段据说来自quake 3源代码的函数,功能是计算平方根。这段程序特别神奇的地方是,他比公版平方根函数要快得多,基本上迭代一两次就能得到很高的精度;而更为神奇的地方是,这段程序之所以能做到这一点,全是因为一个看上去很像胡说八道的怪数。
请看程序中注释里面写作what the fuck读作我艹发生了什么那一行。0x5f3759df这个16进制32位数就是我们谈到的那个怪数。想当年老夫在水木看到一个帖子想学习一下有史以来最伟大的几个程序是怎么编的,看到此处就傻眼了。
不过今天我们不谈这个怪数,谈谈这个程序是怎么求平方根的。
平方根函数是不能用有限次加减乘除计算的。计算这类函数的方法一般有两种,一种是我们中学里学过的查表法,另一大类是以牛顿-拉夫逊法为代表的数值方法。
计算器不算,因为计算器一般使用的CORDIC算法是这两者的一种折衷。
一般来说介绍这个程序的文章都会重点介绍为什么上面提到的那个怪数这么有效,是怎么算出来的,人们如何试图改进而不得,以及如何考证出这个怪数不是如同传闻所言来自著名程序员John Carmack,作者已不得而知,等等;至于程序使用的计算方法(即程序的主要内容),一般只是一笔带过的说是牛顿-拉夫逊迭代。
上过高等数学的读者可以知道,牛顿-拉夫逊迭代基于函数的泰勒展开,是微积分对数值方法的一大贡献;而微积分是初等数学和高等数学的分界线,等等。
亲爱的读者,把这段程序称为牛顿-拉夫逊迭代是不错的,因为这段程序使用的迭代方法是牛顿-拉夫逊法的一个特例;但是在英语文献里这个方法一般叫做巴比伦法。
是的,你没看错,就是指那个古巴比伦。这个程序使用的迭代求解平方根方法是古巴比伦人发现的。
生活在公元前21-17世纪的古巴比伦人。
纸都没有,在泥板上写字的古巴比伦人。
下面这张照片中是考古发现的一块古巴比伦泥板,通称YBC 7289泥板。考古学家认为这泥板中的内容是一个巴比伦学生的作业。

这片泥板上写的东西是什么意思呢?可以看见泥板中画的是一个正方形。
正方形对角边上用楔形文字标明了一些数字,这些数字的值上图中有翻译,分别是1,24,51,10。我们知道古巴比伦人使用六十进制,所以这条斜边上的数是1+24/60+51/60^2+10/60^3。
翻译成十进制,这个数的值约为1.41421296。对,就是根号2。
直角边上的值是30,所以这位巴比伦学生算出斜边的长度是42+25/60+35/60^2,约等于42.4263888。
古巴比伦人显然没表可查。剩下的可能是,他们已经知道了如何使用迭代法求解平方根。
这块泥板的另一个标志是表明古巴比伦人已经知道了勾股定理。在这个姓名早已不可考的巴比伦学生刻出这块泥板的一千多年以后,古希腊的毕达哥拉斯重新发现了这个定理。他的学生希帕索斯证明了根号2不是有理数,因此被毕达哥拉斯判决扔到水里淹死。
如果古巴比伦人知道如何用迭代法计算平方根,一个合理的推断是他们说不定也知道有无限不循环小数这回事。这是公元前21-17世纪。
印度人发明阿拉伯数字两千年以前。
阿拉伯数学家解决一元二次方程问题的两三千年以前。
牛顿-拉夫逊法发现三千多年以前。
有时候我想,某个姓名已不可考的巴比伦数学家发现这个方法以后,会不会高兴得手舞足蹈?会不会用当时先进的耕田技术,把他发现的这个方法命名为牛拉法?
在巴比伦人发现迭代法之后四千年,公元二十世纪,一个姓名已不可考的计算机工程师找到了一个魔数0x5f3759df,改进了这个方法,使得无论求解任何数的平方根,都可以在两步以内达到四位以上的精度。
除了这个数,我们文章开头里提到的这个程序的其他部分,其起源可以追溯到四千年以前。

参考文献:
Chris Lomont, ""
David Fowler and Eleanor Robson, "Square Root Approximations in Old Babylonian Mathematics:YBC 7289 in Context",


//以下事后评论:
人来的不少,我很欣慰。
集中回答一下正文没说清楚的问题。集中回答一下正文没说清楚的问题。
1. 有知友指出能计算平方根不代表就一定是迭代法。
的确,这个正文中说得不清楚。实际上正文中贴出的YBC7289泥板里面的根号二很可能是查表所得。当然,这个表也是巴比伦人自己算出来的,不是得到外星启迪的产物。学界认为巴比伦人掌握迭代法的证据请参看我的第二个引用文献,里面提到了记录在BM96957和VAT6598两块泥板上的习题和题解,详细说明了巴比伦人使用的逼近方法。这道题是专门讲怎样求正方形对角线长度的。
2. 有知友指出fast inverse square root 求的是平方根倒数不是平方根。
这个属于我没说清楚。实际上计算机算法求平方根倒数和求平方根一般是用同一套算法,先求平方根倒数再乘以原数得到平方根。两者原理是一样的,但是求平方根的迭代算法中有一步需要使用变量除法,求平方根倒数则不需要。如果读者有硬件算法实现的经验就能知道计算机算变量除法是很麻烦的一件事,比变量乘法要慢得多,而且电路结构更复杂。所以计算机迭代一般是算平方根倒数,这样要比直接迭代算平方根快得多。
现在看来原文里面写四千年来就魔数法一个改进是不准确的,如评论所说写的时候激动了。
3. 关于两河文明究竟多先进。
其实老夫是个程序猴,并不懂考古。这篇文章的起源是五年前做混沌映射的FPGA实现的时候查到的。当时需要做cusp映射,需要用到平方根。熟悉离散混沌映射的朋友知道它对计算精度很敏感,硬件混沌发生器对运算速度要求不低,但是FPGA上又不可能做一个巨大的表来查。老夫头疼了半天,最后被魔数法搭救了,中间偶然看到了迭代计算平方根的历史沿革。所以如果有朋友想了解两河文明的就只好抱歉了,真的不懂。
如果有其他问题,欢迎继续留言评论。   2/2   首页 上一页 1 2

爱华网本文地址 » http://www.413yy.cn/a/81260103/8521.html

更多阅读

《看上去很美》影评 看上去很美 百度云

看上去很美》影评——对中国教育的反思《看上去很美》:一个叫方枪枪的男孩被父亲送进幼儿园,从天真活变得狡黠孤僻,最终,“逃”出幼儿园,在锣鼓喧天里呆呆地望着戴着大红花兴高采烈的从身边走过的人群。幼儿园对他或许已成为回忆,而对于

聂卫平三度婚姻妻子兰莉娅看上去很美图 聂卫平妻子

聂卫平三度婚姻妻子兰莉娅看上去很美(图)7月15日下午,“2009凤凰古城第四届世界围棋巅峰对决”新闻发布会暨晚宴在北京长城饭店举行,棋圣聂卫平携第三任夫人兰莉娅闪亮登场,活动进行中老聂和妻子一起频频向朋友们敬酒,棋圣婚姻梅开三度

看上去很美 迅雷下载 网上开店是不是仅仅“看上去很美”?

  网上开店与实体开店一样,都是需要用心去做才会有效果的。   网络上夸大其词多的去了,真正想要做好,还是要靠自己的努力。  当然开网店靠的就是图片和文字说明,所以这两样一定要做好。  看上去很美也可与实物相符,这样买家

家居饰品业:看上去很美

    在家居饰品店里,人们总能找到一些或许不那么实用,但却非常吸引人的小饰品。一个看上去老掉牙的挂钟、一个奇形怪状的花瓶,或者一张看不太懂的壁画,主人尽心将它们收罗到家中,一种叫品位的东西也就驻足在了新居里。     许

海外并购:看上去很美

  通过海外并购获得先进的技术、市场甚至品牌,看上去很美好,但是如何才能取得成功?  文 | 牛威 

声明:《看上去很傻其实很聪明 哪些看上去很先进的事物其实早就发明了?》为网友落魄女分享!如侵犯到您的合法权益请联系我们删除