5

In maths, addition (of real numbers) is commutative and associative, ie. for all numbers x, y and z

x + y = y + x (commutativity)

and

x + (y + z) = (x + y) + z (associativity)

Multiplication of real numbers is also commutative and associative. But is this true for ints and floats in .NET? Counterexamples welcome.

Edit: Background is we've recently parallelised an algorithm and now its results are no longer consistent between repeats. I speculate this might be due to the atomic calculations returning (and being merged) in non-deterministic order. In which case, the inconsistency could be fixed by a smarter (but slower) merge algorithm (that sorts the results before merging). I'd like to know what assumptions it can make about .NET arithmetic.

Colonel Panic
  • 132,665
  • 89
  • 401
  • 465
  • 2
    DV seems a little extreme, but exactly what problem are you trying to solve? – spender Oct 14 '13 at 11:30
  • 3
    By adhering to 'I don't know what I'm talking about, but I'll voice my opinion on the subject regardless', I'd say that it holds true for integers, but not necessarily for floats. At least that's my gut feeling regarding floating point arithmetic. – Patryk Ćwiek Oct 14 '13 at 11:31
  • In any language, the basic math rules are respected. Sure for ints, commutativity, associativity, and also permutability for addition should be respected for floats in the limit of the numerical rounding precision. – jacouh Oct 14 '13 at 11:34
  • 1
    Related (but not a dupe) [In C# integer arithmetic, does a/b/c always equal a/(b*c)?](http://stackoverflow.com/q/16837854/73226) – Martin Smith Oct 14 '13 at 11:38
  • 1
    Also, your comment about parallelised (I'm assuming means multi-threaded) may indicate a completely different problem. Perhaps you have a race condition or non-atomic operations that need better locking. – Chris Sinclair Oct 14 '13 at 11:46
  • related [Associative Property on floating point number additions](https://stackoverflow.com/q/47825436/995714), [Is Floating point addition and multiplication associative?](https://stackoverflow.com/q/10371857/995714) – phuclv Jul 17 '18 at 09:14

4 Answers4

11

Assuming no unchecked overflows occur, .NET's integer addition and multiplication (int, long, etc.) is commutative and associative, like the real numbers in math. Floating point arithmetic (float and double) is commutative, but not always precisely associative, due to the limits of precision. From Wikipedia (with an example in the article):

While floating-point addition and multiplication are both commutative (a + b = b + a and a×b = b×a), they are not necessarily associative. That is, (a + b) + c is not necessarily equal to a + (b + c).

Here's an example:

a: 0.825402526103613
b: 0.909231618470155
c: 0.654626872695343
(a*b)*c: 0.491285733573819
a*(b*c): 0.49128573357382

There are some examples where the results appear the same when turned into a string, but are different ((a*b)*c != a*(b*c) is true, and (a*b)*c - a*(b*c) returns a small value, not 0).

a: 0.613781429181705
b: 0.648859122604532
c: 0.795545351596337
(a*b)*c: 0.316832045751117
a*(b*c): 0.316832045751117
difference: 5.55111512312578E-17
Tim S.
  • 55,448
  • 7
  • 96
  • 122
  • 2
    Unchecked overflows actually don't break commutativity or associativity (for integers, floats are a different story). Checked overflows do, though. – harold Oct 14 '13 at 12:59
3

Yes for int, no for (unfortunate selections of) float (because of limited precision).

Thilo
  • 257,207
  • 101
  • 511
  • 656
  • Also, `int`s could have overflow checking. – millimoose Oct 14 '13 at 11:34
  • @millimoose: If overflows result in exceptions then, yes, that would break things. If they just "roll over" then order of application should not matter. – Thilo Oct 14 '13 at 11:36
  • In C# [both are possible](http://msdn.microsoft.com/en-us/library/khy08726.aspx), rolling over is the default IIRC. (Not particularly relevant to the OP of course but still.) – millimoose Oct 14 '13 at 13:04
1

In an unchecked context (the default), the presence of overflow is irrelevant to associativity and commutativity.

For example, take 0x7fffffff + 0x80000000 + 0xffffffff. The result is 0xfffffffe (aka -2) no matter how you parenthesise it. But (0x7fffffff + 0x80000000) + 0xffffffff doesn't overflow whereas 0x7fffffff + (0x80000000 + 0xffffffff) overflows twice. (in unsigned arithmetic, they would both overflow once)

This is also true in general. a + (b + c) = (a + b) + c in integers in C# (if unchecked) and Java. In C and C++, that's only guaranteed for unsigned integers, because signed overflow is undefined.

harold
  • 61,398
  • 6
  • 86
  • 164
0

In a parallelized reduction:

floats.AsParallel().Sum();

... you can expect different results each time. This is because the work is partitioned differently each time, which causes different rounding errors when adding numbers.

To minimize this problem, make sure reductions are done with double's, not with floats. If you want bitwise identical results, you should not use TPL or PLINQ, and roll your own parallel computation.

Please note that in C#, fp accuracy is not guaranteed as strictly as in C++. Read Eric's answer to this SO question.

Community
  • 1
  • 1