PTT動漫區 / C_Chat (希洽)

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

看板C_Chat (希洽)作者 (petohtalrayn)時間6小時前 (2025/07/22 19:15), 6小時前編輯推噓21(21推 0噓 10→)
留言31則, 21人參與, 2小時前最新討論串3/3 (看更多)
i = * ( long * ) &y 把原本浮點數改成long整數的目的 最主要是因為浮點數的紀錄方式可以用來近似成該數字取對數的值 也就是這個動作實際上是在取log(y)的近似值（乘以2^23然後再加上常數） i = 0x5f3759df - ( i >> 1 ); 既然取了對數，那要求原本的數字的根號，只要取對數後的數值除2就好 而二進位數字除2很簡單，就跟10進位數字除10一樣，移一格就好 然後前面的0x5f3759df這個數字是用來調整結果的常數，俗稱魔法數字 因為根號的函數是曲線，這個運算則是直線方程式，會稍微有誤差 實際上最神的也是這個常數，你要怎麼找到誤差最小的常數就是這個運算方式的關鍵 y = * ( float * ) &i; 經過簡單的加減乘除之後，再把原本的整數變回浮點數 也就是把取了log的數字還原成原本的數字 到這一步得到的結果誤差大概5%以下 y = y * ( threehalfs - ( x2 * y * y ) ) 這個則是牛頓法求根，不知道牛頓法是什麼的請去下面這個wiki然後看中文版解說 https://en.wikipedia.org/wiki/Newton%27s_method 簡單來說就是大概把上面那個5%以下的誤差縮小到1%以下 因為原本找到的答案就已經很接近了，用牛頓法可以輕易找到誤差更小的數字 而牛頓法是用越多次誤差會越小，因此原本的程式碼中用了2次， 但工程師認為沒有必要用到2次，1次的誤差就夠小了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.64.25.104 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1753182946.A.234.html ※ 編輯: kuoyipong (61.64.25.104 臺灣), 07/22/2025 19:16:30
推
07/22 19:17, 6小時前 , 1F
：0
07/22 19:17, 1F
→
07/22 19:25, 6小時前 , 2F
其實我覺得整個過程裡面最魔法的是轉浮點數那個步驟
07/22 19:25, 2F
→
07/22 19:25, 6小時前 , 3F
誰ㄊㄇ知道浮點數可以拿來做對數的近似啦
07/22 19:25, 3F
→
07/22 19:26, 6小時前 , 4F
這就是指標的奧妙之處
07/22 19:26, 4F
推
07/22 19:28, 6小時前 , 5F
所以時間複雜度比原本少多少R?
07/22 19:28, 5F
推
07/22 19:29, 6小時前 , 6F
近似log那個學過浮點數知道52位餘數不難理解吧？
07/22 19:29, 6F
推
07/22 19:30, 6小時前 , 7F
log(1+x)和x在0,1間近似，魔法數字就是補償這個誤差
07/22 19:30, 7F
推
07/22 19:30, 6小時前 , 8F
這就O(1)了吧
07/22 19:30, 8F
→
07/22 19:32, 6小時前 , 9F
事後聽講解當然可以理解 問題是怎麼想到的
07/22 19:32, 9F
推
07/22 19:32, 6小時前 , 10F
order多少看你要的精度
07/22 19:32, 10F
推
07/22 19:33, 6小時前 , 11F
第二點那個以前聽到後真的覺得扯
07/22 19:33, 11F
→
07/22 19:34, 6小時前 , 12F
啊被騙了 不完全跟著log值
07/22 19:34, 12F
推
07/22 19:43, 6小時前 , 13F
黃字第一和第三是不是講反了
07/22 19:43, 13F
→
07/22 19:45, 6小時前 , 14F
學術論壇就該如此
07/22 19:45, 14F
推
07/22 19:54, 6小時前 , 15F
有趣
07/22 19:54, 15F
→
07/22 19:58, 6小時前 , 16F
回p3一串數字 小數與大數最早有兩種形式 用10的次方的科學
07/22 19:58, 16F
→
07/22 19:59, 6小時前 , 17F
計數法以及用二的次方的數位計數法 因為標準是後者
07/22 19:59, 17F
→
07/22 20:00, 6小時前 , 18F
以電腦的處理可以非常有效率地求出次方近似
07/22 20:00, 18F
推
07/22 20:01, 6小時前 , 19F
p3一串數字XDDDDD
07/22 20:01, 19F
推
07/22 20:03, 6小時前 , 20F
我也是這麼覺得
07/22 20:03, 20F
推
07/22 20:05, 6小時前 , 21F
原來如此 這樣說就還是沒懂
07/22 20:05, 21F
推
07/22 20:20, 5小時前 , 22F
是學術,讚歎
07/22 20:20, 22F
推
07/22 20:20, 5小時前 , 23F
我覺得第一個evil hacking比較神
07/22 20:20, 23F
推
07/22 20:25, 5小時前 , 24F
型別位址轉型取址太酷了吧...原來可以這樣操作...
07/22 20:25, 24F
推
07/22 20:37, 5小時前 , 25F
學術論壇
07/22 20:37, 25F
推
07/22 20:45, 5小時前 , 26F
資源限制下的精妙演算 跟之前看16bit的感動裡面的做法類似
07/22 20:45, 26F
推
07/22 20:57, 5小時前 , 27F
嗯嗯跟我想的一樣
07/22 20:57, 27F
推
07/22 22:53, 3小時前 , 28F
這真的要歸功於當初設計浮點數格式的人再搭配上二進位的
07/22 22:53, 28F
→
07/22 22:53, 3小時前 , 29F
特性可以非常神奇的完成轉對數跟除以2
07/22 22:53, 29F
推
07/22 22:58, 3小時前 , 30F
當初看這個的算式解說搭配上ieee754的說明我大腦都星爆了
07/22 22:58, 30F
推
07/22 23:11, 2小時前 , 31F
話說後來好像有人算出更好一點的魔法數字
07/22 23:11, 31F
‣ 更多 kuoyipong 的文章
文章代碼(AID): #1eVtBY8q (C_Chat)
C_Chat 近期熱門文章
更多 近期熱門文章 >>
PTT動漫區 即時熱門文章
10
41
[資料] 1302
[ YUGIOH ]
youngluke
5小時前, 07/22
更多 即時熱門文章 >>
‣ 更多 kuoyipong 的文章
文章代碼(AID): #1eVtBY8q (C_Chat)