快速平方根倒数——Quake III 算法
Fast Inverse Square Root — A Quake III Algorithm
频道:Nemean · 时长:20:08 · 发布:2020-11-28 · 播放:6031570
简介
详细讲解 Quake III 的快速平方根倒数,解释常数 0x5f3759df 的来源。涵盖 IEEE 754 浮点数、近似对数的位操作技巧,以及牛顿法优化。
HN 为什么推荐
HN 推荐它作为通俗易懂的解释,让这个著名算法终于变得清晰。
这个视频通俗易懂,解释得相当好 — HN, 2021
中文字幕节选
2005年,一家游戏公司将其电子游戏Quake的引擎开源 3 Arena。在这份源代码中,游戏的粉丝们发现了一个算法,它如此 巧妙,很快便声名远扬。而这个算法唯一做的事就是 计算平方根的倒数。如果我必须写一段代码来 计算平方根的倒数,我会这样做。这里我使用的是 C编程语言,也就是Quake 3所用的同一种编程语言。 但说实话,我其实不会自己把平方根写进去。那些 更熟悉C语言的人,或者说设计者,已经弄清楚了如何 计算平方根,并在math.h文件中为我们提供了算法, 我们程序员只需把它包含进自己的程序即可。那么,Quake 3的算法 究竟有什么如此有趣之处?它的软件是如何计算平方根 的倒数的? 乍一看,它似乎毫无道理。这个数字0x5f3759df 从何而来?它与求平方根有什么关系?为什么 第二条注释里有一个不堪入目的脏话?在本视频中,我将向你展示如何 通过一些巧妙的位操作来计算平方根的倒数,而实现这一点的算法 名为快速平方根倒数。首先, 游戏引擎为什么要计算1除以x的平方根?如果 你想在游戏引擎中实现物理、光照或反射, 那么你用来计算的向量最好归一化为长度为1,因为 否则你的向量可能太短或太长,当你用它们做物理运算时 就会出问题。 众所周知,向量的长度是x平方加y平方 加z平方的平方根。如果你没注意到,我敢说你见过它在 二维中的样子,那就是勾股定理。所以如果我们想把向量的 长度归一化为1,就必须把所有分量都按向量长度缩小。我的意思是, 显然如此,因为如果我们用向量长度除以向量长度, 显然得到1。所以剩下要做的就是将x、y和z除以长度,或者 类似地乘以1除以长度。你可能已经看出 接下来要做什么了。计算x平方加y平方加z平方很容易, 更重要的是在代码中非常快。你会把它实现为x乘x加y 乘y加z乘z,它不过是三个乘法相加。 加法和乘法是常见操作,被设计得 非常快。而平方根则是一个极其缓慢的操作,除法 也好不到哪去。如果我们有几千个表面, 每个都有一个需要归一化的向量,这就不妙了。但这也意味着,这里 有一个提速的机会。如果我们能找到哪怕只是一个 1除以x的平方根的近似值,只要它够快,就能节省宝贵的时间。 快速平方根倒数就是这样一个近似值,误差最多只有 百分之一,速度却快了三倍。再看一遍代码, 我们可以看到开头相当无害。我们得到一个名为number的 数作为输入,也就是我们要对其求平方根倒数的数。首先用 变量i声明一个32位整数,然后声明两个32位小数 x2和y,接着把1.5存入那个名字显而易见的变量three halves。接下来两行只是把输入的一半复制到x2,把整个输入 复制到y。但正是在这之后,魔法发生了。花点时间再看 一眼。好吧,你看得越久,它就越没道理,而 右边的注释也帮不上什么忙。但它们确实暗示了 这个算法有三个步骤。把这三点拼在一起,就会向我们展示 这个算法的精妙之处。但在开始这三个步骤之前,让我们先
HN 上的讨论
非常有趣,这个帖子发布时,我上周末刚刚看了一个关于这段代码的更有趣的YouTube上传。如果有人想看看,这里是那个非常有趣的视频:[VIDEO] — greyfox, 2021-07
显然,将浮点数的位模式解释为整数,它差不多就是自己的对数,这就是为什么Quake 3中著名的快速平方根倒数算法有效:log(x^-½) = -½log(x) =~ -log(x) >> 1。这个视频通俗易懂,解释得相当好:[VIDEO] — infogulch, 2021-09
> 浮点数的位模式作为整数字面量与其log2值(加上一个常数)成正比,…… 我之前看过一个视频[0]讲这个。一旦解释了这个巧合(?),Q_rsqrt终于说得通了。[0]:[VIDEO](约20分钟) — colejohnson66, 2021-08
print("Hello World") /s 但我听说过Doom 3源代码中的快速平方根倒数计算算法很不错。[VIDEO] — bitwidget, 2022-08
相关视频
- 如何在太空中实现纳米级精度? · Breaking Taps · 11:06
- 两把(?)无法撬开的锁,送给 Lock Picking Lawyer! · Stuff Made Here · 14:39
- 这就是为什么我们不能拥有好东西 · Veritasium · 17:30
- 数学的未来? · Microsoft Research · 1:14:48
- [1299] 来自 Stuff Made Here 的无法撬开的锁 · LockPickingLawyer · 10:35
- 为什么不能相乘向量? · Freya Holmér · 51:15
- 傅里叶光学用于光学模式识别 · Huygens Optics · 18:30
- Refterm讲座第一部分 - 优化哲学 · Molly Rocket · 18:41
- 自动微分的简单本质 - Conal Elliott · Microsoft Research · 1:30:45
- 打造我的梦想电脑 - 第 1 部分 · The 8-Bit Guy · 20:37
- D/A 与 A/D | 数字展示与讲解(Monty Montgomery @ xiph.org) · FL Studio · 23:52
- 等待音乐曾经听起来更好。原因如下。 · Tom Scott · 3:36
- 8位与“8位风格”图形——跳出框框 · GDC Festival of Gaming · 1:25:34
- Python如何被泄漏的内部机制塑造,Armin Ronacher,Flask框架 · Видео с мероприятий {speach! · 49:55
- CppCon 2015:Andrei Alexandrescu “std::allocator...” · CppCon · 1:12:27
- 反向模拟 NES,赋予它超级能力! · suckerpinch · 22:21