Does floating point sqrt() function guarantee order relation

Question

given two floating point number x and y, suppose all floating point arithmetic conforming the IEEE754 standard, and a certain implementation of square root function sqrt(),

1. if x < y, is it true that sqrt(x) <= sqrt(y) must hold?
2. if sqrt(x) < sqrt(y), is it true that x <= y must hold?

Let a, b are two (precise) real number, and x = op(a), y = op(b), where op() denotes rounding a real number to its floating point representation. Then the following question: (* means floating point multiplication)

3. if a< b, is it true that sqrt(x) <= sqrt(y) must hold?
4. if sqrt(x)*sqrt(x) < sqrt(y)*sqrt(y), is it true that a <= b must hold.

If to some or all of the above, the answer is NO, then

• Do you know any implementation of sqrt() that guarantees 1, and 2.
• Given a certain rounding rule of truncating real numbers to floating point number, do you know any implementation of sqrt() that guarantees 3 and 4.

Horvitz

(1) would be very hard to achieve. sqrt is an operation that compresses the entire floating-point range into approximately half of that range, so you're bound to end up with some cases where x != y but sqrt(x) = sqrt(y). – Antonomasia

@MarkDickinson it is not only about range, but also resolution. When a floating number decreases by x to sqrt(x), resolution gets higher. – Horvitz

I think you're missing my point. Let S be the (finite!) set of all nonnegative finite floating-point numbers. Then sqrt maps from S to a strict subset of S. By the pigeonhole principle, that guarantees collisions. So your property (1) is impossible to achieve. For the same reason, (5) is impossible. So the last two questions are redundant: there cannot be an implementation of sqrt that satisfies (1), (2), (3) and (4) (because such an implementation already can't satisfy (1)). Similarly, there's no implementation satisfying (5), (6), (7) and (8). – Antonomasia

@MarkDickinson fair point. – Horvitz

@MarkDickinson Thanks very much for your helping clarifying the issue. I updated the question to better reflect my intention, that is, the possible order preserving of sqrt() operation. – Horvitz

Answer 1

IEEE 754 requires that conforming implementations provide square root and operations to convert from decimal to floating-point that are correctly rounded:

All conforming implementations of this standard shall provide the operations listed in this clause for all supported arithmetic formats, except as stated below. Each of the computational operations that return a numeric result specified by this standard shall be performed as if it first produced an intermediate result correct to infinite precision and with unbounded range, and then rounded that intermediate result, if necessary, to fit in the destination’s format…

The rounding mode used most commonly rounds to the nearest representable value. In case of a tie, it rounds to the value with the even low bit. A variant on that rounds ties away from zero.

Regarding question 1, suppose x < y but sqrt(x) > sqrt(y). Since square root is monotonic, then either sqrt(x) must be closer to the mathematical square root of y than sqrt(y) is or sqrt(y) must be closer to the mathematical square root of x than sqrt(x) is. So this would violate the rounding rules.

Other rounding rules rounding to the nearest number in a particular direction, one of toward +infinity, toward −infinity, or toward zero. Disordered sqrt results would violate those rounding rules too.

Note that many platforms will claim to use IEEE 754 format, but that does not mean they conform to IEEE 754 rules for operations, including square root and conversion from decimal to floating-point.

Question 2 is identical.

Question 3 holds with identical reasoning (applied twice: op is weakly monotonic, and sqrt is weakly monotonic) subject to the proviso that a and b are non-negative (or are so small in magnitude that x [or y] zero even though a [or b] is negative, due to rounding during the conversion). Otherwise, you could have a < b, but sqrt(x) <= sqrt(y) does not hold because x is a NaN, which is not less than or equal to anything.

Question 4 holds, now with weak monotonicity applied three times.

Hearn

Very clear exposition, many thanks. As to IEEE 754 conforming operations, are they supported at the CUP level, or at the compiler level, or they are implemented as separate libraries? – Horvitz

@JohnZ.Li: That is like asking whether the motion of a car is provided by the car, the drive train, or the engine. Everything has to work together to deliver a result. Modern general-purpose processors have basic arithmetic for floating-point built-in, and then it is up to compilers and software libraries to use it properly and to add support for additional functions, such as conversion from decimal to binary floating-point and sqrt if the hardware does not provide it. Some compilers do not conform to IEEE 754 even if the hardware does. – Hearn