算法与计算机科学betterexplained.com编辑精选
Quake 的快速平方根倒数
Quake's Fast Inverse Square Root
2009 — 2011，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇 BetterExplained 文章讲解 Quake 中著名的快速平方根倒数算法，介绍这个用位运算和 Newton 迭代近似计算 1/√x 的经典技巧。它适合作为理解该 hack 的入门读物，不过有评论指出文章没有深入解释魔数初始猜测部分。
为什么经久不衰：它把浮点位表示、Newton 迭代和游戏引擎优化史浓缩成一个著名案例，今天读来仍是理解底层优化的绝佳入口，也提醒人先测量再优化。
HN 评论精选
现代硬件和语言下该技巧未必更快，使用前应测量并保留回退方案。
知道这个技巧不错，但要注意现在它通常比直接使用你能拿到的内置平方根更慢。尤其在那些需要不止一次强制类型转换才能从浮点数中取出原始位的语言里，仅这一步就可能抵消任何潜在的性能收益。改动前后都要做性能分析，并确保能轻松回退，以防你发现反而更慢（或者更糟，精度不够用）。如果这是一个普遍有效且没有副作用的优化，它早就被内置到标准数学库里了……
bermanoid查看英文原文
This is a good thing to know about, but bear in mind that these days it's often slower than just using whatever built in square root you have access to. Especially beware in languages where you need to do something more than a cast to get the raw bits out of the floating point number, oftentimes that alone is enough to kill any performance gains you might otherwise see. Profile your code before and after, and make sure you've got an easy way to switch back if you realize that you've gone and made things slower (or worse, too inaccurate for your use case). If this was a universally effective optimization with no potential downside, it would already be built in to your standard math library...
补充了权威条目和相关论文，便于进一步阅读。
另见 Wikipedia 的 Fast inverse square root 条目；更多分析与改进参见 Lomont 等人的论文（InvSqrt.pdf、Fast_Inverse_Square_Root.pdf、FastInverseSqrt.pdf）。
achille查看英文原文
Also see: http://en.wikipedia.org/wiki/Fast_inverse_square_root And for more analysis and improvements see those papers: http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf
批评文章没解释魔数初始猜测，推荐 Lomont 论文但指出其非教学推导。
嗯。这个算法唯一真正有趣的部分是用魔数做初始猜测，而他完全没深入讲这部分。如果你真有兴趣理解，去读 Chris Lamont 的论文。Lomont 论文的唯一缺点是它是事后分析，而不是教学式推导。我去年一步步推导过这个算法，但一直没写成教程。
psykotic查看英文原文
Huh. The only really interesting part of the algorithm is the initial guess with the magic number, and he doesn't go into that part at all. Read Chris Lamont's paper if you care enough to want to understand it. The only downside to Lamont's paper is that it's a post mortem analysis rather than a pedagogical derivation. I worked out a step-by-step development of the algorithm last year, but I've never gotten around to writing it up in tutorial form.
牛顿法是理解该算法的关键。
如果你知道用牛顿法求多项式根是怎么回事，这就很容易理解。
nx查看英文原文
It's really easy to understand if you know what the Newton Method for computing roots of a polynomial is.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选