为什么标准 C++ 中没有 `int pow(int base, int exponent)`?图书馆?

发布于 2024-08-24 23:13:17 字数 180 浏览 19 评论 0原文

我感觉我一定是找不到它了。除了 floatdouble 之外,C++ pow 函数没有实现“power”函数,有什么原因吗?

我知道实现很简单,我只是觉得我正在做应该在标准库中的工作。编写健壮的幂函数(即以某种一致、显式的方式处理溢出)并不有趣。

I feel like I must just be unable to find it. Is there any reason that the C++ pow function does not implement the "power" function for anything except floats and doubles?

I know the implementation is trivial, I just feel like I'm doing work that should be in a standard library. A robust power function (i.e. handles overflow in some consistent, explicit way) is not fun to write.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(11

辞取 2024-08-31 23:13:17

C++11 开始,特殊情况已添加到幂函数套件(以及其他函数)中。 C++11 [c.math] /11 指出,在列出所有 float/double/long double 重载之后(我的重点,以及释义):

此外,应有足够的额外重载来确保,如果与 double 参数对应的任何参数具有类型 double 或整数类型,那么与 double 参数相对应的所有实参都将有效地转换为 double

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


C++11 之前(当您提出问题时),不存在整数重载。

因为在 CC++ 的创建者创建时,我与他们的关系并不密切(尽管我已经很老了),也不参与其中。制定这些标准的 ANSI/ISO 委员会的意见,这必然是我的意见。我想认为这是知情的意见,但是,正如我妻子会告诉你的那样(经常而且不需要太多鼓励),我以前就错了:-)

假设,无论其价值如何,如下。

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

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

由于其最初的用例之一是编写 UNIX 代码,因此浮点几乎毫无用处。 C 所基于的 BCPL 也没有使用幂(根据记忆,它根本没有浮点数)。

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

第三,由于积分算力的实现相对微不足道,因此几乎可以肯定,该语言的开发人员会更好地利用他们的时间提供更有用的东西(请参阅下面关于机会成本的评论)。

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

至于为什么它在 C++11 之前从未被添加到标准中,您必须记住,标准制定机构有具体的指导方针需要遵循。例如,ANSI C 的具体任务是编纂现有实践,而不是创建一种新语言。否则,他们可能会发疯并给我们 Ada :-)

该标准的后续迭代也有具体的指导方针,并且可以在基本原理文件中找到(关于委员会为何做出某些决定的基本原理,而不是语言本身的基本原理)。

例如,C99 基本原理文档专门弘扬了 C89 的两个指导原则,这些原则限制了可以添加的内容:

  • 保持语言小而简单。
  • 仅提供一种方法做手术。

指导方针(不一定是那些特定的指导方针)是为各个工作组制定的,因此也限制了C++委员会(以及所有其他ISO小组)。

此外,标准制定机构意识到他们做出的每一个决定都存在机会成本(一个经济术语,意味着做出决定时必须放弃的东西)。例如,购买价值 10,000 美元的超级游戏机的机会成本是与您的另一半大约六个月的亲切关系(或者可能所有关系)。

Eric Gunnerson 的-100 分解释 至于为什么微软的产品并不总是添加一些东西——基本上一个功能从100分开始,所以它必须增加相当多的价值才能被考虑。

换句话说,您愿意在标准中添加一个完整的电源运算符(老实说,任何半点像样的编码器都可以在十分钟内完成)还是多线程?对于我自己来说,我更喜欢后者,而不必纠结于 UNIX 和 Windows 下的不同实现。

我还希望看到标准库中成千上万的集合(哈希、btree、红黑树、字典、任意映射等),但是,正如其基本原理所述:

标准是实现者和程序员之间的条约。

标准机构中实施者的数量远远超过程序员的数量(或者至少是那些不了解机会成本的程序员)。如果添加了所有这些内容,下一个标准 C++ 将是 C++215x,并且可能会在三百年后由编译器开发人员完全实现。

无论如何,这就是我对此事的(相当长的)想法。如果只根据数量而不是质量来投票,我很快就会把其他人都打垮。感谢您的聆听:-)

As of C++11, special cases were added to the suite of power functions (and others). C++11 [c.math] /11 states, after listing all the float/double/long double overloads (my emphasis, and paraphrased):

Moreover, there shall be additional overloads sufficient to ensure that, if any argument corresponding to a double parameter has type double or an integer type, then all arguments corresponding to double parameters are effectively cast to double.

So, basically, integer parameters will be upgraded to doubles to perform the operation.


Prior to C++11 (which was when your question was asked), no integer overloads existed.

Since I was neither closely associated with the creators of C nor C++ in the days of their creation (though I am rather old), nor part of the ANSI/ISO committees that created the standards, this is necessarily opinion on my part. I'd like to think it's informed opinion but, as my wife will tell you (frequently and without much encouragement needed), I've been wrong before :-)

Supposition, for what it's worth, follows.

I suspect that the reason the original pre-ANSI C didn't have this feature is because it was totally unnecessary. First, there was already a perfectly good way of doing integer powers (with doubles and then simply converting back to an integer, checking for integer overflow and underflow before converting).

Second, another thing you have to remember is that the original intent of C was as a systems programming language, and it's questionable whether floating point is desirable in that arena at all.

Since one of its initial use cases was to code up UNIX, the floating point would have been next to useless. BCPL, on which C was based, also had no use for powers (it didn't have floating point at all, from memory).

As an aside, an integral power operator would probably have been a binary operator rather than a library call. You don't add two integers with x = add (y, z) but with x = y + z - part of the language proper rather than the library.

Third, since the implementation of integral power is relatively trivial, it's almost certain that the developers of the language would better use their time providing more useful stuff (see below comments on opportunity cost).

That's also relevant for the original C++. Since the original implementation was effectively just a translator which produced C code, it carried over many of the attributes of C. Its original intent was C-with-classes, not C-with-classes-plus-a-little-bit-of-extra-math-stuff.

As to why it was never added to the standards before C++11, you have to remember that the standards-setting bodies have specific guidelines to follow. For example, ANSI C was specifically tasked to codify existing practice, not to create a new language. Otherwise, they could have gone crazy and given us Ada :-)

Later iterations of that standard also have specific guidelines and can be found in the rationale documents (rationale as to why the committee made certain decisions, not rationale for the language itself).

For example the C99 rationale document specifically carries forward two of the C89 guiding principles which limit what can be added:

  • Keep the language small and simple.
  • Provide only one way to do an operation.

Guidelines (not necessarily those specific ones) are laid down for the individual working groups and hence limit the C++ committees (and all other ISO groups) as well.

In addition, the standards-setting bodies realise that there is an opportunity cost (an economic term meaning what you have to forego for a decision made) to every decision they make. For example, the opportunity cost of buying that $10,000 uber-gaming machine is cordial relations (or probably all relations) with your other half for about six months.

Eric Gunnerson explains this well with his -100 points explanation as to why things aren't always added to Microsoft products- basically a feature starts 100 points in the hole so it has to add quite a bit of value to be even considered.

In other words, would you rather have a integral power operator (which, honestly, any half-decent coder could whip up in ten minutes) or multi-threading added to the standard? For myself, I'd prefer to have the latter and not have to muck about with the differing implementations under UNIX and Windows.

I would like to also see thousands and thousands of collection the standard library (hashes, btrees, red-black trees, dictionary, arbitrary maps and so forth) as well but, as the rationale states:

A standard is a treaty between implementer and programmer.

And the number of implementers on the standards bodies far outweigh the number of programmers (or at least those programmers that don't understand opportunity cost). If all that stuff was added, the next standard C++ would be C++215x and would probably be fully implemented by compiler developers three hundred years after that.

Anyway, that's my (rather voluminous) thoughts on the matter. If only votes were handed out based on quantity rather than quality, I'd soon blow everyone else out of the water. Thanks for listening :-)

沉溺在你眼里的海 2024-08-31 23:13:17

无论如何,对于任何固定宽度整数类型,几乎所有可能的输入对都会溢出该类型。如果一个函数对于绝大多数可能的输入都没有给出有用的结果,那么标准化这个函数有什么用呢?

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


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

我们先把 exp 放在一边,因为那不是重点(尽管它实际上会让我的情况更有说服力),而专注于 double pow(double x, double y)。该函数对于 (x,y) 对的哪一部分执行有用的操作(即,不仅仅是上溢或下溢)?

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

现在让我们看一下固定宽度(即非大数)整数幂函数。对于哪部分输入,它不会简单地溢出?为了最大化有意义的输入对的数量,应该对基数进行签名,而对指数进行无符号签名。假设底数和指数都是 n 位宽。我们可以轻松地得到有意义的输入部分的界限:

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

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

For any fixed-width integral type, nearly all of the possible input pairs overflow the type, anyway. What's the use of standardizing a function that doesn't give a useful result for vast majority of its possible inputs?

You pretty much need to have an big integer type in order to make the function useful, and most big integer libraries provide the function.


Edit: In a comment on the question, static_rtti writes "Most inputs cause it to overflow? The same is true for exp and double pow, I don't see anyone complaining." This is incorrect.

Let's leave aside exp, because that's beside the point (though it would actually make my case stronger), and focus on double pow(double x, double y). For what portion of (x,y) pairs does this function do something useful (i.e., not simply overflow or underflow)?

I'm actually going to focus only on a small portion of the input pairs for which pow makes sense, because that will be sufficient to prove my point: if x is positive and |y| <= 1, then pow does not overflow or underflow. This comprises nearly one-quarter of all floating-point pairs (exactly half of non-NaN floating-point numbers are positive, and just less than half of non-NaN floating-point numbers have magnitude less than 1). Obviously, there are a lot of other input pairs for which pow produces useful results, but we've ascertained that it's at least one-quarter of all inputs.

Now let's look at a fixed-width (i.e. non-bignum) integer power function. For what portion inputs does it not simply overflow? To maximize the number of meaningful input pairs, the base should be signed and the exponent unsigned. Suppose that the base and exponent are both n bits wide. We can easily get a bound on the portion of inputs that are meaningful:

  • If the exponent 0 or 1, then any base is meaningful.
  • If the exponent is 2 or greater, then no base larger than 2^(n/2) produces a meaningful result.

Thus, of the 2^(2n) input pairs, less than 2^(n+1) + 2^(3n/2) produce meaningful results. If we look at what is likely the most common usage, 32-bit integers, this means that something on the order of 1/1000th of one percent of input pairs do not simply overflow.

吹泡泡o 2024-08-31 23:13:17

因为无论如何都没有办法用 int 来表示所有整数幂:

>>> print 2**-4
0.0625

Because there's no way to represent all integer powers in an int anyways:

>>> print 2**-4
0.0625
荒人说梦 2024-08-31 23:13:17

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

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

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

总体而言,忽略该功能似乎是唯一明智的选择。程序员可以使用带有所有可用错误报告的浮点版本。

That's actually an interesting question. One argument I haven't found in the discussion is the simple lack of obvious return values for the arguments. Let's count the ways the hypthetical int pow_int(int, int) function could fail.

  1. Overflow
  2. Result undefined pow_int(0,0)
  3. Result can't be represented pow_int(2,-1)

The function has at least 2 failure modes. Integers can't represent these values, the behaviour of the function in these cases would need to be defined by the standard - and programmers would need to be aware of how exactly the function handles these cases.

Overall leaving the function out seems like the only sensible option. The programmer can use the floating point version with all the error reporting available instead.

甜心小果奶 2024-08-31 23:13:17

简短回答:

pow(x, n) 的特化(其中 n 是自然数)对于时间性能通常很有用。但是标准库的泛型 pow() 仍然可以很好地实现此目的(令人惊讶!),并且在标准 C 库中包含尽可能少的内容绝对至关重要,因此它可以尽可能地便携且易于实施。另一方面,这并不能阻止它出现在 C++ 标准库或 STL 中,我很确定没有人计划在某种嵌入式平台中使用它们。

现在,给出长答案。

在许多情况下,通过将 n 专门化为自然数,可以使 pow(x, 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赢了。 glibc pow() 花费了 12.0 用户秒,pown 花费了 7.4 用户秒,而 pown_l 仅花费了 6.5 用户秒。所以这并不奇怪。我们或多或少都期待着这一点。

然后,我让 x 为常量(我将其设置为 2.5),并将 n 从 0 到 19 循环一亿次。这一次,出乎意料的是,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_ln 较低时表现最佳,而 pownx 时表现最佳 很高。

因此,这里有三种不同的算法,每种算法在适当的情况下都能够比其他算法表现得更好。因此,最终,最有可能使用哪个版本取决于您计划如何使用 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_expectedn_expected 是在编译时决定的常量,以及可能的其他一些注意事项,一个称职的优化编译器会自动删除整个 pown_auto 函数调用,并将其替换为三种算法中的适当选择。 (现在,如果您确实要尝试使用这个,您可能需要稍微摆弄一下它,因为我并没有完全尝试编译我的内容上面已经写了;))

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

脚注:在时间性能测试中,我给了我的函数相对慷慨的优化标志(-s -O2),这些优化标志可能与用于编译 glibc 的可能相当,甚至更差。我的系统(archlinux),所以结果可能是公平的。为了进行更严格的测试,我必须自己编译 glibc,但我确实不想这样做。我曾经使用 Gentoo,所以我记得需要多长时间,即使任务是自动化的。结果对我来说已经足够决定性的(或者更确切地说是不确定的)。当然,欢迎您自己做这件事。

奖励回合:如果需要精确的整数输出(这确实发生了),则对所有整数的 pow(x, n) 特化是工具。考虑为具有 p^N 元素的 N 维数组分配内存。即使 p^N 减少 1 也会导致可能随机发生的段错误。

Short answer:

A specialisation of pow(x, n) to where n is a natural number is often useful for time performance. But the standard library's generic pow() still works pretty (surprisingly!) well for this purpose and it is absolutely critical to include as little as possible in the standard C library so it can be made as portable and as easy to implement as possible. On the other hand, that doesn't stop it at all from being in the C++ standard library or the STL, which I'm pretty sure nobody is planning on using in some kind of embedded platform.

Now, for the long answer.

pow(x, n) can be made much faster in many cases by specialising n to a natural number. I have had to use my own implementation of this function for almost every program I write (but I write a lot of mathematical programs in C). The specialised operation can be done in O(log(n)) time, but when n is small, a simpler linear version can be faster. Here are implementations of both:


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

(I left x and the return value as doubles because the result of pow(double x, unsigned n) will fit in a double about as often as pow(double, double) will.)

(Yes, pown is recursive, but breaking the stack is absolutely impossible since the maximum stack size will roughly equal log_2(n) and n is an integer. If n is a 64-bit integer, that gives you a maximum stack size of about 64. No hardware has such extreme memory limitations, except for some dodgy PICs with hardware stacks that only go 3 to 8 function calls deep.)

As for performance, you'll be surprised by what a garden variety pow(double, double) is capable of. I tested a hundred million iterations on my 5-year-old IBM Thinkpad with x equal to the iteration number and n equal to 10. In this scenario, pown_l won. glibc pow() took 12.0 user seconds, pown took 7.4 user seconds, and pown_l took only 6.5 user seconds. So that's not too surprising. We were more or less expecting this.

Then, I let x be constant (I set it to 2.5), and I looped n from 0 to 19 a hundred million times. This time, quite unexpectedly, glibc pow won, and by a landslide! It took only 2.0 user seconds. My pown took 9.6 seconds, and pown_l took 12.2 seconds. What happened here? I did another test to find out.

I did the same thing as above only with x equal to a million. This time, pown won at 9.6s. pown_l took 12.2s and glibc pow took 16.3s. Now, it's clear! glibc pow performs better than the three when x is low, but worst when x is high. When x is high, pown_l performs best when n is low, and pown performs best when x is high.

So here are three different algorithms, each capable of performing better than the others under the right circumstances. So, ultimately, which to use most likely depends on how you're planning on using pow, but using the right version is worth it, and having all of the versions is nice. In fact, you could even automate the choice of algorithm with a function like this:

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_expected and n_expected are constants decided at compile time, along with possibly some other caveats, an optimising compiler worth its salt will automatically remove the entire pown_auto function call and replace it with the appropriate choice of the three algorithms. (Now, if you are actually going to attempt to use this, you'll probably have to toy with it a little, because I didn't exactly try compiling what I'd written above. ;))

On the other hand, glibc pow does work and glibc is big enough already. The C standard is supposed to be portable, including to various embedded devices (in fact embedded developers everywhere generally agree that glibc is already too big for them), and it can't be portable if for every simple math function it needs to include every alternative algorithm that might be of use. So, that's why it isn't in the C standard.

footnote: In the time performance testing, I gave my functions relatively generous optimisation flags (-s -O2) that are likely to be comparable to, if not worse than, what was likely used to compile glibc on my system (archlinux), so the results are probably fair. For a more rigorous test, I'd have to compile glibc myself and I reeeally don't feel like doing that. I used to use Gentoo, so I remember how long it takes, even when the task is automated. The results are conclusive (or rather inconclusive) enough for me. You're of course welcome to do this yourself.

Bonus round: A specialisation of pow(x, n) to all integers is instrumental if an exact integer output is required, which does happen. Consider allocating memory for an N-dimensional array with p^N elements. Getting p^N off even by one will result in a possibly randomly occurring segfault.

暮倦 2024-08-31 23:13:17

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

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

One reason for C++ to not have additional overloads is to be compatible with C.

C++98 has functions like double pow(double, int), but these have been removed in C++11 with the argument that C99 didn't include them.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Getting a slightly more accurate result also means getting a slightly different result.

对你而言 2024-08-31 23:13:17

这是一个非常简单的 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 倍的内存更新

Here's a really simple O(log(n)) implementation of pow() that works for any numeric types, including integers:

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

It's better than enigmaticPhysicist's O(log(n)) implementation because it doesn't use recursion.

It's also almost always faster than his linear implementation (as long as p > ~3) because:

  • it doesn't require any extra memory
  • it only does ~1.5x more operations per loop
  • it only does ~1.25x more memory updates per loop
夜光 2024-08-31 23:13:17

世界在不断发展,编程语言也在不断发展。 C 十进制 TR 的第四部分 1 向 添加了更多函数。此问题可能对这些函数的两个系列感兴趣:

  • pown 函数,它采用浮点数和 intmax_t 指数。
  • powr 函数,采用两个浮点数(xy)并计算 x 的幂 < code>y 的公式为 exp(y*log(x))

看来标准制定者最终认为这些功能足够有用,可以集成到标准库中。然而,理性的是这些函数是由 ISO/IEC/IEEE 60559:2011< 推荐的/strong> 二进制和十进制浮点数的标准。我不能肯定地说 C89 时遵循的“标准”是什么,但 的未来演变可能会受到 未来演变的严重影响>ISO/IEC/IEEE 60559 标准。

请注意,小数 TR 的第四部分不会包含在 C2x(下一个主要 C 修订版)中,并且可能稍后作为可选功能包含在内。据我所知,没有任何意图将 TR 的这一部分包含在未来的 C++ 修订版中。


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

The World is constantly evolving and so are the programming languages. The fourth part of the C decimal TR¹ adds some more functions to <math.h>. Two families of these functions may be of interest for this question:

  • The pown functions, that takes a floating point number and an intmax_t exponent.
  • The powr functions, that takes two floating points numbers (x and y) and compute x to the power y with the formula exp(y*log(x)).

It seems that the standard guys eventually deemed these features useful enough to be integrated in the standard library. However, the rational is that these functions are recommended by the ISO/IEC/IEEE 60559:2011 standard for binary and decimal floating point numbers. I can't say for sure what "standard" was followed at the time of C89, but the future evolutions of <math.h> will probably be heavily influenced by the future evolutions of the ISO/IEC/IEEE 60559 standard.

Note that the fourth part of the decimal TR won't be included in C2x (the next major C revision), and will probably be included later as an optional feature. There hasn't been any intent I know of to include this part of the TR in a future C++ revision.


¹ You can find some work-in-progress documentation here.

偏爱自由 2024-08-31 23:13:17

也许是因为处理器的 ALU 没有为整数实现这样的函数,但有这样的 FPU 指令(正如 Stephen 指出的,它实际上是一对)。因此,实际上,转换为 double、使用 double 调用 pow、然后测试溢出并转换回来比使用整数运算实现它更快。

(一方面,对数降低了乘法的幂,但是对于大多数输入来说,整数的对数会损失很多精度)

Stephen 是对的,在现代处理器上这不再是正确的,但是选择数学函数时的 C 标准(C++ 只是使用了 C 函数)现在是什么,20 岁?

Perhaps because the processor's ALU didn't implement such a function for integers, but there is such an FPU instruction (as Stephen points out, it's actually a pair). So it was actually faster to cast to double, call pow with doubles, then test for overflow and cast back, than to implement it using integer arithmetic.

(for one thing, logarithms reduce powers to multiplication, but logarithms of integers lose a lot of accuracy for most inputs)

Stephen is right that on modern processors this is no longer true, but the C standard when the math functions were selected (C++ just used the C functions) is now what, 20 years old?

满天都是小星星 2024-08-31 23:13:17

事实上,确实如此。

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


编辑:纯粹主义者可能会认为这是不正确的,因为实际上使用了“升级”类型。无论怎样,我们都会在 int 参数上得到正确的 int 结果,或者得到错误。

As a matter of fact, it does.

Since C++11 there is a templated implementation of pow(int, int) --- and even more general cases, see (7) in
http://en.cppreference.com/w/cpp/numeric/math/pow


EDIT: purists may argue this is not correct, as there is actually "promoted" typing used. One way or another, one gets a correct int result, or an error, on int parameters.

孤独患者 2024-08-31 23:13:17

一个非常简单的原因:

5^-2 = 1/25

STL 库中的所有内容都基于可以想象到的最准确、最强大的内容。当然,int 会返回到零(从 1/25),但这将是一个不准确的答案。

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

A very simple reason:

5^-2 = 1/25

Everything in the STL library is based on the most accurate, robust stuff imaginable. Sure, the int would return to a zero (from 1/25) but this would be an inaccurate answer.

I agree, it's weird in some cases.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文