[閒聊] 老遊戲的變態程式碼

[Senkanseiki (戦艦棲姫)]

https://www.youtube.com/watch?v=n2Q1Sp7iew4
https://en.wikipedia.org/wiki/Fast_inverse_square_root

1999年製作的一款遊戲：Quake III Arena
在遊戲開發者之間，這款遊戲的程式碼成為了熱門話題
因為下面這個求1/√x的程式碼實在太變態了而讓大家頗為驚訝

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 hacking
        i  = 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;
}

影片中有解說這個程式碼在幹什麼
簡單來說就是用好計算的加減乘除來取代複雜的求平方根的過程
因為現代電腦計算速度夠快，直接叫電腦求平方根也可以

但這款遊戲是1999年出的，求平方根這件事情是為了計算光影的強度
因為會影響到光影的計算速度，就算有一點誤差也希望可以大幅提速
畢竟就算有誤差，1%的明亮度差異應該大多數的人不會在意，所以速度比較重要

具體做了什麼可以參考影片內容
這個程式碼似乎是由某位數學教授想出來的
然後這個遊戲的製作人把數學教授的想法拿來活用的結果

各位有看過這種變態程式碼嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.64.25.104 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1753173942.A.9A6.html
→ gcobc12632: 雷神之鎚3算很有名的案例了吧
→ gcobc12632: 主要是0x5f3759df這個魔術數字是怎麼出現的
→ haoboo: 雷神之槌3的magic number
→ yamis: 聽說是牛頓法算出來的
→ npc776: 卡馬克自己都不記得怎麼寫出來的 什麼時候變成數學教授了
推 ninnyshadow: 文組看不懂 誰能解釋的白話一點QQ
→ npc776: 用一句話把一件事講了個大概準確 在容量只有一行時 很神
推 SPDY: 這很有名啊 看注釋在WTF 就在嘴能用卻不能理解原理
→ vios10009: 這種東西都稱為魔術數字，把計算合在一起的結果，對於
→ vios10009: 低效能的電腦很有用，但沒任何註解就沒人知道怎麼來的
→ ack0011: 以前都要考慮有限的效能能做多少事情，現在都直接靠硬體
→ ack0011: 效能直接車過去，跑不動的請自己換頂級硬體
→ haoboo: 性能有限的時候拿來快速跑出近似解而不是最佳解
→ lazioliz: 卡馬克最近在開發AI的樣子
推 neetarashi: // what the fuck?  我有時候也會寫出這種註解w
推 RockZelda: 好像用到找平方根的牛頓-拉森佛方法
推 abysszzz: 這個案例好像蠻有名的，幾年前就看過有人講
推 lovez04wj06: 註釋應該是接手的人寫的吧，不然真就窮舉法了= =
→ npc776: 20年來都有人在講 不過算了 現在不弄短影音就沒人看過似的
→ nineflower: 數學不好要怎麼寫程式？
推 SPDY: 粗略來說就計算光線之類需要平方根倒數 老實算很慢
→ SPDY: 這個就減少計算浮點能用整數就好 快得多取得近似值
推 orze04: FIS啊 別問 用就是了
→ orze04: 這段的關鍵是WTF這段註解
推 SPDY: 那0x5f3759df也不是唯一能用 WiKi上有中文條目可看
推 meatybobby: 插值法吧 記得這個數字不是最佳解但也很接近了
推 tommy89082: 卡馬克也不是發明者，據說是從古早黑客論壇流出的
推 Aether13: 以前是用數學來幫助程式 例如1 + 到100 可以用for迴圈慢
→ Aether13: 慢sum 但用梯形公式更快 現在就是反過來用大量運算來模
→ Aether13: 擬某個行為後再分析結果 已經變成用程式來幫助數學了
推 wei115: 就是快速平方根倒數阿 那個常數比較神奇 數學論文只給出
→ wei115: 某個範圍的數當初值比較好 這個常數是最好的值
→ wei115: 有人就推測作者是直接窮舉 用程式跑完那個範圍的數 找出最
→ wei115: 好的那個值
→ qd6590: 這老熟了
推 llabc1000: // what the fuck
推 Porops: https://youtu.be/g1r3iLejTw0
→ Porops: 這個議題有人有做中文解說影片
推 ayaneru: 問就是wtf
推 orze04: 卡瑪克有說不是自己發明的，只知道是當時負責雷神之錘項
→ orze04: 目的一個碼農
推 Zchanya: 以前資結聽過介紹好像是用計算尺之類的去填表格 找出那個
→ Zchanya: 16制值
推 grtfor: 以前程式就是有很多創意的解，現在大概就直接問AI就完事
推 as920909: 最快的算法永遠是公式解 O(1)
→ PROMAC: 以前硬體性能不好激發各種創意
推 orze04: 比那個年代更早之前靠人力計算做出SR71和登月軌道
推 yeay: 老程式很常有這種magic number
推 supersusu: It just works
推 b325019: 很多影片都說明過這個數值
→ b325019: SR71最神奇的是他那顆引擎的
推 goisjkps: 遊戲偏前端 所以可以規劃遊戲的時候就先算好然後套數字
→ goisjkps: 進去來節省計算資源
推 kirimaru73: 那不是最佳解 只是誤差程度很變態
→ kirimaru73: 實際上用起來效率跟最佳解沒有多少差別 不用的話則是
→ kirimaru73: 爆慢
推 kirimaru73: 這種功能程式把數字寫死是合理的 當然要直接寫死
→ kirimaru73: 變態的是你為什麼知道那個數字
推 PetrVanis: 程式寫多一點都會遇到 大概是跑數值分析出來的值直接
→ PetrVanis: 套用
推 kor525: 太神啦
推 orze04: 最神奇是裡面沒有除法
推 devilhades: Old school電腦時代的藝術
→ deflife: 就牛頓法+浮點數表示法
→ JamesChen: 不就近似嗎，很直觀就會想到的啊
推 crazy6341556: 不是單純的近似 那個值怎麼找很有門道路
推 b325019: 這個快速算法的精髓就在於那個起始值的挑選
推 richer6605: 太神奇了
推 Bencrie: 古代硬體沒除法才會快啊 XD
→ Bencrie: 而且這東西希恰也出現過不少次吧