HP PRIME not raising overflow/underflow may cause critical errors

[robve]

(03-20-2021 04:48 PM)Albert Chan Wrote:  You might want to re-read Han's post again.
The quote actually support your claim that 0^0 is indeterminate.

I was primarily responding to the notion of "context" in the post and its relationship to the (non-)constraints on the expression that demonstrates indeterminism.

(03-20-2021 04:48 PM)Albert Chan Wrote:  n = exp(ln(n)/ln(x)*ln(x)) = x^(ln(n)/ln(x))

Taking the limit for any x, we get n back.

x->0: 0^(ln(n)/∞) = 0^0 = n
x->1: 1^(ln(n)/0) = 1^∞ = n

Sure, but taking x to the limit close to 0 is not the same as hitting 0.

With respect to the "power operator" X^Y, I find that there are some fascinating historical anecdotes to implementations in programming languages. If you take programming languages as "context" rather than universal truth then yes, sometimes we get 0^0=1.

Let's start by taking an example in which the power operator does not work, but why? On some the earliest Basic machines, the following code never printed "nine":

X=3
IF X^2=9 THEN PRINT "nine"

Take a close look. Why would "nine" not be printed if 3^2 is clearly 9.

The user manual of these early machines, like the TRS-80 PC-2, warned about the accuracy of the power operator/exponentiation. As we all know, the reason is that the power operator is internally implemented with EXP and LOG:

X^Y = EXP(Y*LOG(X))

EXP and LOG are accurate only up to (but not necessarily including) the last digit of the mantissa, because these functions are typically implemented using their Taylor series expansions. Therefore 3^2 does not compute 9 exactly.

Right away we also realize that X cannot be zero or negative. Allowing X to be non-positive requires adding some conditions and additional code, which is non-trivial, e.g. (-27)^(1/3)=-3 but (-2)^(1/2) is complex.

The engineers of the early home computers had very little ROM space to work with, so any additional code should be kept very small. One simple adddition to improve the speed and accuracy is to use repeated multiplication for a small range of Y, which is faster than EXP and LOG, (or even better, use Exponentiation by Squaring, aka. the "Indian power algorithm", but with lots more code):

if (Y >= 0 && Y <= SOME_MAX && Y == (int)Y) {
  result = 1;
  while (Y-- > 0)
    result *= X
  return result;
}
if (X > 0)
  return exp(Y*log(X));
ERROR!

Note that if Y==0 the result=1 is returned for any X. Therefore, I can imagine that hilarity ensues among mathematicians. However, all that the engineers did is to follow the software engineering requirements specification, which must have been something like this:

implement X^Y for the valid range of real values X and Y

The valid range of exponentiation excludes (X,Y)=(0,0). Therefore, they will argue that the implementation is correct. It is indeed correct as long as programmers do not use 0^0 and then rely somehow on the result being 1.

In similar vein, let's implement factorial N! for integer N:

k = N;
r = 1;
while (k > 0) {
  r *= k;
  k -= 1;
}
return r;

Without checking the range of the factorial function, (-1)! gives 1 which is not correct. It is a "feature" (ahem, a bug) of our program. It expects a valid range for the factorial.

In Axiomatic Semantics of program correctness proofs, we can state this formally with a precondition to the algorithm:

PRE: N >= 0
POST: r = N!

We can then prove the correctness of our algorithm, using the loop invariant \( I \equiv (r\,k! = N! \wedge k \ge 0) \):


\( \{ N\ge 0 \} \)
k = N;
\( \{ k! = N! \wedge k\ge 0 \} \)
r = 1;
\( \{ r\,k! = N! \wedge k\ge 0 \} \)
while (k > 0) {
  \( \{ r\,k! = N! \wedge k\ge 0 \wedge k>0 \} \Rightarrow \{ r\,k\,(k-1)! = N! \wedge k-1 \ge 0 \} \)
  r *= k;
  \( \{ r\,(k-1)! = N! \wedge k-1\ge 0 \} \)
  k -= 1;
  \( \{ r\,k! = N! \wedge k\ge 0 \} \)
}
\( \{ r\,k! = N! \wedge k\ge 0 \wedge k\le 0 \} \Rightarrow \{ r = N! \wedge k=0 \} \Rightarrow \{ r = N! \} \)
return r;

Our program works!

But mind the precondition, please! Otherwise, expect undefined behavior.

- Rob