[轉貼]没有显卡的年代，这群程序员用4行代码优化游戏

SIMON1016

[轉貼]没有显卡的年代，这群程序员用4行代码优化游戏

https://www.youtube.com/watch?v=g1r3iLejTw0

1. 
   
2. float Q_rsqrt( float number )
   
3. {
   
4.         long i;
   
5.         float x2, y;
   
6.         const float threehalfs = 1.5F;
   
7. 
   
8.         x2        = number * 0.5F
   
9.         y        = number;
   
10.         i        = * ( long * ) &y;        // evil float point bit level hacking
    
11.         i        = 0x5f3759df - ( i >> 1 );        // what the fuck?
    
12.         y        = *( float * ) &i;
    
13.         y        = y * ( threehalfs - ( x2 * y * y ) );        // 1st iteration
    
14. //        y        = y * ( threehalfs - ( x2 * y * y ) );        // 2nt iteration
    
15.                                                 //this can be removed
    
16.         return y;
    
17. }
    

複製代碼

補充內容 (2024-3-28 10:20 PM):
維基百科: 反平方根快速演算法
https://zh.wikipedia.org/zh-tw/平方根倒数速算法

補充內容 (2024-3-28 10:38 PM):
第10行.程式將浮點數y當作整數i來運算，
第11行.並用常數0x5f3759df減去i/2，
第12行.以結果轉回浮點數。
第13行.為牛頓法來提高精確度。

SIMON1016

這裡有文字說明
維基百科: 反平方根快速演算法
https://zh.wikipedia.org/zh-tw/平方根倒数速算法

程式中的「魔術數字」---作者：沈宜儒 / 臺灣大學計算機及資訊網路中心程式設計組資訊工程師
https://www.cc.ntu.edu.tw/chinese/epaper/0052/20200320_5209.html

alpine295

感謝大大分享，重複看了兩遍，還是沒完全懂，需要再回鍋學習。

jacson99

感謝大大分享，神留下的神祕數字，有看沒懂，
唯一欣慰的是我有玩過雷神之鎚 XD

jason680

這個很久以就看過好幾次...
當然一開始,也都是沒看懂...
只記得有一個magic number

最近剛好,又再看一次,稍微了解一些,可以寫一些簡單原理
詳細數學及公式,網頁上都有,因此只寫簡單概念原理.


0. 題目:
跟據維基百科提到,它是要算....距離,最後是標準化的向量.
網頁: ...此演算法正類如對歐幾里得空間的兩點求取其歐幾里得距離，...
最後,最耗時的計算是先開根號再取倒數(分之一).
最後主要(加速)求值任務,就成了網頁標題 反平方根快速演算法.

反平方根快速演算法 Fast Inverse Square Root
1. 要了解運算過程或原理就要了解浮點數儲存格式
  在電腦計算機中,浮點數是以 IEEE754規格為主的方式儲存

  浮點數(IEEE754)表示法跟科學記號表示法基本架構可以說是一樣的
  兩者差別僅在於十進位與二進位

  科學記號表示法 = a*10^n  , a為實數, 1<= a < 10, n為次方(指數)
  浮點數表示法    = a*2^n, , a為實數, 1<= a < 2, n為次方(指數)

  詳細規格,可以參考相關網頁:
  科學記號: https://zh.wikipedia.org/zh-tw/% ... 0%E6%95%B0%E6%B3%95
  浮點數IEEE754: https://zh.wikipedia.org/zh-tw/IEEE_754

2. 開根號
  浮點數表示法    = a*2^n 在IEEE754中, 其中a 固定為1.xxxx 最開頭固定為1(省略) (除了0.0以外)
  所以  開根號(浮點數)可以表示為  開根號(a*2^n)
  其中 開根號(A*B) = 開根號(A) *開根號(B)      <==各別開根號
  開根號(a*2^n) = 開根號(a)*開根號(2^n)
  在這裏 開根號(2^n) 可以說是可以很簡單算出
  最後重點在 開根號(a) , 1<= a < 2

  例:  開根號(2^6) = 2^3  (2的6次方 開根號 等於 2的3次方(6/2=3))
  註: 奇數次方=偶數次方+1次方, 最後有根號(2)的(固定)值.

  註: 這個不是反平方根快速演算法使用的主要方法,原理相同.(牛頓迭代法求值)
  開根號(a) = a^(1/2) ,  可以使用函數 y = f(x) = x^2-a = 0   用牛頓求根法

3. 牛頓迭代法求值
  牛頓法 維基: https://zh.wikipedia.org/zh-tw/%E7%89%9B%E9%A1%BF%E6%B3%95
  根號(5)影片: https://www.youtube.com/watch?v=am5Jp7PsFRs

  牛頓法求值中,有關微積分部分,請自行參考相關影片或資料,這就不細講.有需要可再詳加討論
  以下x用大寫來表示

    X(n+1) = Xn - ( f(Xn) / f'(Xn) )
    X(n+1) 表示 (下一個)迭代計算結果
    Xn 表示 X0, X1, X2, ..., Xn   
    X0是初值
    X1是用(初值)X0代入上面迭代公式,計算而得
    X2是用X1代入上面迭代公式,計算而得
    依此類推, Xn代入上面迭代公式,計算結果得出下一個值 X(n+1)
    當 Xn 已經很接近答案(根號(a)) 時,整個函數值f(X) = x^2-a 就會趨近於0(或等於0).
    這時下一個值X(n+1)跟當前值 Xn 就會差距很小或相等.

    相同原理 牛頓迭代法求根值跟求反平方根值,差別只在於X(n+1)公式不同而已.
    有興趣者,可自行研究或
    維基最後公式
     Y(n+1) = Yn (1.5 - (X*Yn^2)/2)
    這個X是浮點數中 a*2^n的a,所以也可以改成
     X(n+1) = Xn (1.5 - (a*Xn^2)/2)


3.magic number神奇魔數   
  在SIMON大 本帖影片解說10:30有提到是要縮小平均誤差.
  
  牛頓迭代法原本初值是可以任意設定,但一切都講求效率(要快)的情況下
  a的值介於1到2之間 (但log2(1+x) 約等於x  (實際為 x + 小寫sigma)
  神奇魔數 就是X0(初值), 維基百科最後也有討論 暴力窮舉及誤差最小...等等意題

最後個人簡單總結,對這個問題或這一段code要了解:
1. 一開始的問題 計算正規化向量
   3D圖形程式需要使用正規化向量來實現光照和投影效果...
2. 浮點數格式IEEE754
   浮點數表示法 a * 2^n ,其中  1<=a <2, n為次方
3. 牛頓迭代法求值
  通用公式  X(n+1) = Xn - (f(Xn)/f'(Xn))
4.  反平方根 的 迭代公式 (微積分)
  X(n+1) = Xn (1.5 - (a*Xn^2)/2)
5. magic number神奇魔數
  修正初值,減少 迭代次數.

註: 通常要有興趣,且要反覆多看幾次...

y25982

就像之前有用AB片開機片開機一樣!

時代的進步