讨论:平方根倒数速算法

平方根倒数速算法因符合标准而获列入优良条目。如有需要，请勇于更新页面。如条目不再达标可提出重新评选。

平方根倒数速算法曾获提名典范条目评选，惟因其尚未符合标准而落选。下方条目里程碑的链接中可了解落选的详细原因及改善建议。列表照建议改善之后可再次提名评选。

条目里程碑
日期	事项	结果
2012年5月28日	优良条目评选	入选
2012年6月14日	典范条目评选	落选

本条目曾于2012年5月21日登上维基百科首页的“你知道吗？”字段。

新条目推荐的题目为：

当前状态：优良条目；其后评选典范条目落选

本条目页依照页面品质评定标准被评为优良级。
本条目页属于下列维基专题范畴：

电子游戏专题

（获评优良级，低重要度）

	电子游戏主题本条目页属于电子游戏专题范畴，该专题旨在改善中文维基百科电子游戏类内容。您若有意参与，欢迎浏览专题主页、参与讨论，并完成相应的开放性任务。
优良	根据专题质量评级标准，本条目页获评优良级。
低	根据专题重要度评级标准，本条目页已评为低重要度。

电脑和信息技术专题

（获评优良级、低重要度）

	信息技术主题查论编本条目页属于电脑和信息技术专题范畴，该专题旨在改善中文维基百科信息技术相关条目类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
优良	根据专题质量评级标准，本条目页已评为优良级。
低	根据专题重要度评级标准，本条目已评为低重要度。

数学专题

（获评优良级、低重要度）

	数学主题查论编本条目页属于数学专题范畴，该专题旨在改善中文维基百科数学类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
优良	根据专题质量评级标准，本条目页已评为优良级。
低	根据专题重要度评级标准，本条目已评为低重要度。

新条目推荐讨论

最新留言：11年前10条留言10人参与讨论

本主题或以下段落文字，移动自Wikipedia:新条目推荐/候选。

在候选页的投票结果

哪一种算法常被误认为与约翰·卡马克有关？
平方根倒数速算法条目由作者自荐，其作者为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)回复

优良条目候选编辑

最新留言：11年前21条留言11人参与讨论

平方根倒数速算法（编辑 | 讨论 | 历史 | 链接 | 监视 | 日志），分类：电脑信息-算法，提名人： 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)回复

关于那堆证明编辑

最新留言：11年前4条留言2人参与讨论

原来的那堆又是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)回复

校对过的存档

以右图中的数字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，而指数部分最低位也会随之成为新尾数部分的最高位。需要注意的是，由于有效数字的最高位并不在存储结构中而使其不会受到右移操作的影响，因此这第一步的整体效果近似于指数部分 $\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}}}$

由于解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikipedia.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\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 );这段代码正实现了上述指数部分运算。

添加话题

讨论:平方根倒数速算法

新条目推荐讨论

优良条目候选 编辑

关于那堆证明 编辑

优良条目候选编辑

关于那堆证明编辑