为什么平方根运算如此缓慢？

Question

我曾被许多程序员警告不要使用平方根函数，而是将数字提高到一半的幂。我的问题有两个：

1. 这样做的感知/实际性能优势是什么？为什么更快？

2. 如果它确实更快，为什么还要存在平方根函数？

- Athena

---

将数值提升至1/2并不会更快，它们都是exp(ln(x)/2)。 - Blindy

你的测试显示了什么？ - Adam Zuckerman

这句话的意思是“不要加上减1，而是加上一个负1”。 - hometoast

你的第一原则应该是编写清晰、可维护、有意义的代码。如果你没有性能问题，不要担心性能。如果你确实遇到了性能问题，那么第一步永远是对你的应用进行分析（profile）。当你完成分析并确定了热点时，你就可以开始担心如何修复它们。如果你已经达到了那个点，那么你替换 sqrt 为 pow 时会发现情况变得更糟。 - J...

J.的评论非常好，我希望能够给予认可。 - duffymo

只是部分相关，但有趣的阅读内容是关于常量0x5f3759df。 - Wai Ha Lee

Answer 1

我进行了一项简单测试：

  Stopwatch sw = new Stopwatch();

  sw.Start();

  Double s = 0.0;

  // compute 1e8 times either Sqrt(x) or its emulation as Pow(x, 0.5)
  for (Double d = 0; d < 1e8; d += 1)
    // s += Math.Sqrt(d);  // <- uncomment it to test Sqrt
    s += Math.Pow(d, 0.5); // <- uncomment it to test Pow

  sw.Stop();

  Console.Out.Write(sw.ElapsedMilliseconds);

在我的工作站(x64)上, (平均)结果为

  Sqrt:  950 ms 
  Pow:  5500 ms

正如你所看到的，更具体地说，Sqrt(x) 比其仿真版本 Pow(x, 0.5) 快5.5倍。因此这只是又一个传说（至少在C#中），即Sqrt速度非常慢，应该优先考虑使用Pow代替。

- Dmitry Bychenko

---

在测试（尤其是）数学函数时，通常值得说明目标平台或同时测试“x86”和“x64”。因为硬件实现经常非常不同，有时可能会出现令人惊讶的差异（虽然在这种情况下并不多）。从时间上看，我猜测这个例子是“x64”。对于“x86”，“Pow”只比“sqrt”快一点点（但仍然比“sqrt”慢得多）。 - J...

注意：慢速操作的1亿次需要5.5秒。快速操作的1亿次需要不到1秒钟。你的代码将是瓶颈，而不是这些函数调用。 - duffymo

那有点废话。瓶颈问题总是存在于某个“代码”中。但是，如果你在性能瓶颈处将sqrt替换为Pow，那么不这样做可能会获益。 - J...

当然，瓶颈在某人的代码中。我的观点是，重要的瓶颈更可能在OP的代码中，而不是这些函数中。分析器不太可能说平方根函数正在影响性能。 - duffymo

@duffymo 如果你需要每秒计算数百万个平方根怎么办？在我的情况下，Sqrt占用了超过10％的CPU时间，而我甚至还没有开始优化代码的其他部分，所以它只会增加... - Herman

Answer 2

要回答这个问题，你需要了解每个函数的实现方式。

平方根函数使用牛顿迭代法来迭代计算平方根。它的收敛速度是二次的。没有任何方法可以加快这个过程。

另外的函数 exp() 和 ln(x) 都有它们自己的复杂度和收敛性问题。例如，可以将它们实现成泰勒级数求和的形式。为了保证足够的精度，需要一定数量的项。

如果这些函数恰好是以本机代码实现的，那么就可能比你编写的任何东西都要快。

了解这些将使你做出明智的决定。不要因为那些程序员“知道”答案而轻信。

除非你进行大量的数值计算工作，否则我认为选择不会影响你的整体程序性能。微观优化最好避免，除非你进行大规模科学编程。

- duffymo

---

如果你正在进行严肃的科学编程，那么你算法的数值稳定性和避免灾难性抵消可能比速度同样重要（甚至更重要）。 - Dan Bryant

在此情况下，Sqrt已经在硬件中实现，分别针对x87 FPU（32位）和SSE/SSE2（64位），使用这些函数进行计算比Pow等软件实现要快得多。即使在具有f2xm1、fyl2x等实现的x87硬件上，单个调用f2xm1（它只会让您开始实现Pow）几乎与完整的fsqrt一样昂贵，而fyl2x的时间比fsqrt长三倍以上。除非是非常特殊的边缘情况和巧妙的算法，否则Pow没有办法更快。 - J...