首页 >> 漫画 >> 文章

学界 vs. 商界Comments>>

发表于 2011-04-18 05:09 | Tags 标签:, , ,

原著: XKCD
汉化: Oicebot & Ent

恭喜你发现本文的秘密!
0x5f375a86来自一个传奇算法,出自John Carmack开发的《雷神之锤3》的3D引擎。

这个引擎的源代码里包括一个反平方倒数的算法,其速度要比标准的牛顿迭代法快上几十倍,而其中的关键是一行神秘的代码和一个莫名其妙的数字:[ i   = 0x5f3759df - ( i >> 1 ); // what the fuck? ] 。没有人知道Carmack是怎么发现这个数字的。普度大学的数学家Lomont觉得很好玩,于是自己从理论推导出了一个可能的最佳值0x5f375a86,和Carmack的接近但略微好一丁点,他很怀疑Carmack其实是用试错法找到原来的数的……于是Lomont写了一篇文章发表了这个算法,称之为“Fast inverse square root”。天知道还有多少这样的神奇算法藏在各种商业软件里,不为人知。

 

0
为您推荐

28 Responses to “学界 vs. 商界”

  1. entropy说道:

    理论上。。。。。这种事情确实可能存在。

    不过一般而言,普通程序员干不出这种事情,大家向来都在忙着重复发明轮子。

    • zz说道:

      重复发明轮子是程序员成长的必经之路,哈哈

    • SuperLucky说道:

      没有办法啊,你不重复发明轮子没人会认为你能造的出轮子……

  2. diesirae说道:

    真能刷教科书的牛人应该也不会蹲在一公司当程序员吧……

  3. lohu说道:

    思维不同,效果不同

  4. 瓶子说道:

    0x5f375a86比0x5f375a86更优?

  5. 瓶子说道:

    错了,0x5f375a86比0x5f3759df更优?

    • aa12说道:

      兄弟,更好的那数是穷举出来的
      而这个数字发明的当事是啥时候?95年?反正SGI红火的那阵
      那阵的电脑你穷举去啊?
      这就能看出来最初那个数字的发现者的NB之处了

  6. lamda说道:

    真实

  7. 养生网说道:

    隔行如隔山!

  8. digiter说道:

    找数这种工作作为工程师而言当然是用电脑搜出来了,32bit整数约有2*10^9,用随机化算法搜个近似解还是可行的

    • aa12说道:

      情况不一样,之前瓶子说的那个数是个快速开放函数的Magic Number
      里面涉及的东西多了,比如说浮点数的2进制特性等等,能想到就已经够NB了
      具体数字的效率只能带入一次测一次速度,而这个函数被开发的时候大概是95年前后,那时候电脑才多快?

      • aa12说道:

        开方函数*

        • digiter说道:

          那些思路确实很NB。现在的电脑按每秒10^8算,用摩尔定律推回到95年就大概是10^5,对于枚举10^9的空间需要10^4秒,大约为3个小时

    • 骑士说道:

      其实,就是将反向平方根用待定系数法来解(能有这个想法很nb,也是核心)
      =》
      变换后就是一个超越方程,没有标准解,因此用枚举法
      =》
      用反馈控制来修正结果(方程大于0还是小于0),配合折半查找逼近,计算复杂度并不高。

      • 墨久说道:

        我第一次在论坛里面发现有这么专业的套路,我可以负责任的说,以上内容超过了商学专业的大学数学的水平

  9. atusoft说道:

    写的程序越多,越想去学术圈发展了

  10. 兔子说道:

    本文意思就是,想发个计算机SCI很简单,去读WINDOWS95源码就成了

  11. lic说道:

    特地回帖膜拜卡大神

  12. nipper说道:

    “48小时,200行代码……”句句血泪啊!
    对中断处理,必须在n个指令周期内圆满完成的,泪流状路过……

  13. 那个家伙不是还活着吗?说道:

    John Carmack,问问他不就好了?

  14. 生命收割者说道:

    虽然计算机专业……毕竟才大一,看不懂啊!!!求解释!!!

    • kkk说道:

      也就是如果你为自己写代码,结局如上图;如果你给别人打工,结局如下图

  15. 墨久说道:

    人类进步的两个理由:好奇心、对财富的渴望
    所以商业软件中发现这个,可以理解~