欢迎光临,嵌入式开源博客

0x5f375a86传奇算法-求平方根倒数

0x5f375a86来自一个传奇算法(求平方根倒数),此算法最早被认为是由约翰·卡马克所发明(发明时这个值为0x5f3759df,后来由Lomont通过暴力穷举找到这个更优值),但后来的调查显示,该算法在这之前就于计算机图形学的硬件与软件领域有所应用,如SGI和3dfx就曾在产品中应用此算法。

由来

就现在所知,此算法最早由Gary Tarolli在SGI Indigo的开发中使用。虽说随后的相关研究也提出了一些可能的来源,但至今为止仍未能确切知晓此常数的起源。
这个引擎的源代码里包括一个反平方倒数的算法,其速度要比标准的牛顿迭代法快上 4 倍,而其中的关键是一行神秘的代码和一个莫名其妙的数字:[ i = 0x5f3759df – ( i >> 1 ); // what the fuck? ] 。没有人知道Carmack是怎么发现这个数字的。普度大学的数学家Lomont觉得很好玩,决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。Lomont也是个牛人,在精心研究之后从理论上也推导出一个最佳猜测值,和卡马克的数字非常接近, 0x5f37642f。卡马克真牛,他是外星人吗?
传奇并没有在这里结束。Lomont计算出结果以后非常满意,于是拿自己计算出的起始值和卡马克的神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了… 谁也不知道卡马克是怎么找到这个数字的。最后Lomont怒了,采用暴力方法一个数字一个数字试过来,终于找到一个比卡马克数字要好上那么一丁点的数字,虽然实际上这两个数字所产生的结果非常近似,这个暴力得出的数字是0x5f375a86。
Lomont为此写下一篇论文,”Fast Inverse Square Root”。
赞(3) 打赏
未经允许不得转载:Huangea Blog 嵌入式博客 » 0x5f375a86传奇算法-求平方根倒数
分享到: 更多 (0)

评论 7

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    一个博客能让人流连忘返,讲真,靠的是实力!

    zhixie4个月前 (05-12)回复
  2. #2

    I really can’t believe how great this site is. Keep up the good work. I’m going to tell all my friends about this place.

    Georgie Digmann4个月前 (05-26)回复
  3. #3

    让人百看不厌的博客,真的不是很多!

    巨根增大网4个月前 (06-01)回复
  4. #4

    这个博客就像一座宝藏,我是来掘金滴!

    藏金网4个月前 (06-07)回复
  5. #5

    第一次看,感觉还挺新鲜!

    kitty233个月前 (06-18)回复
  6. #6

    炎热夏天,闲来无事,拜读博客,消暑解闷!

    9483个月前 (06-22)回复
  7. #7

    从百度点进来的,学习学习,呵呵!

    爱就爱啦3个月前 (07-03)回复

一个很有意思的网站

留言板友链

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏