c++ - 为什么标准 C++ 库中没有“int pow(int base, int exponent)”？

Question

我觉得我一定是找不到它。除了s 和s 之外，C++ 函数是否有任何理由pow不实现“power”函数？floatdouble

我知道实现是微不足道的，我只是觉得我正在做应该在标准库中的工作。强大的幂函数（即以某种一致、明确的方式处理溢出）编写起来并不有趣。

score 74 · Accepted Answer

从开始C++11，特殊情况被添加到幂函数（和其他）套件中。C++11 [c.math] /11状态，在列出所有float/double/long double重载（我的重点和释义）之后：

此外，应该有足够的额外重载以确保，如果与参数对应的任何double参数具有类型double或整数类型，则与参数对应的所有double参数都有效地转换为double.

因此，基本上，整数参数将升级为双精度数来执行操作。

在此之前C++11（这是在问您的问题时），不存在整数重载。

由于我既不与他们的创建者密切相关，C也不C++在他们创建的时代（尽管我相当老），也不是创建标准的 ANSI/ISO 委员会的一部分，这必然是我的观点。我想这是有见地的意见，但是，正如我妻子会告诉你的（经常而且不需要太多鼓励），我以前错了:-)

假设，对于它的价值，如下。

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

其次，您必须记住的另一件事是，最初的意图C是作为一种系统编程语言，浮点在该领域是否可取是值得怀疑的。

由于它最初的用例之一是编写 UNIX 代码，因此浮点数几乎没有用处。C 所基于的 BCPL 也没有使用幂（从内存中它根本没有浮点）。

顺便说一句，积分幂运算符可能是二元运算符而不是库调用。您不要添加两个整数，x = add (y, z)而是使用x = y + z-语言的一部分而不是库。

第三，由于积分幂的实现相对微不足道，几乎可以肯定该语言的开发人员会更好地利用他们的时间来提供更多有用的东西（见下面关于机会成本的评论）。

这也与原始C++. 由于最初的实现实际上只是一个生成C代码的翻译器，它继承了C. 它最初的意图是 C-with-classes，而不是 C-with-classes-plus-a-little-bit-of-extra-math-stuff。

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

该标准的后续版本也有特定的指导方针，可以在基本原理文件中找到（关于委员会为什么做出某些决定的基本原理，而不是语言本身的基本原理）。

例如，C99基本原理文件明确提出了两个C89限制可以添加内容的指导原则：

保持语言小而简单。
只提供一种方法来进行操作。

为各个工作组制定了指南（不一定是那些特定C++的指南），因此也限制了委员会（以及所有其他 ISO 组）。

此外，标准制定机构意识到他们做出的每一个决定都存在机会成本（一个经济术语，意思是你必须为做出决定而放弃的东西）。例如，购买价值 10,000 美元的超级游戏机的机会成本是与你的另一半建立约 6 个月的友好关系（或可能是所有关系）。

Eric Gunnerson 用他的-100 分解释很好地解释了为什么不总是将东西添加到 Microsoft 产品中 - 基本上，一个功能从 100 分开始，所以它必须增加相当多的价值才能被考虑。

换句话说，您更愿意在标准中添加一个完整的电源运算符（老实说，任何半体面的程序员都可以在十分钟内完成）还是多线程？就我自己而言，我更喜欢后者，而不必纠结于 UNIX 和 Windows 下的不同实现。

我还希望看到成千上万的标准库（散列、btree、红黑树、字典、任意映射等）的集合，但是，正如基本原理所述：

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

而且标准机构的实施者数量远远超过了程序员的数量（或者至少是那些不了解机会成本的程序员）。如果添加了所有这些东西，那么下一个标准C++将在C++215x300 年后由编译器开发人员完全实现并且可能会完全实现。

无论如何，这是我对此事的（相当大量的）想法。如果只根据数量而不是质量来投票，我很快就会把其他所有人都吓跑了。感谢收听：-）

score 42 · Accepted Answer

对于任何固定宽度的整数类型，几乎所有可能的输入对都会溢出类型。对绝大多数可能的输入都没有给出有用结果的函数进行标准化有什么用？

为了使函数有用，您几乎需要一个大整数类型，并且大多数大整数库都提供了该函数。

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

让我们搁置一旁exp，因为那是无关紧要的（尽管它实际上会使我的情况更强大），并专注于double pow(double x, double y). 该函数对 (x,y) 对的哪一部分有用（即，不只是上溢或下溢）？

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

现在让我们看一个固定宽度（即非bignum）整数幂函数。对于哪部分输入，它不会简单地溢出？为了最大化有意义的输入对的数量，基数应该是有符号的，而指数应该是无符号的。假设基数和指数都是n位宽。我们可以很容易地对有意义的输入部分进行限制：

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

因此，在 2^(2n) 个输入对中，少于 2^(n+1) + 2^(3n/2) 个会产生有意义的结果。如果我们看一下最常见的用法，32 位整数，这意味着大约 1% 的输入对的 1/1000 量级的东西不会简单地溢出。

score 12 · Accepted Answer

12

因为无论如何都无法在 int 中表示所有整数幂：

>>> print 2**-4
0.0625

于 2010-03-07T23:27:34.003 回答

score 9 · Accepted Answer

这实际上是一个有趣的问题。我在讨论中没有发现的一个论点是，这些论点缺乏明显的返回值。让我们计算一下假设int pow_int(int, int)函数可能失败的方式。

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

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

总体而言，将功能排除在外似乎是唯一明智的选择。程序员可以使用具有所有可用错误报告的浮点版本。

score 7 · Accepted Answer

简短的回答：

pow(x, n)到哪里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。没有硬件有这么极端内存限制，除了一些不可靠的 PIC，它们的硬件堆栈只有 3 到 8 个函数调用深度。）

至于性能，您会对花园品种pow(double, double)的能力感到惊讶。我在我 5 岁的 IBM Thinkpad 上测试了一亿次迭代，x迭代次数n等于 10。在这种情况下，pown_l赢了。glibcpow()耗时 12.0 秒，pown耗时 7.4 秒，pown_l仅耗时 6.5 秒。所以这并不奇怪。我们或多或少对此有所期待。

然后，我x保持不变（我设置为 2.5），n从 0 循环到 19 亿次。这一次，出乎意料的是，glibcpow以压倒性优势获胜！只用了 2.0 用户秒。我pown用了 9.6 秒，pown_l用了 12.2 秒。这里发生了什么？我做了另一个测试来找出答案。

我做了与上面相同的事情，只有x一百万。这一次，pown以 9.6 秒获胜。pown_l耗时 12.2 秒，glibc pow 耗时 16.3 秒。现在，很清楚了！glibc在低pow时表现优于三者x，但在高时表现最差x。x高时，低pown_l时表现最佳，高时表现最佳。npownx

因此，这里有三种不同的算法，在适当的情况下，每种算法都能比其他算法表现得更好。因此，最终，使用哪个最有可能取决于您计划如何使用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);
}

As long as x_expectedand n_expectedare constants decided at compile time, along with possibly some other caveats, an optimising compiler worth its salt will automatically remove the entire pown_autofunction call and replace it with the appropriate choice of the three algorithms. （现在，如果你真的要尝试使用它，你可能不得不稍微玩弄它，因为我没有完全尝试编译我上面写的内容。;)）

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

脚注：在时间性能测试中，我给了我的函数相对慷慨的优化标志-s -O2（公平的。对于更严格的测试，我必须自己编译 glibc，而且我真的不想这样做。我曾经使用过 Gentoo，所以我记得需要多长时间，即使任务是自动化的。结果对我来说是决定性的（或者说是不确定的）。当然欢迎你自己做这件事。

奖励回合：如果需要精确的整数输出，则pow(x, n)对所有整数的专门化是有帮助的，这确实发生了。考虑为具有 p^N 个元素的 N 维数组分配内存。将 p^N 减一会导致可能随机发生的段错误。

score 6 · Accepted Answer

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

获得稍微准确的结果也意味着获得稍微不同的结果。

score 3 · Accepted Answer

世界在不断发展，编程语言也在不断发展。C 十进制 TR ¹的第四部分为<math.h>. 这些函数的两个系列可能对这个问题感兴趣：

pown接受浮点数和指数的函数intmax_t。
这些powr函数采用两个浮点数 (x和y) 并使用公式计算x幂。yexp(y*log(x))

似乎标准人员最终认为这些功能足够有用，可以集成到标准库中。然而，合理的是这些函数是ISO/IEC/IEEE 60559:2011标准推荐的二进制和十进制浮点数。我不能确定 C89 时遵循了什么“标准”，但未来的演变<math.h>可能会受到ISO/IEC/IEEE 60559标准未来演变的严重影响。

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

¹您可以在此处找到一些正在进行的文档。

score 3 · Accepted Answer

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

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 倍的内存更新

score 2 · Accepted Answer

也许是因为处理器的 ALU 没有为整数实现这样的功能，但是有这样的 FPU 指令（正如斯蒂芬指出的那样，它实际上是一对）。因此，转换为双精度，使用双精度调用 pow，然后测试溢出并返回，实际上比使用整数算术实现它要快。

（一方面，对数会降低乘法的幂，但整数的对数会在大多数输入中失去很多准确性）

斯蒂芬是对的，在现代处理器上这不再是真的，但是选择数学函数时的 C 标准（C++ 只使用 C 函数）现在是什么，20 岁了？

score -3 · Accepted Answer

事实上，确实如此。

由于 C++11 有pow(int, int)--- 的模板化实现，甚至更一般的情况，请参见 http://en.cppreference.com/w/cpp/numeric/math/pow中的 (7)

编辑：纯粹主义者可能会认为这是不正确的，因为实际上使用了“提升”类型。一种或另一种方式，在参数上得到正确的int结果或错误。int

score -4 · Accepted Answer

一个非常简单的原因：

5^-2 = 1/25

STL 库中的所有内容都基于可以想象的最准确、最强大的东西。当然，int 会返回零（从 1/25 开始），但这将是一个不准确的答案。

我同意，在某些情况下这很奇怪。

c++ - 为什么标准 C++ 库中没有“int pow(int base, int exponent)”？

11 回答 11

Related

Reference