Floating Point Monotonic Property

Question

I was reading a book (CSAPP) . In the book it is written that-

floating point addition satisfies the following monotonicity property :
if a>=b then (x + a) >= (x+b) for any value a,b and x other than NaN. This property of real (and integer) addition is not obeyed by unsigned or two's complement addition.

How floating point obeys it?
Why unsigned or two's complement addition doesn't obeys it?

@PeterJ it doesn't hold under wrapping, eg `1 >= 0` but `1 + UINT_MAX < 0 + UINT_MAX` — harold, Aug 12 '17 at 16:19
Overflow can happen in floating point operations too. You can create a value larger than the largest magnitude value (which is +/- 1.11111111111111111111111 x 2^128 in IEEE 754 single precision). Values larger than that might be rounded to infinity, which may not be what you want it to do.So floating point doesnt wraps.... — Danish Ahmed, Aug 12 '17 at 16:26
https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/underflow.html — Danish Ahmed, Aug 12 '17 at 16:36

Kamajii · Answer 1 · 2017-08-13T04:02:30.197

8

Unsigned integers in C basically form a ring, i.e. they eventually wrap. For example, continuously adding 1 to an unsigned integer will continuously increase it until it wraps to zero, which means adding one yields a result at least less than one, so monotonicity is not satisfied.

Signed integers do overflow which is more complicated but in C it also is undefined behaviour, so we should exclude that.

For floating point numbers in C, according to IEEE745, the addition of two positive numbers (which implies none of them is NaN as NaN is not known to be positive or negative) yields a result greater or equal than the the larger of the two addends: Either by forming a result that indeed is larger, or by yielding one of the addends because the other one gets absorbed, or by yielding infinity. The important point is to note that the addition satisfies monotonicity but not necessarily strict monotonicity.

edited Aug 13 '17 at 04:02

answered Aug 12 '17 at 16:04

Kamajii

1,826
9
21

It's monotonous of me to point out that it is monotonicity and not monotony. – Jonathan Leffler Aug 12 '17 at 16:10
Unsigned wrap not overflow. – Tony Tannous Aug 12 '17 at 16:10
I'm not a native speaker, my dictionary seems to list the translation for [DE]Monotonie as [EN]monotony[also math] as well as [EN]monotonicity[math]. I'll fix it. – Kamajii Aug 12 '17 at 16:12
Indeed. For example, x86 FLAGS register contains an OVERFLOW flag for signed overflows and a CARRY flag that catches on the unsigned wrap. – Kamajii Aug 12 '17 at 16:21
@Kamajii the x86 flags are not quite like that. The processor has no idea of the *context*, i.e. whether the values are signed or unsigned, but sets the flags for various conditions, and the programmer (or compiler) then chooses which flag testing instructions to use. – Weather Vane Aug 12 '17 at 16:29
1

Did you really mean "the addition of two positive numbers (which implies none of them is NaN as NaN is not known to be positive or negative) yields a result greater or equal than the sum of the two numbers"? I would have said "than the larger of the two numbers". – Patricia Shanahan Aug 12 '17 at 18:59
@Vane of course, but it shows that also in hardware there is a notion of the different terminology with _overflow_ and _wrap_. The context you're referring to is established e.g. by the compiler choosing to emit instructions for signed arithmetic or for unsigned arithmetic. – Kamajii Aug 13 '17 at 03:58
1

@PatriciaShanahan You're right. Clarified it, thanks! – Kamajii Aug 13 '17 at 04:01
Great answer. I think that's exactly what the book wants to tell. – Rick Dec 11 '20 at 17:44

Floating Point Monotonic Property

1 Answers1