什么更有效? 用幂平方还是用它自己乘？

这两种方法在 C 语言中哪一种更有效:

pow(x,3)

对。

x*x*x // etc?
133411 次浏览
小开

x*x或 x*x*x将比 pow快，因为 pow必须处理一般情况，而 x*x是特定的。此外，还可以省略函数调用之类的内容。

然而，如果您发现自己像这样进行微优化，那么您需要一个分析器并进行一些严肃的分析。极有可能的是，你永远不会注意到这两者之间的任何差异。

小开

你问错问题了。正确的问题应该是: “对于我的代码的人类读者来说，哪一个更容易理解?”

如果速度很重要(稍后) ，不要问，而是量度。(在此之前，测量一下这种优化是否真的会产生任何明显的效果。)在此之前，编写代码以便于阅读。

剪辑
只是为了明确这一点(虽然它已经应该是) : 突破加速通常来自于像 使用更好的算法，改善数据的位置，减少使用动态记忆，< 环境监察及审核 > 预先计算结果等东西。它们在 非常少的地方中完成，这只能在 小心中找到(而且很耗时) ，通常它们可以通过做一些非常不直观的事情(比如插入 noop语句)来加快速度，对一个平台的优化有时是对另一个平台的悲观(这就是为什么你需要测量，而不是询问，因为我们不完全了解/拥有你的环境)。

让我再次强调一下: 即使在少数几个重要的应用程序中，在大多数使用它们的地方它们也不重要，而且 通过查看代码，您不太可能找到它们重要的位置。你确实需要 首先确定热点，因为否则优化代码就只是 浪费时间。

即使一个操作(比如计算某个值的平方)占用了 应用程序执行时间的10% (IME 非常罕见) ，即使优化它节省了该操作所必需的 50% 的时间(IME 更是非常非常罕见) ，您仍然让应用程序占用了 只减少了5% 的时间。
您的用户甚至需要一个秒表来注意到这一点。(我想在大多数情况下，任何低于20% 的加速都不会引起大多数用户的注意。而 那个就是你需要找到的四个这样的点。)

小开

如果指数是常数且很小，则将其展开，使乘法次数最小。(例如，x^4不是最优的 x*x*x*x，而是 y*y，其中 y=x*x。而 x^5是 y*y*x其中 y=x*x。等等。)对于常数整数指数，只需写出优化的表单; 对于小指数，这是一个标准的优化，无论代码是否已经分析，都应该执行这个优化。在大多数情况下，优化后的表单会更快，因此基本上总是值得去做的。

(如果使用 Visual C + + ，std::pow(float,int)将执行我提到的优化，即操作序列与指数的位模式相关。不过，我不能保证编译器会为您展开循环，所以手工操作还是值得的。)

[编辑]顺便说一句，pow有一个(不)令人惊讶的倾向，突然出现在分析器的结果。如果你不是绝对需要它(例如，指数很大或者不是一个常数) ，并且你非常关心性能，那么最好写出最佳代码，然后等待分析器告诉你它(令人惊讶地)在进一步思考之前浪费时间。(另一种方法是调用 pow，让分析器告诉你这是在浪费时间(这并不令人惊讶)——聪明地完成这一步，你就省去了这一步。)

小开
最佳答案

更新日期2021

我将基准代码修改如下:

  • 用于定时测量的计时器而不是助推器
  • 使用 C + + 11 <random>代替 rand()
  • 避免重复可能被吊起的操作。基本参数是不断变化的。

使用 GCC 10-O2我得到以下结果(以秒为单位) :

exp     c++ pow     c pow       x*x*x...
2       0.204243    1.39962     0.0902527
3       1.36162     1.38291     0.107679
4       1.37717     1.38197     0.106103
5       1.3815      1.39139     0.117097

海湾合作委员会10-O3几乎与海湾合作委员会10-O2完全相同。

海湾合作委员会10-0-2-快速计算:

exp     c++ pow     c pow       x*x*x...
2       0.203625    1.4056      0.0913414
3       0.11094     1.39938     0.108027
4       0.201593    1.38618     0.101585
5       0.102141    1.38212     0.10662

海湾合作委员会10-03-快速计算:

exp     c++ pow     c pow       x*x*x...
2       0.0451995   1.175       0.0450497
3       0.0470842   1.20226     0.051399
4       0.0475239   1.18033     0.0473844
5       0.0522424   1.16817     0.0522291

用12-O2克朗:

exp     c++ pow     c pow       x*x*x...
2       0.106242    0.105435    0.105533
3       1.45909     1.4425      0.102235
4       1.45629     1.44262     0.108861
5       1.45837     1.44483     0.1116

克朗12-O3几乎与克朗12-O2完全相同。

用克朗12-O2-快速算法:

exp     c++ pow     c pow       x*x*x...
2       0.0233731   0.0232457   0.0231076
3       0.0271074   0.0266663   0.0278415
4       0.026897    0.0270698   0.0268115
5       0.0312481   0.0296402   0.029811

Clang 12-O3-快速数学和 Clang 12-O2-快速数学几乎是一样的。

计算机是 Linux 5.4.0-73-general x86 _ 64上的 Intel Core i7-7700K。

结论:

  • 有了 GCC10(不快速数学) ，x*x*x...比 一直都是快
  • 使用 GCC 10-O2-fast-數学，std::pow对于 奇怪指数来说和 x*x*x...一样快
  • 使用 GCC 10-O3快速算法，对于所有测试用例，std::pow的速度都与 x*x*x...一样快，并且大约是 -O2的两倍。
  • 对于 GCC 10，C 的 pow(double, double)总是慢得多
  • 使用 Clang 12(no-fast-數学) ，对于大于2的指数，x*x*x...更快
  • 使用 Clang 12-fast-data，所有方法都会产生相似的结果
  • 对于整数指数，pow(double, double)和 std::pow一样快
  • 编写基准测试而编译器又不比你聪明，这就是 用力。

我最终将抽出时间在我的机器上安装更新版本的 GCC，并在这样做时更新我的结果。

下面是更新后的基准代码:

#include <cmath>
#include <chrono>
#include <iostream>
#include <random>


using Moment = std::chrono::high_resolution_clock::time_point;
using FloatSecs = std::chrono::duration<double>;


inline Moment now()
{
return std::chrono::high_resolution_clock::now();
}


#define TEST(num, expression) \
double test##num(double b, long loops) \
{ \
double x = 0.0; \
\
auto startTime = now(); \
for (long i=0; i<loops; ++i) \
{ \
x += expression; \
b += 1.0; \
} \
auto elapsed = now() - startTime; \
auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
std::cout << seconds.count() << "\t"; \
return x; \
}


TEST(2, b*b)
TEST(3, b*b*b)
TEST(4, b*b*b*b)
TEST(5, b*b*b*b*b)


template <int exponent>
double testCppPow(double base, long loops)
{
double x = 0.0;


auto startTime = now();
for (long i=0; i<loops; ++i)
{
x += std::pow(base, exponent);
base += 1.0;
}
auto elapsed = now() - startTime;


auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
std::cout << seconds.count() << "\t"; \


return x;
}


double testCPow(double base, double exponent, long loops)
{
double x = 0.0;


auto startTime = now();
for (long i=0; i<loops; ++i)
{
x += ::pow(base, exponent);
base += 1.0;
}
auto elapsed = now() - startTime;


auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
std::cout << seconds.count() << "\t"; \


return x;
}


int main()
{
using std::cout;
long loops = 100000000l;
double x = 0;
std::random_device rd;
std::default_random_engine re(rd());
std::uniform_real_distribution<double> dist(1.1, 1.2);
cout << "exp\tc++ pow\tc pow\tx*x*x...";


cout << "\n2\t";
double b = dist(re);
x += testCppPow<2>(b, loops);
x += testCPow(b, 2.0, loops);
x += test2(b, loops);


cout << "\n3\t";
b = dist(re);
x += testCppPow<3>(b, loops);
x += testCPow(b, 3.0, loops);
x += test3(b, loops);


cout << "\n4\t";
b = dist(re);
x += testCppPow<4>(b, loops);
x += testCPow(b, 4.0, loops);
x += test4(b, loops);


cout << "\n5\t";
b = dist(re);
x += testCppPow<5>(b, loops);
x += testCPow(b, 5.0, loops);
x += test5(b, loops);


std::cout << "\n" << x << "\n";
}

老答案，2010年

我使用以下代码测试了小型 i的 x*x*...和 pow(x,i)之间的性能差异:

#include <cstdlib>
#include <cmath>
#include <boost/date_time/posix_time/posix_time.hpp>


inline boost::posix_time::ptime now()
{
return boost::posix_time::microsec_clock::local_time();
}


#define TEST(num, expression) \
double test##num(double b, long loops) \
{ \
double x = 0.0; \
\
boost::posix_time::ptime startTime = now(); \
for (long i=0; i<loops; ++i) \
{ \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
} \
boost::posix_time::time_duration elapsed = now() - startTime; \
\
std::cout << elapsed << " "; \
\
return x; \
}


TEST(1, b)
TEST(2, b*b)
TEST(3, b*b*b)
TEST(4, b*b*b*b)
TEST(5, b*b*b*b*b)


template <int exponent>
double testpow(double base, long loops)
{
double x = 0.0;


boost::posix_time::ptime startTime = now();
for (long i=0; i<loops; ++i)
{
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
}
boost::posix_time::time_duration elapsed = now() - startTime;


std::cout << elapsed << " ";


return x;
}


int main()
{
using std::cout;
long loops = 100000000l;
double x = 0.0;
cout << "1 ";
x += testpow<1>(rand(), loops);
x += test1(rand(), loops);


cout << "\n2 ";
x += testpow<2>(rand(), loops);
x += test2(rand(), loops);


cout << "\n3 ";
x += testpow<3>(rand(), loops);
x += test3(rand(), loops);


cout << "\n4 ";
x += testpow<4>(rand(), loops);
x += test4(rand(), loops);


cout << "\n5 ";
x += testpow<5>(rand(), loops);
x += test5(rand(), loops);
cout << "\n" << x << "\n";
}

结果如下:

1 00:00:01.126008 00:00:01.128338
2 00:00:01.125832 00:00:01.127227
3 00:00:01.125563 00:00:01.126590
4 00:00:01.126289 00:00:01.126086
5 00:00:01.126570 00:00:01.125930
2.45829e+54

注意，我积累了每次幂计算的结果，以确保编译器不会优化它。

如果我使用 std::pow(double, double)版本和 loops = 1000000l，我得到:

1 00:00:00.011339 00:00:00.011262
2 00:00:00.011259 00:00:00.011254
3 00:00:00.975658 00:00:00.011254
4 00:00:00.976427 00:00:00.011254
5 00:00:00.973029 00:00:00.011254
2.45829e+52

这是在运行 Ubuntu 9.1064位的 Intel Core Duo 上，使用 gcc 4.4.1 with-o2优化编译。

所以在 C 中，是的 x*x*x会比 pow(x, 3)快，因为没有 pow(double, int)过载。在 C + + 中，它大致相同。(假设我的测试方法是正确的。)

这是对安马尔科姆的评论的回应:

即使发出了 using namespace std指令，如果 pow的第二个参数是 int，那么将调用来自 <cmath>的 std::pow(double, int)重载，而不是来自 <math.h>的 ::pow(double, double)。

这个测试代码确认了这个行为:

#include <iostream>


namespace foo
{


double bar(double x, int i)
{
std::cout << "foo::bar\n";
return x*i;
}




}


double bar(double x, double y)
{
std::cout << "::bar\n";
return x*y;
}


using namespace foo;


int main()
{
double a = bar(1.2, 3); // Prints "foo::bar"
std::cout << a << "\n";
return 0;
}
小开

我还想知道性能问题，并希望编译器能够根据@EmileCormier 的答案优化这个问题。然而，我担心他展示的测试代码仍然允许编译器优化掉 std: : pow ()调用，因为每次调用都使用相同的值，这将允许编译器存储结果并在循环中重用它——这将解释所有情况下几乎相同的运行时间。所以我也查了一下。

下面是我使用的代码(test _ power. cpp) :

#include <iostream>
#include <cmath>
#include <chrono>


class Timer {
public:
explicit Timer () : from (std::chrono::high_resolution_clock::now()) { }


void start () {
from = std::chrono::high_resolution_clock::now();
}


double elapsed() const {
return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - from).count() * 1.0e-6;
}


private:
std::chrono::high_resolution_clock::time_point from;
};


int main (int argc, char* argv[])
{
double total;
Timer timer;






total = 0.0;
timer.start();
for (double i = 0.0; i < 1.0; i += 1e-8)
total += std::pow (i,2);
std::cout << "std::pow(i,2): " << timer.elapsed() << "s (result = " << total << ")\n";


total = 0.0;
timer.start();
for (double i = 0.0; i < 1.0; i += 1e-8)
total += i*i;
std::cout << "i*i: " << timer.elapsed() << "s (result = " << total << ")\n";


std::cout << "\n";


total = 0.0;
timer.start();
for (double i = 0.0; i < 1.0; i += 1e-8)
total += std::pow (i,3);
std::cout << "std::pow(i,3): " << timer.elapsed() << "s (result = " << total << ")\n";


total = 0.0;
timer.start();
for (double i = 0.0; i < 1.0; i += 1e-8)
total += i*i*i;
std::cout << "i*i*i: " << timer.elapsed() << "s (result = " << total << ")\n";




return 0;
}

这是用以下方法编制的:

g++ -std=c++11 [-O2] test_pow.cpp -o test_pow

基本上，区别在于 std: : pow ()的参数是循环计数器。正如我所担心的，表现上的差异是显而易见的。如果没有 -O2标志，我的系统(Arch Linux 64位，g + + 4.9.1，Intel i7-4930)上的结果是:

std::pow(i,2): 0.001105s (result = 3.33333e+07)
i*i: 0.000352s (result = 3.33333e+07)


std::pow(i,3): 0.006034s (result = 2.5e+07)
i*i*i: 0.000328s (result = 2.5e+07)

通过优化，结果同样惊人:

std::pow(i,2): 0.000155s (result = 3.33333e+07)
i*i: 0.000106s (result = 3.33333e+07)


std::pow(i,3): 0.006066s (result = 2.5e+07)
i*i*i: 9.7e-05s (result = 2.5e+07)

因此，看起来编译器至少尝试优化 std: : pow (x，2)大小写，但不优化 std: : pow (x，3)大小写(它比 std: : pow (x，2)大小写长约40倍)。在所有情况下，手动扩展表现得更好-但特别是功率3的情况下(60倍更快)。如果在一个紧凑的循环中运行整数幂大于2的 std: : pow () ，那么这一点绝对值得记住..。

小开

最有效的方法是考虑乘法的指数增长:

template <typename T>
T expt(T p, unsigned q){
T r =1;
while (q != 0) {
if (q % 2 == 1) {    // if q is odd
r *= p;
q--;
}
p *= p;
q /= 2;
}
return r;
}
小开

我一直忙于解决一个类似的问题，结果让我很困惑。我在 n 体情况下计算牛顿引力的 x-3/2(从位于距离向量 d 的另一个质量 M 物体的加速度) : a = M G d*(d²)⁻³/²(其中 d2是 d 本身的点(标量)乘积) ，我认为计算 M*G*pow(d2, -1.5)会比 M*G/d2/sqrt(d2)简单

诀窍在于，这对于小型系统来说是正确的，但是随着系统规模的增长，M*G/d2/sqrt(d2)会变得更有效率，我不明白为什么系统的规模会影响这个结果，因为在不同的数据上重复操作并不会影响这个结果。这就好像随着系统的增长存在可能的优化，但是对于 pow是不可能的

enter image description here


提交答案