跳至內容

討論:平方根倒數速算法

頁面內容不支援其他語言。
維基百科，自由的百科全書
優良條目平方根倒數速算法因符合標準而獲列入優良條目。如有需要，請勇於更新頁面。如條目不再達標可提出重新評選。
典範條目落選平方根倒數速算法曾獲提名典範條目評選，惟因其尚未符合標準而落選。下方條目里程碑的連結中可了解落選的詳細原因及改善建議。列表照建議改善之後可再次提名評選。
條目里程碑
日期事項結果
2012年5月28日優良條目評選入選
2012年6月14日典範條目評選落選
新條目推薦
本條目曾於2012年5月21日登上維基百科首頁的「你知道嗎？」欄位。
新條目推薦的題目為：
    當前狀態：優良條目；其後評選典範條目落選
              本條目頁依照頁面評級標準評為優良級。
    本條目頁屬於下列維基專題範疇：
    		電子遊戲專題 （獲評優良級，低重要度）
    本條目頁屬於電子遊戲專題範疇，該專題旨在改善中文維基百科電子遊戲類內容。您若有意參與，歡迎瀏覽專題主頁、參與討論，並完成相應的開放性任務。
     優良級優良  根據專題品質評級標準，本條目頁獲評優良級。
     低  根據專題重要度評級標準，本條目頁已評為低重要度。
    		電腦和資訊科技專題 （獲評優良級、低重要度）
    本條目頁屬於電腦和資訊科技專題範疇，該專題旨在改善中文維基百科資訊科技相關條目類內容。如果您有意參與，請瀏覽專題主頁、參與討論，並完成相應的開放性任務。
     優良級優良  根據專題品質評級標準，本條目頁已評為優良級。
     低  根據專題重要度評級標準，本條目已評為低重要度。
    		數學專題 （獲評優良級、低重要度）
    本條目頁屬於數學專題範疇，該專題旨在改善中文維基百科數學類內容。如果您有意參與，請瀏覽專題主頁、參與討論，並完成相應的開放性任務。
     優良級優良  根據專題品質評級標準，本條目頁已評為優良級。
     低  根據專題重要度評級標準，本條目已評為低重要度。

    新條目推薦討論

    本主題或以下段落文字，移動自Wikipedia:新條目推薦/候選。

    在候選頁的投票結果

    優良條目候選

    [編輯]

    平方根倒數速算法（編輯 | 討論 | 歷史 | 連結 | 監視 | 日誌），分類：電腦信息-算法，提名人： Dr. Cravix ♬La Pluie 2012年5月21日 (一) 08:24 (UTC)[回覆]

    投票期：2012年5月21日 (一) 08:24 (UTC) 至 2012年5月28日 (一) 08:24 (UTC)

    關於那堆證明

    [編輯]

    原來的那堆又是rho又是M的證明，相當複雜，並且難以理解。還不如我給添加上去的那段解釋，實際上等於後面

    對於一次移位與減法操作以達到使浮點數的指數除-2的方法，Chris Lomont的論文中亦有有個相對簡單的解釋：以為例，將其指數除-2可得；而由於浮點表示的指數有進行過偏移處理，所以指數的真實值e應為，因此可知除法操作的實際結果為，這時用R（在此即為「魔術數字」0x5f3759df）減之即可使指數的最低有效數位轉入有效數字域，之後重新轉換為浮點數時，就能得到一個相當接近所輸入的浮點數的平方根倒數的近似值。在這裏對常數R的選取亦有所講究，選取一個好的R值可以減少對指數進行除法與對有效數字域進行移位時可能產生的錯誤。基於這一標準，0xbe即是最合適的R值，而0xbe右移一位即可得到0x5f，這恰是魔術數字R的第一個字節。

    的詳細解釋，並較其嚴謹和易懂。其實關於尾數部分的選擇，我記得當年也看到過一篇文章詳細介紹其思路的，這裏沒有這部分的記錄，較為可惜。當年我還仔細推敲過，這個尾數的選擇算是非常巧妙。可惜我已經不記得了（包括來源），無法貢獻了。如果有朋友記得，還請修改一下。—— Sumtec（讚美 罵街 討論 察看貢獻） 2012年6月8日 (五) 09:14 (UTC)[回覆]

    我覺得指數如何被-2除是很容易理解的事情(參看上面GAN存檔的理由),浮點數部分也沒必要舉例(前面的說明已經很清楚了,再詳細有點越俎代庖代替浮點條目之嫌...個人感覺吧),但這且按下不提,你這樣直接插一段讓我非常難辦,因為內容明顯是重複的,條理也被打亂了,現在一時間沒有整理的頭緒.這個條目畢竟已經是GA了,擴充內容固然好,但修改前還是想想怎麼才能比較保持條理吧...現在只作了校對,剩下的後面再說. - Dr. Cravix ♬La Pluie 2012年6月8日 (五) 14:29 (UTC)[回覆]
    (～)補充:抱歉,但我不能不說你簡直是亂搞,"魔術數字"那一部分的主題明顯就不是尾數,編輯前請先仔細看一遍好嗎?逗號也不能濫用,這麼混亂再改下去連B級條目都算不上吧.抱歉我必須撤掉你加入的內容並存檔於此,以後想清楚怎麼整理好再加入吧. - Dr. Cravix ♬La Pluie 2012年6月8日 (五) 14:38 (UTC)[回覆]
    於是存檔如下,mathjax里亂糟糟的"<"與">"號也已校正.順便對某IP用戶說一句:{{-}}本質上是br clear=all,可能會造成潛在的隱患(最直接的就是隱藏頁面bug),請不要再度濫用這一模板,好心也會辦壞事的. - Dr. Cravix ♬La Pluie 2012年6月8日 (五) 15:07 (UTC)[回覆]
    校對過的存檔
    1. 以右圖中的數字0.15625為例，其二進制表示法為0.00101000...（即，0.15625=0.125+0.03125=1/8+1/32）。根據浮點數的存儲規則，「0.00101...」需要表示成1.01*10-3。其中有效數字0.00101用科學計數法表示為（二進制），其首位數1不需要存儲在浮點數當中，於是剩下的「0100...」即成為右圖中紅色部分的內容。而指數-3，則需要加上127之後得到124（二進制01111100），成為右圖中的綠色部分。藍色部分為原本有理數的符號位，大於等於0用0表示，小於0用1表示。
    2. 運算解釋

    這一公式的第一步是進行了整數的右位移操作（高位向低位位移），其實際效果即是將指數部分（右上圖綠色部分）除以2。同時，尾數部分也因為右位移操作而除以2，而指數部分最低位也會隨之成為新尾數部分的最高位。需要注意的是，由於有效數字的最高位並不在存儲結構中而使其不會受到右移操作的影響，因此這第一步的整體效果近似於指數部分除以2（注意，不是實際的指數）。此運算步驟所做的操作很容易理解，但是實際上至此仍難以理解其真正用意。

    上述代碼中魔術數字0x5f3759df的二進制展開形式為0 10111110 01101110101100111011111，即相當於，這一個數值是整個算法當中最難以理解的部分。其中指數部分（二進制）（十進制），是整個運算的過程的關鍵。為了便於理解，在此回顧原始計算公式：

    設

    ，其中為有效數字部分且滿足解析失败 (未知函数“\lt”): {\displaystyle 1 \le X_m \lt 2} ，為指數，易得：

    由於解析失败 (未知函数“\lt”): {\displaystyle \scriptstyle1 \le X_m \lt 2} ，因此解析失败 (未知函数“\lt”): {\displaystyle \scriptstyle 0.707106 \lt X_m^{-\tfrac{1}{2}} \le 1} ，易見此部分引起的變化較為有限。使近似值快速趨向結果值的關鍵之一，是後一部分的運算，在此也即指數的運算。由於浮點數當中的指數部分保存的是而不是，因此不能直接用來直接求得，其中為結果在浮點數存儲結構當中的指數部分（注意，不是真正的指數），而正確的計算方法應當是：

    ，因此
    解析失败 (未知函数“\gt”): {\displaystyle E_y = B - \frac{E_x - B}{2} = B - \frac{E_x}{2} + \frac{B}{2} = 127 + 63 - (E_x \gt\gt 1) = 190 - (E_x \gt\gt 1) }

    魔術數字0x5f3759df當中指數部分的值190正是由此求得。相對應的，算法中所使用的i = 0x5f3759df - ( i >> 1 );這段代碼正實現了上述指數部分運算。

    取自 "https://zh.wikipedia.org/w/index.php?title=Talk:平方根倒数速算法&oldid=61007747"