为什么 std::pow(int, int) 比具有整数值的 for 循环快得多？

Question

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

P = abⁿ + a²b^n-1 + a³b^n-2 + ... aⁿ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;
}

程序returns 100000 与预期的执行时间：0.048 s 和 0.049 s 运行第二次

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

#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;
}

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

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

Answer 1

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

例如一些标准库计算 pow(x, y) 为 exp(log(x)*y) 即使对于整数指数，因此它可能不准确和缓慢，导致这些问题

Why does pow(5,2) become 24?
Why pow(10,5) = 9,999 in C++

但一些更好的 pow 实现检查指数是否为整数以使用更好的算法。他们还使用 exponentiating by squaring 所以他们会比你的线性乘法快很多，比如你的 for 循环。例如对于 b¹⁰⁰⁰⁰⁰ 他们只需要 17 个循环而不是 100000

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

更快

为什么 std::pow(int, int) 比具有整数值的 for 循环快得多？

Why is std::pow(int, int) way faster than for loop with integer values?

c++

loops

for-loop

execution-time

pow