Why not use the Pow function for integers?
P.s. If anything, I'm talking about the C++ Pow function.
I have often come across recommendations like "do not use the Pow function". Why do many people make this recommendation?
void MyPow(int& a, int n)
{
int c = a;
for (size_t i = 0; i < n; i++)
a *= c;
}
Will this function be faster than the standard Pow? Or is this recommendation given due to the fact that Pow is implemented not binary, but linear? (this one, by the way, I don't know if it's binary or not)
2 answers
I have to apologize in advance - I want to talk about the applicability pow in general, , and not just for integer values.
Even if you want to raise to the power by multiplication, you do not need to do it so straightforwardly, there is a method of fast raising to the power of n at the speed of O (lg n).
Further, like any advice, it is advice, not dogma. This advice is perfectly valid, for example (and I always give it in such situations), when they start calculating something like pow(-1,n) (you can guess how to calculate it quickly and accurately?) or pow(x,2) - because even in the same VC++ pow with an integer degree in is implemented as (threw out the superfluous for understanding)
double pow(double _Xx, int _Yx) noexcept
{
if (_Yx == 2) return (_Xx * _Xx);
return pow(_Xx, static_cast<double>(_Yx));
}
So what's the point of constantly checking whether two is equal to two? :) For small power values, it may also turn out that the direct calculation is faster than the function call.
If you are hinting at a template implementation of the pow<int,int> type , then throwing out the unimportant for understanding, in VC++, it looks like this:
template<class _Ty1, class _Ty2,
class = enable_if_t<is_arithmetic_v<_Ty1> && is_arithmetic_v<_Ty2>>>
_Common_float_type_t<_Ty1, _Ty2> pow(const _Ty1 _Left, const _Ty2 _Right)
{ // bring mixed types to a common type
using _Common = _Common_float_type_t<_Ty1, _Ty2>;
return (pow(static_cast<_Common>(_Left), static_cast<_Common>(_Right)));
}
That is, it still reduces to the usual pow floating point. Which begins to perform a series of gestures to check arguments, etc., so that a simple replacement with exp(y*log(x)) works is slightly faster than (however, this difference significantly depends on the floating-point model used - in VC++ 2017, from almost equal at /fp:fast to a difference of 1.8 times at /fp:precise). By the way, I think (more precisely-I know :), see P. P. S.), if you apply even your linear the method of calculation - it will be ahead of the standard one to sufficiently large degree values.
The accuracy of exponentiation of an integer value also suffers, but this has already been discussed above.
In short, every tool is good when properly applied.
One more remark in connection with the last phrase - it also pisses me off when they start using pow to calculate some series of the type
When each member it is calculated by exponentiation, not multiplication by x, or when a polynomial is also calculated head-on, ignoring the Gorner scheme. Here, the use of pow is stupid, not because it is bad, but because here, the exponentiation of is not required at all!
P.S. And in general, in programming, as in many other fields of activity - in the same movie, there are a lot of examples - at first they begin to apply something thoughtlessly everywhere simply because they have learned to use it something. Then comes sobering up - it's obviously too much, maybe you should give up this opportunity altogether?.. And only then comes the understanding that everything is good in moderation and in its place :) But this is so, abstract reflections that do not relate to the specific question..
P. P. S. Couldn't stand it - I was interested, but in fact, when will it be faster to use pow than just linear multiplication? I sketched a small code, calculated it one-time, built it chart...
It turns out that somewhere up to 30 degrees is better to simply multiply than to count the exponent of the logarithm, and somewhere up to 50 - if you use pow. If you use fast exponentiation , then this curve is simply not visible on the graph, since its value over the entire range fluctuates around 0.25-0.3 ms..
There is an error in your pow implementation: it gives an incorrect answer for zero n (and for negative ones). Not to mention that it doesn't support fractional n.
The standard pow is faster, it runs in constant time (independent of n) , and can be implemented by multiple processor instructions pow(x,y)==exp( log(x)*y ). But! It converts numbers to double and back, which can lead to a loss of precision because 64-bit int-contains more significant digits than the mantissa in double.