跳转到内容

讨论:平方根倒数速算法

页面内容不支持其他语言。
维基百科，自由的百科全书
优良条目平方根倒数速算法因符合标准而获列入优良条目。如有需要，请勇于更新页面。如条目不再达标可提出重新评选。
典范条目落选平方根倒数速算法曾获提名典范条目评选，惟因其尚未符合标准而落选。下方条目里程碑的链接中可了解落选的详细原因及改善建议。列表照建议改善之后可再次提名评选。
条目里程碑
日期事项结果
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} ，为指数，易得：

    由于解析失败 (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} ，易见此部分引起的变化较为有限。使近似值快速趋向结果值的关键之一，是后一部分的运算，在此也即指数的运算。由于浮点数当中的指数部分保存的是而不是，因此不能直接用来直接求得，其中为结果在浮点数存储结构当中的指数部分（注意，不是真正的指数），而正确的计算方法应当是：

    ，因此
    解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikipedia.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\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”