4 ms·

(small number)+(small number)+ ... +(small number)+(much bigger number) may not give the same result as (much bigger number)+(small number)+(small number)+

by jonsen 8y ago

(small number)+(small number)+ ... +(small number)+(much bigger number) may not give the same result as (much bigger number)+(small number)+(small number)+ ... +(small number)

BeetleB 8y ago
You are confusing associativity with commutativity. The IEEE floating point standard guarantees commutativity for addition.
- jonsen 8y ago
  I think you are confusing commutativity in general with commutativity of binary operations.
  - BeetleB 8y ago
    We are now lost in a semantic discussion, as it is clear that all parties agree on the content, just not the terminology. In that spirit, I will disagree. In mathematics, commutativity is always about two operands. My textbook on floating point arithmetic[1] (probably the most famous one) states that addition and multiplication in floating point is commutative. They use examples similar to yours as an example of associativity being violated, and point out that commutativity is preserved. Putting FP aside: In mathematics, no one disputes that addition is commutative. Yet, they all agree that for infinite sums, if you rearrange the order of the terms, you can get different results. They don't say that addition is commutative only for finite sums. They say it is commutative for all addition, and that associativity is the property that fails for infinite sums. See the discussion here[2] for example: >The commutative property of addition is that a+b=b+a. Technically, it applies only to sums of two numbers! >Actually, commutivity does hold for infinite sums. Glossing over a few technicalities, commutivity says that you get the same answer whenever you interchange any two terms in a sum. Although I'll grant that when I look at some other answers in StackExchage, they do generalize to "repeated use of commutativity", and that if commutativity is applied a finite number of times, the sum is preserved, but not if applied an infinite number of times. The common refrain in both cases, though, is that commutativity applies only to two operands. [1] https://www.springer.com/us/book/9780817647056 https://www.springer.com/us/book/9780817647056 [2] https://math.stackexchange.com/questions/646665/why-does-commutativity-of-addition-fail-for-infinite-sums https://math.stackexchange.com/questions/646665/why-does-com...
    - jonsen 8y ago
      Take subtraction. The binary operator - is not commutative in the sense that a - b is not equal to b - a. But a - b commutes to - b + a. Any number of +or-with-operand can be arranged in any order. This is commutativity in general. See the start of Chapter 1 in Part 1: https://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp36404 https://onlinebooks.library.upenn.edu/webbin/book/lookupid?k... This is a very practical semantics of commutativity when programming. It’s unfortunately lost in most modern math expositions.
      - 0815test 8y ago
        But this relies on associativity - without associativity, you just don't have a consistent definition of e.g. (a + b + c + d) but only, e.g. + + + / \ / \ / \ + + a + a + / \ / \ / \ / \ a b c d + d b + / \ / \ b c c d and others as well. There would be practically no point in trying to find a definition of "commutative" for these structures that don't involve associativity.
        jonsen 8y ago
        -6-7-8 == -8-7-6 == -7-8-6 == ... How does this rely on associativity? It does not rely on parenthetical associativity. The operator is of course associated with an operand, but that’s not what is meant by associativity.
        dragonwriter 8y ago
        > How does this rely on associativity? It does not rely on parenthetical associativity. It's exactly the combination of commutivity of addition, associativity of addition, and equivalence of subtraction with addition of the additive inverse, that allows the general rearrangement of symbols you are discussing.
        deleted 8y ago
        [deleted]
dbaupp 8y ago
That is due to associativity. You're implicitly relying on a consistent left-to-right evaluation order, but the fundamental problem can be phrased as (using s for small and b for big): (((b + s) + s) + s) + s Can be different to b + (s + (s + (s + s))) This re-parenthesising is related to associativity, not commutivity.
- jonsen 8y ago
  Rearranging operands with their operations is commuting. Rearranging parentheses is associating. Yes, floating point operations are also not in general associative.
- jonsen 8y ago
  You're implicitly relying on a consistent left-to-right evaluation order, That’s standard, I think.
  - dbaupp 8y ago
    Indeed, it is standard, but eliding the parentheses doesn't mean they aren't implicitly there, and doesn't turn non-associativity into non-commutativity. Commutivity means that these are equal: (((b + s) + s) + s) + s == s + (s + (s + (s + b)))

by jonsen 8y ago

(small number)+(small number)+ ... +(small number)+(much bigger number) may not give the same result as (much bigger number)+(small number)+(small number)+ ... +(small number)

BeetleB 8y ago

You are confusing associativity with commutativity. The IEEE floating point standard guarantees commutativity for addition.

jonsen 8y ago
I think you are confusing commutativity in general with commutativity of binary operations.
- BeetleB 8y ago
  We are now lost in a semantic discussion, as it is clear that all parties agree on the content, just not the terminology. In that spirit, I will disagree. In mathematics, commutativity is always about two operands. My textbook on floating point arithmetic[1] (probably the most famous one) states that addition and multiplication in floating point is commutative. They use examples similar to yours as an example of associativity being violated, and point out that commutativity is preserved. Putting FP aside: In mathematics, no one disputes that addition is commutative. Yet, they all agree that for infinite sums, if you rearrange the order of the terms, you can get different results. They don't say that addition is commutative only for finite sums. They say it is commutative for all addition, and that associativity is the property that fails for infinite sums. See the discussion here[2] for example: >The commutative property of addition is that a+b=b+a. Technically, it applies only to sums of two numbers! >Actually, commutivity does hold for infinite sums. Glossing over a few technicalities, commutivity says that you get the same answer whenever you interchange any two terms in a sum. Although I'll grant that when I look at some other answers in StackExchage, they do generalize to "repeated use of commutativity", and that if commutativity is applied a finite number of times, the sum is preserved, but not if applied an infinite number of times. The common refrain in both cases, though, is that commutativity applies only to two operands. [1] https://www.springer.com/us/book/9780817647056 https://www.springer.com/us/book/9780817647056 [2] https://math.stackexchange.com/questions/646665/why-does-commutativity-of-addition-fail-for-infinite-sums https://math.stackexchange.com/questions/646665/why-does-com...
  - jonsen 8y ago
    Take subtraction. The binary operator - is not commutative in the sense that a - b is not equal to b - a. But a - b commutes to - b + a. Any number of +or-with-operand can be arranged in any order. This is commutativity in general. See the start of Chapter 1 in Part 1: https://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp36404 https://onlinebooks.library.upenn.edu/webbin/book/lookupid?k... This is a very practical semantics of commutativity when programming. It’s unfortunately lost in most modern math expositions.
    - 0815test 8y ago
      But this relies on associativity - without associativity, you just don't have a consistent definition of e.g. (a + b + c + d) but only, e.g. + + + / \ / \ / \ + + a + a + / \ / \ / \ / \ a b c d + d b + / \ / \ b c c d and others as well. There would be practically no point in trying to find a definition of "commutative" for these structures that don't involve associativity.
      - jonsen 8y ago
        -6-7-8 == -8-7-6 == -7-8-6 == ... How does this rely on associativity? It does not rely on parenthetical associativity. The operator is of course associated with an operand, but that’s not what is meant by associativity.
        dragonwriter 8y ago
        > How does this rely on associativity? It does not rely on parenthetical associativity. It's exactly the combination of commutivity of addition, associativity of addition, and equivalence of subtraction with addition of the additive inverse, that allows the general rearrangement of symbols you are discussing.
        deleted 8y ago
        [deleted]

dbaupp 8y ago

That is due to associativity. You're implicitly relying on a consistent left-to-right evaluation order, but the fundamental problem can be phrased as (using s for small and b for big): (((b + s) + s) + s) + s Can be different to b + (s + (s + (s + s))) This re-parenthesising is related to associativity, not commutivity.

jonsen 8y ago
Rearranging operands with their operations is commuting. Rearranging parentheses is associating. Yes, floating point operations are also not in general associative.
jonsen 8y ago
You're implicitly relying on a consistent left-to-right evaluation order, That’s standard, I think.
- dbaupp 8y ago
  Indeed, it is standard, but eliding the parentheses doesn't mean they aren't implicitly there, and doesn't turn non-associativity into non-commutativity. Commutivity means that these are equal: (((b + s) + s) + s) + s == s + (s + (s + (s + b)))