Why Isn't 'Int Pow(Int Base, Int Exponent)' in the Standard C++ Libraries

Why isn't `int pow(int base, int exponent)` in the standard C++ libraries?

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 :-)

Why does std::pow of a float and int invoke this overload?

Since C++11, mixed argument pow has any integral argument cast to double. The return type of the mixed argument functions is always double except when one argument is long double then the result is long double.

[c.math]
In addition to the double versions of the math functions in , C++ adds float and long double overloaded versions of these functions, with the same semantics.
Moreover, there shall be additional overloads sufficient to ensure:
If any argument corresponding to a double parameter has type long double, then all arguments corresponding to double parameters are effectively cast to long double.
Otherwise, 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.
Otherwise, all arguments corresponding to double parameters are effectively cast to float.

So to sum up:

One argument long double >> long double
Both arguments float >> float
Otherwise >> double

error: ‘int pow(double, int)’ conflicts with a previous declaration int pow(double a, int n) {

I have no idea what the original reason for introducing the pow definitions in this code were (especially since they are guarded by implementation macros), but in conformant standard C++ the definition

int pow(double a, int n) {
    return pow(a, (double)n);
}

in global namespace is going to cause trouble. Depending on the standard version, whether <math.h> and/or <cmath> are included directly or indirectly and dependent on the unspecified standard library implementation details, this may or may not be a valid definition.

The C++ standard library already offers an overload with signature pow(double, int) or potentially a template pow accepting these arguments and in the former case, the definition in user code will be an invalid redefinition if this overload/template is placed into the global namespace (including math.h always does that, including <cmath> may do that).

The second overload

int pow(int a, int n) {
    // versions for float/double are defined in stdlib.
    int r = a;
    for (int i = 1; i < n; i++) r *= a;
    return r;
}

will cause similar issues, but only since C++11 (this overload did not exist before that and it has different semantics than the version here in C++11 and up).

Therefore this is simply a bug in the code. As workaround I noticed that (for some reason that is not clear to me) GCC versions 5.x and below do not seem to error on the definition, even though I tried to make sure that they would. Since 6.1 the overload always causes an error together with #include<math.h> and -std=c++89/-std=gnu++89.

You may also want to try compiling against -std=c++11 or -std=gnu++11, because since C++11 implementations are allowed to implement the pow overloads as template functions, in which case no redefinition error would occur. (I think that was not allowed before C++11.) This seems to be the case with GCC in my testing.

C's pow function refuses to work with variable exponent

It's a very interesting behavior, and a good learning example.

To solve your problem, add

-lm

to your gcc command line (provided you're using gcc). This tells the compiler to link against the math library.

What seems to be going on, is that if you're using

pow(2.0, 3);

the compiler realizes this expression evaluates to a constant, and does mere substitution.

Thus, no library function has to be called.

Why isn't there Math.Pow that takes an int as the exponent?

Because you'd just need to convert it back into a float to multiply it against the logarithm of the base.

n^m = e^{m × ln n}

How to force pow(float, int) to return float

You could easily write your own fpow using exponentiation by squaring.

float my_fpow(float base, unsigned exp)
{
    float result = 1.f;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

Boring part:

This algorithm gives the best accuracy, that can be archived with float type when |base| > 1

Proof:

Let we want to calculate pow(a, n) where a is base and n is exponent.

Let's define b₁=a¹, b₂=a², b₃=a⁴, b₄=a⁸,and so on.

Then aⁿ is a product over all such b_i where i_th bit is set in n.

So we have ordered set B={b_k1,b_k1,...,b_kn} and for any j the bit k_j is set in n.

The following obvious algorithm A can be used for rounding error minimization:

If B contains single element, then it is result
Pick two elements p and q from B with minimal modulo
Remove them from B
Calculate product s = p*q and put it to B
Go to the first step

Now, lets prove that elements in B could be just multiplied from left to right without loosing accuracy. It comes form the fact, that:

b_j > b₁*b₂*...*b_j-1

because b_j=b_j-1*b_j-1=b_j-1*b_j-2*b_j-2=...=b_j-1*b_j-2*...*b₁*b₁

Since, b₁ = a¹ = a and its modulo more than one then:

b_j > b₁*b₂*...*b_j-1

Hence we may conclude, that during multiplication from left to right the accumulator variable is less than any element from B.

Then, expression result *= base; (except the very first iteration, for sure) does multiplication of two minimal numbers from B, so the rounding error is minimal. So, the code employs algorithm A.

why math.h have pow() return double and not int

Anol's answer is very on-point and I believe is the most correct assessment as to why int pow() is not a part of the standard library, however I would like to amend it with another possibility.

The most useful aspect of the pow function is the ability to correctly (at least as far as floating point arithmetic is concerned) perform exponentiation to non-integer powers. This type of behavior is non-trivial to implement using integer math, let alone floating point math. Rather than asking library implementors to write both an integer exponentiation routine and a floating point exponentiation routine, they decided to ask for the more useful of the two. It also helps that the x87 instruction set, as well as many other FPU instruction sets, provides built-in floating point exponentiation instructions to make the implementation on the software side trivial.

C also doesn't have any notion of exceptions, and no language-level global state that could expose things like CPU flags. This would make overflow detection in an int pow() implementation difficult to provide. In the case of double pow(), it can just return a non-signalling NaN or Infinity in the case of exceptional circumstances. However there is no notion of NaN or Infinity in the integer world.

In the case of an exception, the program could do one of the following:

Overflow Silently
Return INT_MIN or INT_MAX
Change an integer whose pointer was provided to the function by the caller
Change some global state like errno
Emit a SIGFPE
Provide a sister function int pow_overflow_check() that can be used to boilerplate the call

None of these are desirable. The first two options would lead to hard-to-diagnose logic errors in possibly unrelated areas of a program. The third one would provide an annoying and cumbersome barrier to the use of the function. The fourth one would ruin any sort of reentrancy guarantee. The fifth option would make the entire program grind to a halt. The sixth option would work well, but would also bloat the standard more, and make the function more cumbersome to use like in the third option.

Further, just like others have stated, exponentiation to an integer power, especially if the base is 2, is trivial to implement. A first year compsci student with a basic understanding of math should be able to formulate a correct implementation that could suit most use cases.

The original C language was aimed squarely at assembly programmers, and this is one of the symptoms of that. A very common theme in the language spec is that the language library should only provide things that are either impossible to implement in-language in a portable manner, or extremely non-trivial to implement purely in-language, especially when there are commonly available CPU/FPU instructions that can do it for you.

The most efficient way to implement an integer based power function pow(int, int)

Exponentiation by squaring.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography.

Why Isn't 'Int Pow(Int Base, Int Exponent)' in the Standard C++ Libraries