前幾天翻到一段源自雷神之槌(Quake III)的平方根倒數源碼,網上關於它原理的介紹已經很多,這裡就不再重複推導了。
原始實現是用 C 語言寫的,靠位運算加上牛頓迭代一次,把 1/√x 的計算壓到極致。我看完之後冒出一個念頭:這套玩法在 JavaScript 裡能不能照樣跑起來?答案是可以,關鍵在於用 ArrayBuffer 和 DataView 拿到底層的 32 位浮點與整數視圖,模擬出 C 語言裡的指針型轉換。
function InvSqrt(x){ var h=0.5*x; var b=new ArrayBuffer(4); var d=new DataView(b,0); d.setFloat32(0,x); var i=d.getInt32(0); i=0x5f375a86-(i>>1); d.setInt32(0,i); var r=d.getFloat32(0); r=r*(1.5-h*r*r); return r; }
接着跑一組對比測試,各循環一千萬次:
console.time("t"); for(var i=0;i<10000000;i++){ InvSqrt(i); } console.timeEnd("t"); console.time("t"); for(var i=0;i<10000000;i++){ 1/Math.sqrt(i); } console.timeEnd("t"); VM2303:18 t: 33438.000ms VM2303:24 t: 16720.000ms
結果很直白:手寫版本耗時約 33 秒,原生 Math.sqrt 只要 16 秒出頭,整整快了一倍,而且精度上還吃虧。畢竟現代 JS 引擎已經把內建數學函數優化到接近硬件水平,當年那個魔數帶來的收益早被抹平了。
話雖如此,這個實現依然有它的價值——它生動說明了 TypedArray 讓 JavaScript 具備了操作二進制數據的能力,也讓我們對引擎的優化程度有了直觀的認識。以上就是用 JavaScript 實現平方根倒數算法的完整過程,代碼不到十行,有興趣的朋友可以自己動手跑一跑。