鍍金池/ 教程/ HTML/ 平方根倒數(shù)快速算法
備忘錄模式
解釋器模式
類似 Python 的 zip 函數(shù)
類變量和實例變量
提示參數(shù)
指數(shù)對數(shù)運算
檢查變量的類型是否為數(shù)組
由數(shù)組創(chuàng)建一個字符串
生成隨機數(shù)
刪除數(shù)組中的相同元素
大寫單詞首字母
雙向服務(wù)器
類的混合
計算復(fù)活節(jié)的日期
轉(zhuǎn)換弧度和度
找到上一個月(或下一個月)
雙向客戶端
橋接模式
嵌入 JavaScript
AJAX
觀察者模式
克隆對象(深度復(fù)制)
一個隨機整數(shù)函數(shù)
清理字符串前后的空白符
歸納數(shù)組
平方根倒數(shù)快速算法
適配器模式
打亂數(shù)組中的元素
將數(shù)組連接
使用數(shù)組來交換變量
更快的 Fibonacci 算法
服務(wù)器
服務(wù)端和客戶端的代碼重用
客戶端
查找子字符串
策略模式
CoffeeScrip 的 type 函數(shù)
由數(shù)組創(chuàng)建一個對象詞典
回調(diào)綁定
工廠方法模式
映射數(shù)組
當(dāng)函數(shù)括號不可選
生成可預(yù)測的隨機數(shù)
不使用 jQuery 的 Ajax 請求
把字符串轉(zhuǎn)換為小寫形式
類方法和實例方法
擴展內(nèi)置對象
定義數(shù)組范圍
MongoDB
匹配字符串
創(chuàng)建一個不存在的對象字面值
列表推導(dǎo)
比較范圍
修飾模式
檢測每個元素
拆分字符串
字符串插值
對象數(shù)組
去抖動函數(shù)
使用 Nodeunit 測試
SQLite
單件模式
篩選數(shù)組
替換子字符串
數(shù)組最大值
計算(美國和加拿大的)感恩節(jié)日期
找到一個月中的最后一天
計算兩個日期中間的天數(shù)
基本的 HTTP 服務(wù)器
把字符串轉(zhuǎn)換為大寫形式
使用 HTML 命名實體替換 HTML 標(biāo)簽
For 循環(huán)
模板方法模式
重復(fù)字符串
使用 Jasmine 測試
對象的鏈?zhǔn)秸{(diào)用
數(shù)學(xué)常數(shù)
反轉(zhuǎn)數(shù)組
計算月球的相位
使用 Heregexes
查找子字符串
生成器模式
遞歸函數(shù)
HTTP 客戶端
創(chuàng)建 jQuery 插件
檢測與構(gòu)建丟失的函數(shù)
生成唯一ID
命令模式

平方根倒數(shù)快速算法

問題

你想快速計算某數(shù)的平方根倒數(shù)。

解決方案

在 Quake Ⅲ Arena 的源代碼中,這個奇怪的算法對一個幻數(shù)進行整數(shù)運算,來計算平方根倒數(shù)的浮點近似值。

在 CoffeeScript 中,他使用經(jīng)典原始的變量,以及由 Chris Lomont 發(fā)現(xiàn)的新的最優(yōu) 32 位幻數(shù)。除此之外,還使用 64 位大小的幻數(shù)。

另一特征是可以通過控制牛頓迭代法的迭代次數(shù)來改變其精確度。

相比于傳統(tǒng)的,該算法在性能上更勝一籌,這歸功于使用的機器及其精確度。

運行的時候使用 coffee -c script.coffee 來編譯 script:

然后復(fù)制粘貼編譯的 JS 代碼到瀏覽器的 JavaScript 控制臺。

注意:你需要一個支持類型數(shù)組的瀏覽器

參考:

  1. ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip
  2. http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
  3. http://en.wikipedia.org/wiki/Newton%27s_method
  4. https://developer.mozilla.org/en/JavaScripttypedarrays
  5. http://en.wikipedia.org/wiki/Fastinversesquare_root

以下的代碼來源于:https://gist.github.com/1036533

###

Author: Jason Giedymin <jasong _a_t_ apache -dot- org>
        http://www.jasongiedymin.com
        https://github.com/JasonGiedymin

在 Quake Ⅲ Arena 的源代碼 [1](ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip) 中,這個奇怪的算法對一個幻數(shù)進行整數(shù)運算,來計算平方根倒數(shù)的浮點近似值 [5](http://en.wikipedia.org/wiki/Fast_inverse_square_root)。

在 CoffeeScript 中,我使用經(jīng)典原始的變量,以及由 Chris Lomont [2](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 發(fā)現(xiàn)的新的最優(yōu) 32 位幻數(shù)。除此之外,還使用 64 位大小的幻數(shù)。

另一特征是可以通過控制牛頓迭代法 [3](http://en.wikipedia.org/wiki/Newton%27s_method) 的迭代次數(shù)來改變其精確度。

相比于傳統(tǒng)的,該算法在性能上更勝一籌,歸功于使用的機器及其精確度。

運行的時候使用 coffee -c script.coffee 來編譯 script: 

然后復(fù)制粘貼編譯的 JS 代碼到瀏覽器的 JavaScript 控制臺。

注意:你需要一個支持類型數(shù)組 [4](https://developer.mozilla.org/en/JavaScript_typed_arrays) 的瀏覽器

###

approx_const_quake_32 = 0x5f3759df # See [1]
approx_const_32 = 0x5f375a86 # See [2]
approx_const_64 = 0x5fe6eb50c7aa19f9 # See [2]

fastInvSqrt_typed = (n, precision=1) ->
    # 使用類型數(shù)組?,F(xiàn)在只能在瀏覽器中操作。
    # Node.JS 的版本即將推出。

    y = new Float32Array(1)
    i = new Int32Array(y.buffer)

    y[0] = n
    i[0] = 0x5f375a86 - (i[0] >> 1)

    for iter in [1...precision]
        y[0] = y[0] * (1.5 - ((n * 0.5) * y[0] * y[0]))

    return y[0]

### 單次運行示例

testSingle = () ->
    example_n = 10

    console.log("Fast InvSqrt of 10, precision 1: #{fastInvSqrt_typed(example_n)}")
    console.log("Fast InvSqrt of 10, precision 5: #{fastInvSqrt_typed(example_n, 5)}")
    console.log("Fast InvSqrt of 10, precision 10: #{fastInvSqrt_typed(example_n, 10)}")
    console.log("Fast InvSqrt of 10, precision 20: #{fastInvSqrt_typed(example_n, 20)}")
    console.log("Classic of 10: #{1.0 / Math.sqrt(example_n)}")

testSingle()