时间戳

首页 > 解决方案 > 为什么 std::pow(int, int) 比带有整数值的 for 循环更快？

c++ - 为什么 std::pow(int, int) 比带有整数值的 for 循环更快？

问题描述

我和我的朋友写了一个计算多项式的程序：

P = ab n + a 2 b n-1 + a 3 b n-2 + ... a n b

他使用了 C++std::pow(int, int)函数，而我使用了两个 for 循环，因为我被告知带有整数的 for 循环比std::pow(int, int)函数快，或者在最坏的情况下速度几乎相同！

他的代码：

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a = 1,b = 1,n = 100000;
    long long P = 0;

    for(int i = 1, j = n; i <= n; i++, j--)
    {
        P += pow(a,i) * pow(b,j);
    }
    cout << P;
    return 0;
}

程序按预期返回 100000，执行时间为：0.048 秒，第二次运行时为 0.049 秒

但是，当我运行我的代码时：

#include <iostream>

using namespace std;

int main()
{
    int a = 1,b = 1,n = 100000;
    long long P = 0;

    for(int i = 1, j = n; i <= n; i++, j--)
    {
        int c = a, d = b;

        for (int k = 1; k < i; ++k) {

            c *= a;
        }

        for (int k = 1; k < j; ++k) {

            d *= b;
        }

        P += c * d;
    }
    cout << P;
    return 0;
}

程序再次返回预期的 100000，但执行时间：第二次运行时为 17.039 秒和 17.117 秒。

我的问题是，正如我一直被人们教导的那样，我在文章和教程中读到，std::pow(int, int)要么会比带有整数的 for 循环慢，要么速度几乎相等，为什么执行时间会有这样的如果我们将数字增加到 1000000，那么我的代码甚至需要几分钟才能执行，而pow(int, int)函数代码会在几秒钟内执行。

标签： c++loopsfor-loopexecution-timepow

解决方案

这完全取决于实现的质量std::pow，以及编译器的优化能力

例如，一些标准库对整数指数进行计算pow(x, y)，exp(log(x)*y)因此它可能不准确且速度慢，从而导致此类问题

但是一些更好pow的实现会检查指数是否为整数以使用更好的算法。他们还使用平方求幂，因此它们将比您的线性乘法（如 for 循环）快很多。例如对于 b 100000他们只需要 17 个循环而不是 100000

如果编译器足够聪明，可以识别您的循环来计算功率，它可能会std::pow完全转换为。但可能这不是你的情况，所以std::pow仍然更快。如果您编写pow(int, int)使用平方取幂的函数，那么它可能比std::pow

推荐阅读