討論:平方根倒數速算法

新條目推薦討論

在候選頁的投票結果

• 哪一種算法常被誤認為與約翰·卡馬克有關？

  平方根倒數速算法條目由作者自薦，其作者為Cravix（討論 | 貢獻），屬於「computer science」類型，提名於2012年5月15日 15:17 (UTC)。

  • (＊)提醒:由英文GA翻譯而得,很有趣的文章(可當都市傳說(?)看),準備試着沖GA,歡迎順便給些改進意見. - Dr. Cravix _{♬La Pluie} 2012年5月15日 (二) 15:14 (UTC)
  • (＋)支持有意思的條目，不過看的有點累--Wolfch (留言) 2012年5月15日 (二) 15:36 (UTC)
  • (＋)支持，可以申請GA。--CHEM.is.TRY 2012年5月16日 (三) 01:27 (UTC)
  • (＋)支持：有趣的條目。 AlexHe34（留言） 2012年5月16日 (三) 09:46 (UTC)
  • (＋)支持--Amazingloong ☏ 2012年5月16日 (三) 10:01 (UTC)
  • (＋)支持--yrr933! (留言)|化學、科技提升計劃! 2012年5月16日 (三) 12:03 (UTC)
  • (＋)支持--Alexchris（留言） 2012年5月17日 (四) 00:46 (UTC)
  • (＋)支持--B2322858（留言） 2012年5月17日 (四) 02:42 (UTC)
  • (＋)支持：摩卡·賀昇 2012年5月18日 (五) 08:28 (UTC)
  • (＋)支持--Iflwlou [ M {  2012年5月18日 (五) 13:50 (UTC)

優良條目候選

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

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

• (＋)支持：提名人票。個人翻譯自英文優良條目,dedicated to id Software.BTW,看了一下沒有"算法"這個分類,如果沒辦法就直接和enwiki一樣歸進數學類吧.-- Dr. Cravix _{♬La Pluie} 2012年5月21日 (一) 08:24 (UTC)
  • (～)補充：順便借問:根據FA的標準此條目若要入FA的話還需作何修改呢?(雖然最近也會比較忙而沒空馬上改,囧) - Dr. Cravix _{♬La Pluie} 2012年5月21日 (一) 23:51 (UTC)
• (＋)支持：深知編程算開方之麻煩沒效率，然而居然會有這種算法……條目素質甚佳，敘述很清楚易懂，讚一個。關於沒有算法分類我只想引用該條目代碼概述第十行之註釋--Hans Li（Li|Sn|ΔH） 2012年5月21日 (一) 08:57 (UTC)
• 雷神之錘xD--鐵鐵的火大了（留言） 2012年5月21日 (一) 10:35 (UTC)
• (＋)支持--有意思，參考很多足以支持全文。Merphisto（留言） 2012年5月22日 (二) 00:49 (UTC)
• 題外話，MathJax加載慢死了……--達師 － 218 － 372 2012年5月22日 (二) 06:44 (UTC)
  • Firefox下速度正常,會不會是瀏覽器問題? - Dr. Cravix _{♬La Pluie} 2012年5月23日 (三) 03:30 (UTC)
• (＋)支持，比較專業，也很詳細--Huandy618 (留言) 2012年5月22日 (二) 13:53 (UTC)
• (＋)支持--有意思，長見識了。Shypanda（留言） 2012年5月23日 (三) 02:27 (UTC)
• (！)意見：註釋部分參考文獻不足。那些灰色背景的公式為什麼要弄灰色背景？有一些多餘的粗體。「魔術數字」部分有個公式顯示錯誤--百無一用是書生 (☎) 2012年5月23日 (三) 02:30 (UTC)
  • (：)回應:嗯,謝謝建議與修正註釋的確沒寫清參考,於是加了;灰色背景是標明界限利於與正文相區分;多餘的粗體是指什麼呢?全文除表格外只有三處粗體呀(剛才順便修掉了一處);我這裏公式顯示正常,還是說我公式里寫錯什麼了呢?如果是的話還請幫我修改一下吧 - Dr. Cravix _{♬La Pluie} 2012年5月23日 (三) 03:30 (UTC)
• (＋)支持，翻譯通順。PS:為毛俺的Fx就不解析MathJax……--鐵鐵的火大了（留言） 2012年5月23日 (三) 06:35 (UTC)
  • 只能說我的Arch下Firefox,Opera,Midori甚至虛擬機XP下的IE都可以解析 囧rz……是版本問題嗎?還是如果可以的話請描述一下具體的問題吧,我試着檢查一下~ - Dr. Cravix _{♬La Pluie} 2012年5月23日 (三) 09:02 (UTC)
    • 呃，全是灰色的字，寫的全是線性排列的公式。Fx4和Fx12都不能解析，神奇……--鐵鐵的火大了（留言） 2012年5月23日 (三) 14:14 (UTC)
      • 這個...是所有公式都顯示成原始代碼嗎?也看看Help:數學公式,樣例都能正常顯示嗎?如果不行的話我的確搞不清楚是怎麼回事了= = - Dr. Cravix _{♬La Pluie} 2012年5月23日 (三) 23:48 (UTC)
        • 呃，我還是接着用圖片吧，公式能顯示出來就行了……--鐵鐵的火大了（留言） 2012年5月24日 (四) 04:48 (UTC)
          • (～)補充: 囧,說到圖片我才明白是怎麼回事,我都沒注意我本來設置的就是顯示為png= =剛才試了一下MathJax,也是可以的,但是流程是:頁面載入完後(一定要載入完不能中斷)先顯示為灰色的原式(應該就是你看到的),然後左下角顯示 載入MathJax(一個小框裏面顯示"Loading (MathJax各組件)"),載入完就能正常顯示了~要不你再試試吧 - Dr. Cravix _{♬La Pluie} 2012年5月24日 (四) 05:31 (UTC)

• (＋)支持，內容有趣--CHEM.is.TRY 2012年5月23日 (三) 10:46 (UTC)
• (＋)支持，連我都能看懂，說明這語句夠通俗了。-- 豆腐daveduv編寫上海留言 2012年5月24日 (四) 15:59 (UTC)
• (＋)支持：內容豐富詳細，參考資料足以支撐全文，段落大致上都有注腳，以支持票作獎勵。—ArikamaI 在沒有人有槍的國度裏，一把手槍的人就是國王（謝絕廢話|戰鬥記錄） 2012年5月25日 (五) 10:31 (UTC)

關於那堆證明

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

對於一次移位與減法操作以達到使浮點數的指數除-2的方法，Chris Lomont的論文中亦有有個相對簡單的解釋：以$\scriptstyle 10000=10^{4}$為例，將其指數除-2可得$\scriptstyle 10000^{-1/2}=10^{-2}=1/100$；而由於浮點表示的指數有進行過偏移處理，所以指數的真實值e應為$\scriptstyle e=E-127$，因此可知除法操作的實際結果為$\scriptstyle -e/2+127$，這時用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用科學計數法表示為$\scriptstyle 1.01\times 2^{-3}$（二進制），其首位數1不需要存儲在浮點數當中，於是剩下的「0100...」即成為右圖中紅色部分的內容。而指數-3，則需要加上127之後得到124（二進制01111100），成為右圖中的綠色部分。藍色部分為原本有理數的符號位，大於等於0用0表示，小於0用1表示。
2. 運算解釋

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

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

$Y=X^{-{\frac {1}{2}}}$

設

$X=X_{m}\times 2^{X_{e}}$，其中$X_{m}$為有效數字部分且滿足解析失败 (未知函数“\lt”): {\displaystyle 1 \le X_m \lt 2} ，$X_{e}=E-B$為指數，易得：

$Y=X^{-{\frac {1}{2}}}=(X_{m}\times 2^{X_{e}})^{-{\frac {1}{2}}}=X_{m}^{-{\frac {1}{2}}}\times 2^{-{\frac {X_{e}}{2}}}$

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

$E_{y}-B=-{\frac {X_{e}}{2}}=-{\frac {E_{x}-B}{2}}$，因此
解析失败 (未知函数“\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當中指數部分$\scriptstyle E$的值190正是由此求得。相對應的，算法中所使用的i = 0x5f3759df - ( i >> 1 );這段代碼正實現了上述指數部分運算。