Thursday, June 25, 2015

Non-associative property of floating-point operations

As you may be motivated to know how come it is possible to have different values by prioritizing the addition operator according to my last post, I decided to write this post to show you the floating point operations does not necessarily have the associative property. Before dive into the details, let's start with an example,

print(M, digits=20)
print(N, digits=20)
More probably you will see the following results on your screen,

[1] 0.60000000000000008882
[1] 0.5999999999999999778

Surprisingly, not only the floating point operations does not necessarily have the associative property, but also the commutative property does not hold either! It is better to demonstrate this by the following example,

print(M, digits=20)
print(N, digits=20)

The following result was produced in R,
[1] 30.000000000000003553
[1] 30

In mathematics, the associative property is a property of some binary operations. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs.

Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value. 
Wikipedia definition

Despite, the addition operator should meet the associative property theoretically for all real numbers, floating-point operations, as defined in the IEEE-754 standard, are not associative numerically.

More specifically, on massively multi-threaded systems, the non-deterministic nature of how floating-point operations are performed inside the machine, such as the intermediate values that have to be rounded or truncated to fit in the available precision leads to non-deterministic numerical error propagation.

Floating point arithmetic is known to be non-associative since the limited precision of the representation requires intermediate values be rounded. The IEEE-754 provides uniform semantics for operations across a wide range of implementations. The standard de fines correct behavior for all operations, as well as any necessary rounding.

So if you want to implement your algorithm, or reimplement an existing algorithm and port it in another programming language, be careful about this issue.