为什么标准C++库中没有`int pow(int base, int exponent)`函数？

Question

我觉得我一定是找不到它。是否有任何理由，导致C++的 pow 函数除了 float 和 double 以外，不实现“幂”函数？

我知道实现很简单，但我觉得我正在做应该在标准库中的工作。一个强大的幂函数（即以某种一致、明确的方式处理溢出）不是很好写。

- Dan O

---

这是一个好问题，我认为答案并不是很有意义。负数指数不起作用？将无符号整数作为指数。多数输入会导致溢出？exp和double pow也是如此，我没有看到任何人抱怨。那么为什么这个函数不是标准的？ - static_rtti

@static_rtti：“exp和double pow也是如此”这种说法完全是错误的。我会在我的回答中详细阐述。 - Stephen Canon

自 C++11 (§26.8[c.math]/11 第二个小点) 起，标准 C++ 库有一个 double pow(int base, int exponent) 函数。该函数用于计算底数为整型的次方指数的幂值。 - Cubbi

你需要在“实现很简单”和“写起来不好玩”之间做出决定。 - user207421

Answer 1

从 C++11 开始，一些特殊情况被添加到了幂函数（和其他函数）的套件中。 根据 C ++ 11 [c.math] / 11 （其中列出了所有的 float/double/long double 重载），如下所述：

此外，还应有足够的其他重载以确保，如果与 double 参数相对应的任何参数具有 double 或整数类型，则与 double 参数相对应的所有参数都被有效地强制转换为 double。

因此，基本上将整数参数升级为 double 类型以执行操作。

---

在 C++11 之前（也是提出问题时的情况），不存在整数重载。

由于我既不是 C 或 C++ 的创建者，也不是创建标准的 ANSI/ISO 委员会的成员（尽管我很老），因此这必然是我的观点。我认为这是一个有根据的观点，但是，正如我的妻子经常并且不需要太多的鼓励告诉你的那样，我曾经犯过错误 :-)

以下是我推测的情况。

我认为最初的 ANSI 前的 C 没有这个功能的原因是完全没有必要。首先，已经有一种非常好的方法来进行整数幂运算（使用双精度浮点数然后简单地转换回整数，在转换之前检查整数溢出和下溢）。

其次，您还必须记住，C 的最初意图是作为一个系统编程语言，而在这个领域是否需要浮点数是值得怀疑的。

由于其最初的使用案例之一是编写UNIX，浮点数将几乎没有用处。基于BCPL语言的C语言也没有使用幂运算（从记忆中它根本没有浮点数）。

顺便提一下，整数幂操作符可能本来就应该是一个二元运算符而不是库函数调用。你不是用 x = add(y, z) 来相加两个整数，而是用 x = y + z - 这是语言本身的一部分而不是库。

第三，由于实现整数幂相对简单，开发者们肯定会更好地利用他们的时间提供更有用的东西（查看下面关于机会成本的评论）。

这对原始的C++也是相关的。由于原始的实现实际上只是一个翻译器，产生了C代码，因此它继承了许多C的属性。它最初的意图是带类的C，而不是带类加一点额外数学东西的C。

至于为什么在C++11之前从未添加到标准中，您必须记住标准制定机构有特定的指导方针要遵循。例如，ANSIC专门负责编码现有实践，而不是创建新语言。否则，他们可能会疯狂并给我们提供Ada :-)

该标准的后续版本也有具体的指南，并且可以在理论文档中找到（关于委员会做出某些决定的理由，而不是有关语言本身的理由）。

例如，C99理论文档明确延续了C89的两个指导原则，限制了可以添加的内容：

• 使语言保持小巧简单。
  
• 仅提供执行操作的一种方式。

各个工作组为个人设置了指导方针，因此也限制了C++委员会（以及所有其他ISO组）。

此外，标准制定机构认识到每个决策都有一定的“机会成本”（经济学术语，指因做出某个决策而必须放弃的其他选择机会）。例如，购买那台价值10000美元的超级游戏机将会导致你与另一半的关系变得微妙（或可能是没有关系）长达六个月，这就是机会成本。

Eric Gunnerson在他的博客-100 points explanation中很好地解释了为什么不会将所有功能都加入Microsoft产品-基本上，一个新功能默认会减去100分，因此它必须提供足够的价值才能被考虑添加。

换句话说，您更愿意在标准中添加一个整数幂运算符（其实，任何半靠谱的编码人员都可以在10分钟内完成），还是添加多线程呢？对我而言，我更喜欢后者，不想在UNIX和Windows下进行各种不同的实现。

我也希望标准库中能包含成千上万的集合（哈希表、B树、红黑树、字典、任意映射等），但正如相关原理所述：

“标准是实现者和程序员之间的协议。”

标准制定机构的实现者数量远远超过程序员数量（或者至少是那些不理解机会成本的程序员）。如果所有这些都被添加进去，下一个C++标准将变成C++215x，并且可能会在300年后被编译器开发人员完全实现。

总之，以上是我对此事的（相当冗长的）想法。如果只是根据数量而不是质量来分配票数，我很快就可以击败其他所有人。谢谢你的倾听 :-)

- paxdiablo

---

就我个人而言，我认为C++并不遵循“仅提供一种执行操作的方式”这一限制。这是正确的，因为例如to_string和lambda表达式都是方便的工具，可用于已经存在的操作。我想人们可能可以非常宽松地解释“只有一种方法来执行操作”，以允许这两者，同时几乎可以想象任何功能的重复，通过说“啊哈！不行！因为这些方便之处使其与精确等效但更冗长的替代品略有不同！”。对于lambda表达式这一点肯定是正确的。 - Steve Jessop

仅仅是其中一点： "任何代码程序员十分钟就能搞定"。当然，如果每年有100个代码程序员（这个用词很侮辱人，顺便说一下）这样做（可能是低估了），我们就浪费了1000分钟。效率非常高，是吧？ - Jürgen A. Erhard

@Jürgen，这并不是要冒犯任何人（因为我实际上没有将标签归属给任何特定的人），只是表明pow并不需要太多技巧。当然，我宁愿标准提供一些需要很多技能的东西，并且如果必须重复努力，会导致更多浪费的时间。 - paxdiablo

@JürgenA.Erhard：更糟糕的是，每个检查调用某个自定义函数来执行此操作的人都需要检查该函数，以确定它实际上是否以符合调用方需求的方式运行。 - supercat

@eharo2，请将当前文本中的“半吊子程序员”替换为“码农”。我认为这并不是一种侮辱，但我认为最好谨慎一些，说实话，当前的措辞传达了相同的意思。 - paxdiablo

Answer 2

对于任何固定宽度的整数类型，几乎所有可能的输入对都会溢出该类型。那么标准化一个在其大多数可能的输入下都不能给出有用结果的函数有什么用呢？

你需要一个大整数类型才能使该函数变得有用，并且大多数大整数库都提供了该函数。

---

编辑： 在问题的评论中，static_rtti写道“大多数输入会导致溢出？exp和double pow也是如此，我没有看到任何抱怨。” 这是不正确的。

让我们暂且不管exp，因为这与重点无关（尽管实际上这会更加支持我的观点），并聚焦于double pow(double x, double y)。这个函数在哪些(x,y)对的部分可以产生有用的结果（即不会简单地溢出或下溢）？

我只会关注一小部分的输入对，证明我的观点就足够了：如果x是正数且|y|≤1，则pow不会溢出或下溢。这包括近四分之一的浮点数对（非NaN浮点数的一半为正，略小于一半的非NaN浮点数的大小小于1）。显然，还有许多其他输入对可以产生有用的结果，但是我们已经确定它至少占所有输入的四分之一。

现在让我们来看看一个固定宽度（即非大整数）的整数幂函数。在哪些输入中它不会简单地溢出？为了最大限度地提高有意义的输入对的数量，基数应为有符号的，指数应为无符号的。假设基数和指数都是n位宽。我们可以轻松地获得有意义的输入部分的下界：

• 如果指数为0或1，则任何基数都是有意义的。
• 如果指数大于等于2，则没有比2^(n/2)更大的底数会产生有意义的结果。

因此，在2^(2n)个输入对中，少于2^(n+1) + 2^(3n/2)个对将产生有意义的结果。如果我们看一下最常见的用法，即32位整数，这意味着大约千分之一的输入对不仅仅是溢出。

- Stephen Canon

---

无论如何，这都是无谓的。仅因为某些或很多输入值对于某个函数无效，并不意味着它变得不那么有用。 - static_rtti

@static_rtti：如果|y|<=1，则pow(x,y)不会向零下溢。对于一些输入（大x，y接近-1），会出现非常狭窄的带状区域发生下溢，但在该范围内结果仍然是有意义的。 - Stephen Canon

@static：这很重要。如果我必须决定是否包含此函数，这正是我不会包含它的原因。 - Yakov Galka

为什么你会选择这个原因呢？我个人更倾向于解决大量问题和程序员的有用性，以及可能制作比大多数程序员编写的朴素实现更快的硬件优化版本等。你的标准似乎完全是武断的，并且说实话，相当无意义。 - static_rtti

光明的一面是，你的论点表明整数pow的显然正确和最优实现只需要一个小小的查找表。 :-) - R.. GitHub STOP HELPING ICE

Answer 3

因为在int类型中无法表示所有的整数次幂:

>>> print 2**-4
0.0625

- Ignacio Vazquez-Abrams

---

对于有限大小的数字类型，由于溢出的原因，无法在该类型内表示所有该类型的幂。但是你关于负幂的观点更为有效。 - Chris Lutz

我认为负指数可以作为标准实现的一部分来处理，可以通过将无符号整数作为指数或在提供负指数作为输入且期望输出为整数时返回零来处理。 - Dan O

或者拥有单独的 int pow(int base, unsigned int exponent) 和 float pow(int base, int exponent) 函数。 - Ponkadoodle

他们可以将其声明为未定义行为以传递负整数。 - Johannes Schaub - litb

在所有现代实现中，超出int pow(int base, unsigned char exponent)的任何内容都有些无用。要么基数为0或1，指数不重要，为-1，在这种情况下，只有指数的最后一位是有意义的，要么是base >1 || base< -1，在这种情况下，exponent<256，否则会溢出。 - MSalters

除了所有其他出色的帖子和所有关于溢出等的哲学讨论之外，这是为什么没有int = pow（int，int）的最好理由。“没有办法在int中表示所有整数幂。” - eharo2

Answer 4

这实际上是一个有趣的问题。在讨论中，我没有找到一个简单的论点来解释参数的明显返回值不足。让我们来看看假设的 int pow_int(int, int) 函数可能失败的方式。

1. 溢出
2. 结果未定义 pow_int(0,0)
3. 结果无法表示 pow_int(2,-1)

该函数至少有2种故障模式。整数无法表示这些值，函数在这些情况下的行为需要由标准定义 - 程序员需要知道函数如何处理这些情况。

总的来说，省略该函数似乎是唯一明智的选择。程序员可以使用带有所有错误报告的浮点版本。

- phoku

---

但是前两种情况不也适用于浮点数之间的pow吗？取两个大浮点数，将一个数的幂次方提高到另一个数，就会出现溢出。而且pow(0.0, 0.0)也会导致你第二点所述的问题。你第三点才是实现整数和浮点数幂函数的唯一真正区别。 - numbermaniac

Answer 5

简短回答：

对于自然数n，将pow(x, n)进行特化通常有助于提高时间性能。但是标准库的通用pow()仍然非常适用于此目的，并且在标准C库中包含尽可能少的内容非常关键，以便使其具有最大的可移植性和易于实现性。另一方面，这并不妨碍它成为C++标准库或STL的一部分，我相信没有人计划在某种嵌入式平台上使用它。

现在，详细回答如下。

pow(x, n)可以通过将n特化为自然数，在许多情况下大大提高速度。我几乎每次编写数学程序时都需要使用自己的实现函数（但我经常使用C语言编写数学程序）。专门操作可以在O(log(n))时间内完成，但当n较小时，较简单的线性版本可能更快。以下是两种实现：

    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

（我使用双精度浮点数作为变量x和返回值，因为pow（double x，unsigned n）的结果与pow（double，double）的结果一样适合于双精度浮点数。）

（是的，pown是递归的，但破坏堆栈绝对是不可能的，因为最大堆栈大小大约等于log_2（n），而n是整数。如果n是64位整数，则给您约为64的最大堆栈大小。除了一些只能进行3到8个函数调用深度的有问题的PIC具有硬件堆栈之外，没有任何硬件具有如此极端的内存限制。）

至于性能，您将会惊讶于普通的pow（double，double）能够做到什么。我在我的5年老IBM Thinkpad上测试了1亿次迭代，其中x等于迭代次数，n等于10。在这种情况下，pown_l胜出。glibc pow（）需要12.0秒用户时间，pown需要7.4秒用户时间，而pown_l仅需要6.5秒用户时间。所以这并不令人惊讶。我们或多或少地预料到了这一点。

然后，我让x保持不变（将其设置为2.5），并将n从0到19循环1亿次。这次，出乎意料地，glibc pow赢了，并且大幅领先！它只花费了2.0秒用户时间。我的pown需要9.6秒，而pown_l需要12.2秒。这里发生了什么？我进行了另一个测试以找出答案。

我做了与上述相同的事情，只是将x设置为一百万。这次，pown在9.6秒内获胜。pown_l需要12.2秒，而glibc pow需要16.3秒。现在，很清楚了！当x较低时，glibc pow的性能优于其他三种情况，但当x较高时，则最差。当x较高时，pown_l在n较低时性能最佳，而pown在x较高时性能最佳。

因此，这里有三种不同的算法，每种算法都能在正确的情况下比其他算法表现更好。因此，最终使用哪个版本可能取决于您计划如何使用pow，但是使用正确的版本是值得的，并且拥有所有版本也很好。实际上，您甚至可以使用此类函数自动选择算法：

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

只要 x_expected 和 n_expected 是在编译时确定的常量，并且可能还有其他一些注意事项，一个值得其盐的优化编译器将自动删除整个 pown_auto 函数调用并用三种算法中适当的选择替换它。(现在，如果你实际上要尝试使用这个，你可能需要稍微玩弄一下，因为我并没有确切地尝试编译我上面写的内容。 ;))

另一方面，glibc 的 pow 是有效的，而且 glibc 已经足够大了。C 标准应该是可移植的，包括对各种嵌入式设备的支持(事实上，到处都有嵌入式开发人员普遍认为 glibc 对他们来说已经太大了)，如果对于每个简单的数学函数它需要包含每个可能有用的替代算法，那么它就无法移植。所以，这就是为什么它不在 C 标准中的原因。

脚注: 在时间性能测试中，我给我的函数相对宽松的优化标志(-s -O2)，这些标志可能与在我的系统(archlinux)上编译 glibc 时使用的标志相当或更差，所以结果可能是公正的。要进行更严格的测试，我必须自己编译 glibc，但我真的不想这样做。我曾经使用 Gentoo，所以我记得它需要多长时间，即使任务是自动化的。对我来说，结果已经足够(或者说是不确定的)。当然，你也可以自己尝试。

额外奖励: 对于所有整数的 pow(x, n) 的特殊化是非常重要的，如果需要精确的整数输出，这确实会发生。考虑为一个有 p^N 个元素的 N 维数组分配内存。如果 p^N 偏差超过一个，那么可能会随机出现 segfault。

- enigmaticPhysicist

---

我猜如果你摆脱递归，就可以节省堆栈分配所需的时间。我们曾经遇到过pow使所有的运算变慢的情况，所以我们不得不实现自己的pow函数。 - Sambatyon

“没有人有如此极端的内存限制”是错误的。PIC通常具有有限的调用堆栈，最多为3个（例如PIC10F200）到8个（例如16F722A）调用（PIC使用硬件堆栈进行函数调用）。 - 12431234123412341234123

哦，天啊，那太残酷了，哈哈。好的，那么它在那些PIC上不起作用。 - enigmaticPhysicist

对于像问题所询问的整数基数和指数，编译器（如gcc和clang）将轻松地从迭代（而不是递归）实现生成无分支循环。这避免了来自n的每个位的分支预测错误。 https://godbolt.org/z/L9Kb98. gcc和clang未能将您的递归定义优化为简单的循环，并实际上在n的每个位上进行分支。（对于pown_iter（double，unsigned），它们仍然分支，但可以使用x86 asm或C intrinsics实现无分支SSE2或SSE4.1的实现，但即使是这样也比递归好）。 - Peter Cordes

糟糕，现在我必须再次进行基于循环的基准测试，以确保结果。我会考虑一下。 - enigmaticPhysicist

Answer 6

C++没有额外的重载函数是为了与C兼容。C++98有一些函数，如double pow(double, int)，但在C++11中已被删除，因为C99没有包含它们。参考http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550。获得稍微更准确的结果也意味着获得稍微不同的结果。

- Bo Persson

Answer 7

下面是一个非常简单的O(log(n)) pow() 实现，适用于任何数字类型，包括整数:

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

这个实现比enigmaticPhysicist的O(log(n))算法更好，因为它不使用递归。

而且，只要p > ~3，它几乎总是比他的线性实现快，因为：

• 它不需要额外的内存
• 每次循环只需要多做约1.5倍的操作
• 每次循环只需要多做约1.25倍的内存更新

- serg06

Answer 8

世界不断发展，编程语言也在不断演进。C十进制 TR 的第四部分¹在<math.h>中添加了一些函数。其中两个函数族可能对此问题有所帮助：

• pown 函数，它接受一个浮点数和一个 intmax_t 指数。
• powr 函数，它接受两个浮点数（x 和 y），并使用公式exp(y*log(x))计算x的y次幂。

似乎标准委员会最终认为这些功能足够有用，可以集成到标准库中。然而，理性的解释是这些函数被ISO/IEC/IEEE 60559:2011标准推荐用于二进制和十进制浮点数。我无法确定在C89时期遵循了哪个“标准”，但<math.h>的未来发展可能会受到ISO/IEC/IEEE 60559标准未来发展的重大影响。

请注意，十进制TR的第四部分将不会包含在C2x（下一个主要的C修订版）中，并且可能稍后作为可选功能包含。据我所知，没有意图将此部分TR包含在未来的C++修订版中。

---

¹ 你可以在这里找到一些正在进行中的文档 链接。

- Morwenn

---

有没有什么合理的实现方式，使用大于LONG_MAX的指数使用pown应该产生与使用LONG_MAX不同的值，或者小于LONG_MIN的值应该产生与LONG_MIN不同的值？我想知道使用intmax_t作为指数所获得的好处是什么？ - supercat

@supercat 不好意思，我不知道。 - Morwenn

值得一提的是，从标准来看，它似乎还定义了一个可选的“crpown”函数，如果定义了，它将是“pown”的正确舍入版本；否则，标准不指定所需的精度。实现快速且适度精确的“pown”很容易，但在所有情况下确保正确舍入可能会更加昂贵。 - supercat

Answer 9

也许是因为处理器的ALU没有为整数实现这样的功能，但有一个FPU指令（正如Stephen所指出的，它实际上是一对）。因此，将其转换为双精度浮点数，使用双精度浮点数调用pow函数，然后测试溢出并进行转换，实际上比使用整数算术实现更快。

（首先，对数将幂减少到乘法，但整数的对数对于大多数输入失去了很多精度）

Stephen正确地指出，在现代处理器上，这已不再成立，但当选择数学函数时，C标准（C++只使用了C函数）现在已经有20年了？

- Ben Voigt

---

我不知道有任何现代架构有一个针对 pow 的 FPU 指令。x86 有一个 y log2 x 指令 (fyl2x)，可以作为 pow 函数的第一部分使用，但是以这种方式编写的 pow 函数在当前硬件上需要数百个周期才能执行；一个良好编写的整数指数运算程序则要快几倍。 - Stephen Canon

我不知道“数百”是否准确，对于大多数现代CPU，在fyl2x和f2xm1上大约需要150个周期，而且这些指令会与其他指令一起使用。但你是对的，经过良好调整的整数实现应该会更快（现在）因为IMUL已经比浮点指令加速得多。然而，在编写C标准时，IMUL非常昂贵，并且在循环中使用它可能比使用FPU花费更长时间。 - Ben Voigt

考虑到更正，我改变了我的投票；但是请记住：（a）C标准在1999年经历了一次重大修订（包括数学库的大规模扩展），（b）C标准并不针对任何特定的处理器架构编写 - x86上FPU指令的存在或缺失基本上与C委员会选择标准化的功能无关。 - Stephen Canon

它并没有绑定任何体系结构，但我猜查找表插值（通常用于浮点实现）相对于整数乘法的成本比已经在所有体系结构上发生了巨大的变化。 - Ben Voigt

Answer 10

事实上，它确实如此。

自从C++11以来，pow(int, int)有模板化的实现方式---甚至还有更加普通的情况，请参见（7）在http://en.cppreference.com/w/cpp/numeric/math/pow中

---

编辑：纯粹主义者可能会认为这不正确，因为实际上使用了“推广”输入法。无论如何，在 int 参数上，一个可以得到正确的结果或错误。

- Dima Pasechnik

---

这是不正确的。(7)重载是pow(Arithmetic1 base, Arithmetic2 exp)，如果您已经阅读了描述，则会转换为double或long double。描述如下：“7）一组重载或函数模板，用于所有未被1-3）覆盖的算术类型参数的组合。如果任何参数具有整数类型，则将其转换为double。如果任何参数是long double，则返回类型Promoted也是long double，否则返回类型始终为double。” - phuclv

这里有什么不正确的吗？我只是说现在（自C++11以来），标准库中有一个模板化的pow(,)，而在2010年并非如此。 - Dima Pasechnik

不，它不会。模板将这些类型提升为double或long double，因此它适用于底层的double类型。 - Trismegistos

@Trismegistos 它仍然允许int参数。如果没有这个模板，传递int参数会导致将int中的位解释为float，从而导致任意意外结果。混合输入值也是如此。例如 pow(1.5f, 3) = 1072693280 但是 pow(1.5f, float(3)) = 3.375 - Mark Jeronimus

OP 要求 int pow(int, int)，但 C++ 11 只提供了 double pow(int, int)。请参考 @phuclv 的解释。 - xuhdev

无论实现是否进行双精度转换，更多的是实现细节 - 只要能保证正确答案即可。 - Dima Pasechnik