在Doom 3 BFG代码中，将计算Sqrt(x)的方法改为x * InvSqrt(x)是否有任何意义？

Question

我浏览了最近发布的Doom 3 BFG源代码，当我发现一些看起来毫无意义的东西时，它们与数学函数包装在idMath类中。其中一些函数只是转发到math.h中对应的函数，但有些是重新实现的（例如idMath::exp16()），我认为它们比它们的math.h对应函数具有更高的性能（也许以精度为代价）。

然而，令我困惑的是他们如何实现float idMath::Sqrt(float x)函数：

ID_INLINE float idMath::InvSqrt( float x ) {
     return ( x > FLT_SMALLEST_NON_DENORMAL ) ? sqrtf( 1.0f / x ) : INFINITY;
}

ID_INLINE float idMath::Sqrt( float x ) {
     return ( x >= 0.0f ) ? x * InvSqrt( x ) : 0.0f;
}

这似乎执行了两个不必要的浮点运算：首先是除法，然后是乘法。

有趣的是，原始Doom 3源代码也以这种方式实现了平方根函数，但倒数平方根使用了快速倒数平方根算法。

ID_INLINE float idMath::InvSqrt( float x ) {

    dword a = ((union _flint*)(&x))->i;
    union _flint seed;

    assert( initialized );

    double y = x * 0.5f;
    seed.i = (( ( (3*EXP_BIAS-1) - ( (a >> EXP_POS) & 0xFF) ) >> 1)<<EXP_POS) | iSqrt[(a >> (EXP_POS-LOOKUP_BITS)) & LOOKUP_MASK];
    double r = seed.f;
    r = r * ( 1.5f - r * r * y );
    r = r * ( 1.5f - r * r * y );
    return (float) r;
}


ID_INLINE float idMath::Sqrt( float x ) {
    return x * InvSqrt( x );
}

如果InvSqrt(x)内部只是调用math.h的fsqrt(1.f/x)，那么将Sqrt(x)计算为x * InvSqrt(x)是否有优势？我在这里可能忽略了关于非规格化浮点数的重要内容，或者这只是id软件的粗心大意？

- Robert Rüger

---

我想整个优势应该在于利用著名的快速反平方根实现。 - Roman R.

他们的方法对于非规范化数（因为非规范化数乘以正无穷得到正无穷，但实际上一个非规范化数的平方根是一个小值）给出了不同且不太准确的结果。也许他们在其他地方有依赖于此的代码，需要新的 "Sqrt" 与旧的兼容，但他们仍然可以通过特殊情况处理来解决这个问题。 - Steve Jessop

当快速的 invSqrt 成为过时技术后，没有人费心去更新普通平方根函数... - Mysticial

可能标准的 sqrtf 在处理非规格化浮点数时会比较慢？ - user1773602

@aleguna：也许是这样，但他们仍然可以在Sqrt()内部检查反规范化，并返回他们认为合适的内容。 - Robert Rüger

我很好奇两种情况下的x86汇编是什么。 - Nathan Ernst

Answer 1

我可以看到这样做的两个原因：首先，“快速invSqrt”方法（真正的牛顿-拉弗森方法）现在是许多硬件中使用的方法，所以这种方法留下了利用这种硬件的可能性（并且一次可以进行四个或更多的此类操作）。本文稍微讨论了一下这个问题：How slow (how many cycles) is calculating a square root? 第二个原因是为了兼容性。如果你改变计算平方根的代码路径，你可能会得到不同的结果（特别是对于零、NaN等），并失去依赖旧系统的代码的兼容性。

- Benny Smith

---

我不确定我理解你回答的第一部分。你是说今天的硬件可能在InvSqrt()内部执行快速反平方根算法，即使它没有明确地写出来吗？ InvSqrt()只是在内部调用math.h的sqrt()，所以我猜这至少需要使用C标准库实现的支持... - Robert Rüger

我想说的是，你可以编写一个InvSqrt的实现，利用支持它的平台上的硬件，在其他平台上只需使用默认的1.0/sqrt。它看起来应该像这样： #if defined(X86) // SSE2实现 #elif defined(PSP) // 使用他们的SIMD指令的解决方案 #else // 原始的默认实现 #endif对于格式问题，很抱歉，我无法在评论中放置代码。 - Benny Smith

啊，我明白了！从他们在 Github 上放的代码来看，似乎他们并没有这样做。 - Robert Rüger

Answer 2

据我所知，InvSqrt 用于计算颜色，因为颜色取决于光线从表面反射的角度，这将给出一些使用平方根的倒数的函数。

在这种情况下，当计算这些数字时，他们不需要很高的精度，因此 Doom 3 代码背后的工程师（最初来自 Quake III）想出了一种非常非常快速的方法来仅使用几个牛顿 - 拉弗森迭代来计算 InvSqrt 的近似值。

这就是为什么他们在所有代码中都使用 InvSqrt 而不是使用内置（更慢）函数。我猜使用 x * InvSqrt(x) 是为了避免通过具有两个非常有效的函数（一个用于 InvSqrt，另一个用于 Sqrt）将工作乘以两倍。

您应该阅读此文章，它可能会解决此问题。

- alestanis

---

是的！我同意这很可能是原版Doom 3和Quake 3代码计算平方根的原因。然而，仍然存在一个问题，即为什么新的BFG代码将Sqrt(x)计算为x * InvSqrt(x)，尽管InvSqrt()没有特别优化。 - Robert Rüger

Answer 3

当代码被多人修改时，要回答关于为什么它具有当前形式的问题变得困难，特别是没有修订历史记录的情况下。

然而，考虑到三分之一个世纪的编程经验，这段代码符合其他人提到的模式：一度，InvSqrt非常快，并且使用它来计算平方根是有意义的。然后，InvSqrt发生了改变，但没有人更新Sqrt。

- Eric Postpischil

---

我同意，但我认为对于BFG代码而言，稍微改动了Sqrt()函数有点奇怪。有人必须查看过它，这让我怀疑是否仍然存在某些魔法操作... - Robert Rüger

Answer 4

他们可能遇到了一个相对简单的sqrtf版本，对于更大的数字而言速度明显较慢。

- YvesgereY