Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Floating Point Monotonic Property

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?

like image 814
Danish Ahmed Avatar asked Aug 12 '17 15:08

Danish Ahmed


1 Answers

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.

like image 187
Kamajii Avatar answered Oct 22 '22 23:10

Kamajii