4 ms·

Does Julia ignore the problem of floating point not being associative, commutative nor distributive? The reason it’s a thing is from LLVM and I’m not sure you

Does Julia ignore the problem of floating point not being associative, commutative nor distributive? The reason it’s a thing is from LLVM and I’m not sure you can “language design” your way out of this problem as it seems intrinsic to IEEE 754.

tomsmeding 1y ago
Nitpick, but IEEE float operations are commutative (when relevant and appropriate). Associative and distributive they indeed are not.
- vlovich123 1y ago
  Unless I’m having a brain fart it’s not commutative or you mean something by “relevant and appropriate” that I’m not understanding. a+b+c != c+b+a That’s why you need techniques like Kahan summation.
  - wtallis 1y ago
    "a+b+c" doesn't describe a unique evaluation order. You need some parentheses to disambiguate which changes are due to associativity vs commutativity. a+(b+c)=(c+b)+a should be true of floating point numbers, due to commutativity. a+(b+c)=(a+b)+c may fail due to the lack of associativity.
    - adastra22 1y ago
      It is not, due to precision. Consider a=1.00000, b=-0.99999, and c=0.00000582618.
      - zygentoma 1y ago
        You still need to specify an evaluation order …
      - immibis 1y ago
        Does (1.00000+-0.99999)+0.00000582618 != 0.00000582618+(-0.99999+1.00000) ? This would disprove commutativity. But I think they're equal.
      - jcranmer 1y ago
        No, the two evaluations will give you exactly the same result: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=eb13978ce3c30a619da6a63209351a9d https://play.rust-lang.org/?version=stable&mode=debug&editio... IEEE 754 operations are nonassociative, but they are commutative (at least if you ignore the effect of NaN payloads).
        dbdr 1y ago
        Is there a case involving NaN where they are not commutative? Do you mean getting a different bit-level representation of NaN?
        Remnant44 1y ago
        In practical use for simd, various min/max operations. On Intel at least, they propagate nan or not based on operand order
        boulos 1y ago
        Also all comparisons.
        jcranmer 1y ago
        IEEE 754 doesn't (usually) distinguish between different NaN encodings for the purposes of semantics--if the result is a NaN, it doesn't specify which NaN the result is. Most hardware vendors implement a form of NaN propagation: when both inputs are NaN, one of the operands is returned, for example, always the left NaN is returned if both are NaN. As a side note: all compilers I'm aware of make almost no guarantees on preserving the value of NaN payloads, hence they consider floating-point operations to be fully commutative, and there's no general way to guarantee that they evaluate in exactly the order you specified.
        imtringued 1y ago
        https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=1440b547fd063bab88a7f2c2a203c8f0 https://play.rust-lang.org/?version=stable&mode=debug&editio... You're supposed to do (a+b) to demonstrate the effect, because floating point subtraction that results in a number near zero is sensitive to rounding (worst case, a non-zero number gets you a zero number), which can introduce a huge error when a and b are very similar numbers.
  - nyrikki 1y ago
    IEEE 754 floating-point addition and multiplication are commutative in practice, even if there are exceptions with NaNs etc.. But remember that commutative is on the operations (+,x) which are binary operations, a+b=b+a and ab=ba, you can get accumulated rounding errors on iterated forms of those binary operations.
  - wfleming 1y ago
    We’re in very nitpicky terminology weeds here (and I’m not the person you’re replying to), but my understanding is “commutative” is specifically about reordering operands of one binary op (4+3 == 3+4), while “associative” is about reordering a longer chain of the same operation (1+2+3 == 1+3+2). Edit: Wikipedia actually says associativity is definitionally about changing parens[0]. Mostly amounts to the same thing for standard arithmetic operators, but it’s an interesting distinction. [0]: https://en.wikipedia.org/wiki/Associative_property https://en.wikipedia.org/wiki/Associative_property
    - nyrikki 1y ago
      It is not a nit it is fundamental, a•b•c is associativity, specifically operator associativity. Rounding and eventual underflow in IEEE means an expression X•Y for any algebraic operation • produces, if finite, a result (X•Y)·( 1 + ß ) + µ where |µ| cannot exceed half the smallest gap between numbers in the destination’s format, and |ß| < 2^-N , and ß·µ = 0 . ( µ ≠ 0 only when Underflow occurs.) And yes that is a binary relation only a•b•c is really (a•b)•c assuming left operator associativity, one of the properties that IEEE doesn't have.
  - amluto 1y ago
    I think the other replies are overcomplicating this. + is a binary operation, and a+b+c can’t be interpreted without knowing whether one treats + as left-associative or right-associative. Let’s assume the former: a+b+c really means (a+b)+c. If + is commutative, you can turn (a+b)+c into (b+a)+c or c+(a+b) or (commuting twice) c+(b+a). But that last expression is not the same thing as (c+b)+a. Getting there requires associativity, and floating point addition is not associative.
    - deleted 1y ago
      [deleted]
  - dataangel 1y ago
    For those to be equal you need both associativity and commutativity. Commutativity says that a*b = b*a, but that's not enough to allow arbitrary reordering. When you write a*b*c depending on whether * is left or right associative that either means a*(b*c) or (a*b)*c. If those are equal we say the operation is associative. You need both to allow arbitrary reordering. If an operation is only commutative you can turn a*(b*c) into a*(c*b) or (b*c)*a but there is no way to put a in the middle.
ChrisRackauckas 1y ago
No it only uses the same LLVM compiler passes and you enable certain optimizations locally via macros if you want to allow reordering in a given expression.

tomsmeding 1y ago

Nitpick, but IEEE float operations are commutative (when relevant and appropriate). Associative and distributive they indeed are not.

vlovich123 1y ago
Unless I’m having a brain fart it’s not commutative or you mean something by “relevant and appropriate” that I’m not understanding. a+b+c != c+b+a That’s why you need techniques like Kahan summation.
- wtallis 1y ago
  "a+b+c" doesn't describe a unique evaluation order. You need some parentheses to disambiguate which changes are due to associativity vs commutativity. a+(b+c)=(c+b)+a should be true of floating point numbers, due to commutativity. a+(b+c)=(a+b)+c may fail due to the lack of associativity.
  - adastra22 1y ago
    It is not, due to precision. Consider a=1.00000, b=-0.99999, and c=0.00000582618.
    - zygentoma 1y ago
      You still need to specify an evaluation order …
    - immibis 1y ago
      Does (1.00000+-0.99999)+0.00000582618 != 0.00000582618+(-0.99999+1.00000) ? This would disprove commutativity. But I think they're equal.
    - jcranmer 1y ago
      No, the two evaluations will give you exactly the same result: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=eb13978ce3c30a619da6a63209351a9d https://play.rust-lang.org/?version=stable&mode=debug&editio... IEEE 754 operations are nonassociative, but they are commutative (at least if you ignore the effect of NaN payloads).
      - dbdr 1y ago
        Is there a case involving NaN where they are not commutative? Do you mean getting a different bit-level representation of NaN?
        Remnant44 1y ago
        In practical use for simd, various min/max operations. On Intel at least, they propagate nan or not based on operand order
        boulos 1y ago
        Also all comparisons.
        jcranmer 1y ago
        IEEE 754 doesn't (usually) distinguish between different NaN encodings for the purposes of semantics--if the result is a NaN, it doesn't specify which NaN the result is. Most hardware vendors implement a form of NaN propagation: when both inputs are NaN, one of the operands is returned, for example, always the left NaN is returned if both are NaN. As a side note: all compilers I'm aware of make almost no guarantees on preserving the value of NaN payloads, hence they consider floating-point operations to be fully commutative, and there's no general way to guarantee that they evaluate in exactly the order you specified.
      - imtringued 1y ago
        https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=1440b547fd063bab88a7f2c2a203c8f0 https://play.rust-lang.org/?version=stable&mode=debug&editio... You're supposed to do (a+b) to demonstrate the effect, because floating point subtraction that results in a number near zero is sensitive to rounding (worst case, a non-zero number gets you a zero number), which can introduce a huge error when a and b are very similar numbers.
- nyrikki 1y ago
  IEEE 754 floating-point addition and multiplication are commutative in practice, even if there are exceptions with NaNs etc.. But remember that commutative is on the operations (+,x) which are binary operations, a+b=b+a and ab=ba, you can get accumulated rounding errors on iterated forms of those binary operations.
- wfleming 1y ago
  We’re in very nitpicky terminology weeds here (and I’m not the person you’re replying to), but my understanding is “commutative” is specifically about reordering operands of one binary op (4+3 == 3+4), while “associative” is about reordering a longer chain of the same operation (1+2+3 == 1+3+2). Edit: Wikipedia actually says associativity is definitionally about changing parens[0]. Mostly amounts to the same thing for standard arithmetic operators, but it’s an interesting distinction. [0]: https://en.wikipedia.org/wiki/Associative_property https://en.wikipedia.org/wiki/Associative_property
  - nyrikki 1y ago
    It is not a nit it is fundamental, a•b•c is associativity, specifically operator associativity. Rounding and eventual underflow in IEEE means an expression X•Y for any algebraic operation • produces, if finite, a result (X•Y)·( 1 + ß ) + µ where |µ| cannot exceed half the smallest gap between numbers in the destination’s format, and |ß| < 2^-N , and ß·µ = 0 . ( µ ≠ 0 only when Underflow occurs.) And yes that is a binary relation only a•b•c is really (a•b)•c assuming left operator associativity, one of the properties that IEEE doesn't have.
- amluto 1y ago
  I think the other replies are overcomplicating this. + is a binary operation, and a+b+c can’t be interpreted without knowing whether one treats + as left-associative or right-associative. Let’s assume the former: a+b+c really means (a+b)+c. If + is commutative, you can turn (a+b)+c into (b+a)+c or c+(a+b) or (commuting twice) c+(b+a). But that last expression is not the same thing as (c+b)+a. Getting there requires associativity, and floating point addition is not associative.
  - deleted 1y ago
    [deleted]
- dataangel 1y ago
  For those to be equal you need both associativity and commutativity. Commutativity says that a*b = b*a, but that's not enough to allow arbitrary reordering. When you write a*b*c depending on whether * is left or right associative that either means a*(b*c) or (a*b)*c. If those are equal we say the operation is associative. You need both to allow arbitrary reordering. If an operation is only commutative you can turn a*(b*c) into a*(c*b) or (b*c)*a but there is no way to put a in the middle.

ChrisRackauckas 1y ago

No it only uses the same LLVM compiler passes and you enable certain optimizations locally via macros if you want to allow reordering in a given expression.