In a previous post I've criticized a careless, effortless but highly-valued post pretending to contain an algorithm, written in C++, to compute ab, when indeed it computes the wrong results, since it implements (likely wrongly) a wrong algorithm, hence teaching something wrong.
I've written the algorithm and analysed his code a bit, but I haven't given an actual implementation. Here it is in this post.
First of all, when you provide a functionality, e.g. a piece of code which compute ab, you put it into a function: it's its natural “home”. Then you can use the function to show it works. This is testing. I'll show you later; now, let's implement our pow function.
Beware! Achtung!
Since C++11 was released, I use at least C++11 (unless there's legacy code to be maintained).
Let's start…
Let's start with the prototype.
double my_pow(double a, int b);
Exactly. Our power of function can compute ab when a is a real number (a double in C/C++), but b must be integer. Real exponents are a different story and we leave them alone.
However, even if a were an integer, the result must still be a double, because when b is negative in fact we have a fraction, 1/a|b|, so the return value of the function must be a double.
Implementation:
#include <limits>
double my_pow(double a, int b)
{
double result = 1.0;
bool invert = false;
if (b < 0) {
invert = true;
b = -b;
}
for (int n = 0; n < b; ++n) {
result = result * a;
}
if (invert) {
if (result != 0) {
result = 1.0/result;
} else {
result = std::numeric_limits<double>::infinity();
}
}
return result;
}
You can see that when I must invert result, but this is 0, I put into result a special value, which is the hugest value a double can represent, and can be read a infinity — of course it isn't actually infinity, though. This is provided by the C++ standard. Another option is to throw an exception (then the include stdexcept is needed):
if (invert) {
if (result != 0) {
result = 1.0/result;
} else {
throw std::overflow_error("division by zero");
}
}
This code throws the standard exception overflow error, with text “division by zero”, because a divide-by-zero exception doesn't exist, and when you do 1/0, you can say it gives infinity, which is a value which cannot fit inside a double, hence the overflow choice.
The exception must then be handled… I prefer the other solution, where result becomes a special value representing “infinity” for a double. In real use cases the choice depends on the application: is it ok the computation goes on with such a “huge” value, or should be thrown an exception because there's a problem?
Testing
We have our function and we want to know if it gives correct results. I hate to check things by hand: let's the computer do it for us!
In order to do so, we must use the standard pow function and compare results. Comparing floating point numbers is tricky. Here I am happy if my poor my_pow() is able to compute a value which is close enough to the value given by pow. How close? We can tune our program changing a constant. In this example the result of my_pow() must be between r - 0.0001 and r + 0.0001, where r is the result given by pow().
The function to check if the values are close enough:
bool close_enough(double a1, double a2, double threshold)
{
return a1 > (a2 - threshold) && a1 < (a2 + threshold);
}
I want also a function which, given the inputs, computes ab with my_pow(), then with pow() and at last it outputs the verdict, handling also a little bit of formatting, just to have a “nice” output.
Here it is:
void test_pow(double a, int b)
{
constexpr double thrs = 0.0001;
constexpr int w = 10;
double r1 = my_pow(a, b);
double r2 = pow(a, b);
std::cout << std::setw(w) << a
<< " ** "
<< std::setw(w) << std::left << b
<< " = "
<< std::right << std::setw(w)
<< std::setprecision(4) << r1
<< " ... "
<< (close_enough(r1, r2, thrs) ? "ok!" : "NO.")
<< std::endl;
}
Now we are ready for the main(). Let's test the input values I've used in my previous post. This is a very boring main, …
int main()
{
test_pow(0, 0);
test_pow(1, 10);
test_pow(2, 10);
test_pow(2, -1);
test_pow(2, -2);
test_pow(2, -3);
test_pow(-2, 1);
test_pow(4, 1);
test_pow(-2, 2);
test_pow(-2, 3);
test_pow(-2, -1);
test_pow(-2, -2);
test_pow(-2, -3);
test_pow(10, -1);
test_pow(11, -1);
test_pow(12, -1);
test_pow(10, -2);
test_pow(12, -2);
test_pow(10, -3);
test_pow(100, -1);
test_pow(100, -2);
test_pow(100, -3);
test_pow(100, -4);
test_pow(-100, -4);
test_pow(1000, 1);
return 0;
}
Compiled and run, the output is:
0 ** 0 = 1 ... ok!
1 ** 10 = 1 ... ok!
2 ** 10 = 1024 ... ok!
2 ** -1 = 0.5 ... ok!
2 ** -2 = 0.25 ... ok!
2 ** -3 = 0.125 ... ok!
-2 ** 1 = -2 ... ok!
4 ** 1 = 4 ... ok!
-2 ** 2 = 4 ... ok!
-2 ** 3 = -8 ... ok!
-2 ** -1 = -0.5 ... ok!
-2 ** -2 = 0.25 ... ok!
-2 ** -3 = -0.125 ... ok!
10 ** -1 = 0.1 ... ok!
11 ** -1 = 0.09091 ... ok!
12 ** -1 = 0.08333 ... ok!
10 ** -2 = 0.01 ... ok!
12 ** -2 = 0.006944 ... ok!
10 ** -3 = 0.001 ... ok!
100 ** -1 = 0.01 ... ok!
100 ** -2 = 0.0001 ... ok!
100 ** -3 = 1e-06 ... ok!
100 ** -4 = 1e-08 ... ok!
-100 ** -4 = 1e-08 ... ok!
1000 ** 1 = 1000 ... ok!
Let's try with 0 and a negative exponent: we add the line
test_pow(0, -2);
and the last line of the output now is:
0 ** -2 = inf ... NO.
This doesn't mean that pow(0, -2) is something different from inf. The fact is that the special double “huge” value has the property that it can only match exactly. If you look at close_enough(), you see we have excluded the lower and upper bound (< and > instead of <= and >=). But the math of inf is this:
inf + a_finite_value = inf
inf - a_finite_value = inf
Therefore close_enough() return false (inf > inf && inf < inf is clearly false). If you change the code including the extremes of the range, like this:
bool close_enough(double a1, double a2, double threshold)
{
return a1 >= (a2 - threshold) && a1 <= (a2 + threshold);
}
The the last line of the output will be:
0 ** -2 = inf ... ok!
Of course if we did the choice of throwing an exception, the last line wouldn't appear at all. Glad to have chosen the same way pow() does! (Which isn't, indeed, by chance, also considering that it's a plain C function, and C hasn't exceptions, thus…)
The whole code, with a small modification to print the result of pow() in case it doesn't match with my_pow(), can be found in this pastebin and also in this hastebin, whatever you prefer — hastebin is without ads and all the noise pastebin has.
More about exponentiation
I wrote an article about it in the past: Exponentiation (positive and negative, integer and rational exponents).
Written in C++11
(Mainly because of constexpr)
Edited in Emacs, compiled with GCC 6.3.0
source and source; done by Daniel Lundin
Thanks to the Free Software Foundation and GNU.
Sorry but your code and examples have errors.
First result variable is uninitialised and undefined in first example.
0**0 is undefined in maths.
O**-2 = 0
And your code doesn't check for overflows.
I've renamed r to result on the fly, forgot some, fixed in the final source but forgot to fix it back in the text, sorry. Check the given hastebin, which I've compiled and run actually, so it's fine.
Then, don't forget that this is not meant to be ready-for-production code, but an straightforward implementation of a simple algorithm, to contrast with the post I talk about here.
It's quite disputed (see e.g. here or well, just wikipedia).
But anyway, the result is coherent with what
pow()does: haven't you read the test part, how it callsmy_pow()and checks the result withpow()?What? Is it supposed to be a zero (0) or a (O)? What do you mean?
Think about how should it handle overflows, and ask yourself how the original
pow()does it and how the programmer calling the overflowingpow()should notice. The double just stick to the special value Inf, and this again is coherent with the result of the standard pow(). Therefore I don't get your point.I suppose you have a solid experience implementing correctly math functions in C/C++, so I look forward to read your suggestions about how to do the overflow checks and what to do inside the function once you spot the overflow.
Sorry but as you were correcting someone else's post (which is good) I thought that it was important to be accurate in yours.
You are right about the fact that 0**0 is controversial.
You could check for overflows condition in your loop:
if (a > (max_double / a))
But I agree that it's quite inneficient.
There might be some clever mathematical shortcut to check the above.
No, I'm no expert at math algorithm implementation. 😁
I accepted gladly the point about
r/resultsince it is a matter of fact. But I had doubts about your other remarks. Now you admit they aren't genuine but just childish aimless behavior.And yours is also just pointless and empty pedantry:
pow();Infvalue, and then anyway there's no way to signal the overflow, except by throwing an exception (in C++ — but guess whatcmath'spow()does…); bonus third reason, the behavior is consistent withpow().Now I must stress that I am not “correcting someone else's post” for a matter of accuracy, nor I've been in the post pointlessly pedant about something that it's good (but not just as good as I'd like it to be), or that it is just not bad.
No, the reasons for my post are different. Let me summarize few points here, though it's a waste of my time because your comment wasn't genuine but driven by an irrational kind of “spite”.
I sincerely believe that showing those problems can improve the quality of the contents on steemit, and that that kind of posts should be swept away, not implicitly defended trying to give me “the same medicine” — which is not, in case it isn't clear yet. They are “toxic” posts.
And I want to stress another point. Let us suppose it is a genuine post and not just a “fraud” to get money. I am not judging a poem, or an opinion: code can be objectively judged at least by one criterion, which is very simple: does the code do what you say it does?
If it doesn't, and it fails blatantly, not subtly in few special cases hard to get, how come you publish it trying to sell it as something that supposedly is teaching how to compute ab without builtin functions?
And moreover it takes votes… It's a scam, and it shouldn't be defended, if not for the money at least because there's a risk a novice takes the code seriously and steemit is marked as a bad place for code and programming.
I thought I was pretty clear about my intention in my previous post but clearly you took offense.
I never sought to defend the post that you were correcting. If anything I said that was a good thing.
But clearly I thought that if you are going to provide corrections you need to be accurate.
I pointed at a mistake in your code. No need to be so sensitive. We all make mistakes.
As for the overflow I don't pretend to know the most efficient way to check for it but if your intention was to show an example implementation of pow, a quick check on the man page would show you that the library call would set errno to ERANGE in this scenario.
Anyway I certainly don't carry any hard feeling and this will be my last comment in this matter.
Wishing you all the best.