c++ - 快速获取单位长度 vector 的长度 "improve"的方法

Question

当已知 vector 已经几乎是单位长度时，在性能关键代码中支付完整的 vector 规范化似乎是浪费。

有谁知道使 double 3D vector 的长度更接近 1 的快速实用方法？我在想象一种基于 Newton-Raphson 迭代或 1 左右的有限泰勒展开的迭代方法。

Here是这样一个例程可能有用的真实世界情况。 incoming vector 已经接近单位长度，但如果没有明确的规范化，它仍然会触发断言。

可以使用 SSE 2、SSE 4.2 或 AVX 内在函数。

Answer 1

手头的问题归结为找到(近似值)reciprocal square root .

SSE 和 AVX 包括近似倒数平方根机器指令，rsqrt , 这特别适合这个。根据原文 AMD64 Architecture Programmer's Manual, volume 1 ，平方根倒数变体的最大相对误差最大为1.5×2^-12，即小于0.0004。

如果你使用 GCC，你可以使用 __builtin_ia32_rsqrtss() SSE 内置函数计算 vector 长度平方的平方根倒数，并将 vector 分量乘以结果，得到一个“几乎单位”的 vector 。

请注意，SSE 和 AVX 都提供了加速平方长度计算以及乘以每个分量的函数。 (不过，您需要将比例因子复制到大小相等的 vector 。)

---

如果没有 SSE/AVX，一般的问题是我们希望将 vector 分量乘以 f(S) ≃ sqrt(1/S) == 1/sqrt(S)，其中S是 vector 与自身的内积(点积)，即其长度的平方；但是 sqrt() 被认为太慢了，并且已知 S 已经接近 1。

任何函数 f(S) 其值介于 1 和 sqrt(1/S) 之间，在我们认为“接近 1”的范围内，都将起作用。我能想到的最简单的函数是 f(S) = (C + 1 - S)/C 。对于 S = 0.5² 到 2²(即对于长度在 1/2 和 2 之间的 vector )，C 是 6。

如果我们没有任何对平方根倒数的硬件支持，我将尝试的第一个近似值将遵循以下几行:

1. 计算 vector 的平方长度S

2. 计算 M = 0.125 * (9 - S)

   注意任何常量对 C₁ 和 C₂ = 1 + 1/C ₁ 应该有效，只是范围和收敛速度不同。我为这个例子选择了 C₁ = 1/8 只是因为它在 IEEE-754 浮点表示中是精确的，而且通常乘法比除法快得多。其他值(如我上面提到的范围为 0.5 到 2 的 1/6)不精确，可能需要手动调整(以一种或另一种方式调整两个常量中的最低有效单位)。

3. 将 vector 的每个分量乘以M。

如果这没有产生足够好的结果，我就不再担心它，而是使用(硬件)平方根。 (在某些架构上，将平方长度转换为单精度以计算比例因子可以产生显着的加速。但在 x86/AMD64 上则不然。)