6 ms·

Minor erratum: Floating point addition actually is commutative; it's in fact non-associative.

by ogogmad 4y ago

dekhn 4y ago
with some significant exceptions, such as NaNs.
- recursive 4y ago
  Can you think of some `x` where `x + NaN` is not identical to `NaN + x`? I can't.
  - dekhn 4y ago
    you mean, like 1 + NaN = NaN and NaN + 1 = NaN, but NaN != NaN? (I'm not a numerical expert, just repeating what others have told me)
    - CountSessine 4y ago
      Yes. An NaN in IEEE754 has all 1’s in the exponent, and then the high bit of the mantissa determines whether it’s quiet or signalling, but then rest of the mantissa is/can be a “payload”.
      - bruce343434 4y ago
        Sign bit determines signalling
        robocat 4y ago
        Please double check your facts before disagreeing with somebody so abruptly. Sign bit is NOT the signalling/quiet bit. Bit 51 (edit or bit 50 - damn ***** IEEE for not publishing important standards for free public access) is according to the first result I looked at: https://craftinginterpreters.com/optimization.html https://craftinginterpreters.com/optimization.html Edit 2 from IEEE 754 (2008 version): 6.2.1 NaN encodings in binary formats This subclause further specifies the encodings of NaNs as bit strings when they are the results of operations. When encoded, all NaNs have a sign bit and a pattern of bits necessary to identify the encoding as a NaN and which determines its kind (sNaN vs. qNaN). The remaining bits, which are in the trailing significand field, encode the payload, which might be diagnostic information (see above). All binary NaN bit strings have all the bits of the biased exponent field E set to 1 (see 3.4). A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0. If the first bit of the trailing significand field is 0, some other bit of the trailing significand field must be non-zero to distinguish the NaN from infinity. In the preferred encoding just described, a signaling NaN shall be quieted by setting d1 to 1, leaving the remaining bits of T unchanged. 6.3 The sign bit When either an input or result is NaN, this standard does not interpret the sign of a NaN. Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand. The logical predicate totalOrder is also affected by the sign bit of a NaN operand. For all other operations, this standard does not specify the sign bit of a NaN result, even when there is only one input NaN, or when the NaN is produced from an invalid operation. When neither the inputs nor result are NaN, the sign of a product or quotient is the exclusive OR of the operands’ signs; the sign of a sum, or of a difference x−y regarded as a sum x+(−y), differs from at most one of the addends’ signs; and the sign of the result of conversions, the quantize operation, the roundTo- Integral operations, and the roundToIntegralExact (see 5.3.1) is the sign of the first or only operand. These rules shall apply even when operands or results are zero or infinite. When the sum of two operands with opposite signs (or the difference of two operands with like signs) is exactly zero, the sign of that sum (or difference) shall be +0 in all rounding-direction attributes except roundTowardNegative; under that attribute, the sign of an exact zero sum (or difference) shall be −0. However, x + x = x − (−x) retains the same sign as x even when x is zero. When (a×b)+c is exactly zero, the sign of fusedMultiplyAdd(a, b, c) shall be determined by the rules above for a sum of operands. When the exact result of (a × b) + c is non-zero yet the result of fusedMultiplyAdd is zero because of rounding, the zero result takes the sign of the exact result. Except that squareRoot(−0) shall be −0, every numeric squareRoot result shall have a positive sign. I.e. you are definitely wrong. The sign bit can be + or - for NaN (presumably a side-effect of the encoding for +/-Infinity ). And then that leads to a bunch of arse (section 6.3) because the spec needs to decide what happens to the sign bit in a bunch of different situations. PS: fucking infinity. Infinity should have been NaN. Infinity ≠ Infinity, except in in the egghead-land IEEE (side note: egghead is a compliment IMHO). Mind you, easy to see mistakes in retrospect, but corner cases are shit in programming. I do like NaN, although reading comments here, and the IEEE spec, forces me to learn how little I now about NaN encodings. Oh, and any NaN should equal any other NaN. Mathematically obviously not, but logically yes and IEEE is for programming. NaN is already defined as a nonsense, so at least keep the nonsense consistent. Changing if = to if ≠ should not introduce subtle logic bugs. Ranting edit #755: and while we are at it, -0 is an abomination in the eyes of the Great Architect in the Matrix - it should never have been allowed - perhaps -0 should have been NaN with signalling bits in the exponent (even though that would prevent some language virtual machine optimisations where 53 bits of NaN get used to pack other information, but the win would be compelling because reducing bugs due special cases is huge IMHO). How many developers understand IEEE corner cases: fuck all in my long experience.
        bruce343434 4y ago
        The source I had in my head as I was replying was https://posithub.org/docs/Posits4.pdf https://posithub.org/docs/Posits4.pdf pages 31/32 which implies that the sign bit is responsible for signalling-ness. Neither of these are a primary source however. A random stackoverflow answer without sources seems to confirm your pov. Now I don't know what to believe. How is the sign bit used in NaNs? Would they really waste that bit?
        stephencanon 4y ago
        Hi, former IEEE 754 committee member here: languages and architectures are allowed to choose how they encode signalingness, but they cannot use the sign bit to do it. The most common choice is to use the high-order but of the significand field, but most choices you might make is represented by some architecture.
        robocat 4y ago
        Awesome! So the important part of section 6.2.1 (2008) is the “should” is not a “must”? “A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0.“ Or is it that some implementations before 2008 used other bits? PS: I might be complaining, but I do sincerely thank you for your hard work. I certainly would not want to be on a standards committee, so I sincerely appreciate the efforts of the committed whom fight so hard to make things better. Your comment just goes to show how many corner cases there are to the corner cases!!
        jcranmer 4y ago
        Traditionally, PPC used a different encoding of qNaN than, well, everybody else. PPC itself would later include a hardware mode that aligned to the more universal interpretation of qNaN.
        4y ago
  - MaulingMonkey 4y ago
    If x is another NaN with a different payload, the result is likely a NaN with a payload corresponding to the left side of the addition.
    - raphlinus 4y ago
      That is correct, here is a playground link which shows that result: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=5ca91830039cb3ac1a2f97b12de7cfe0 https://play.rust-lang.org/?version=stable&mode=debug&editio...
    - stephencanon 4y ago
      This varies tremendously across architectures and uarches and compilers. The result will be a quiet NaN, and you can’t say anything beyond that.
  - jcranmer 4y ago
    It depends on your model of NaN. If you think there is only one NaN value, then the two values return the same result. If there are multiple distinct NaN values (i.e., you distinguish between NaNs with different payloads), then the resulting payload of an arithmetic operation is... not well-specified. Most hardware architectures (x86, ARM fall into this category) pick the rule that the payload is the Nth operand (usually first, sometimes second) when multiple inputs are NaN. I believe there's some hardware where the lesser of the payloads (converted to an integer) is picked instead. RISC-V dispenses with NaN payload propagation entirely. There is theoretically the ability for hardware to generate a new unique NaN with the hardware address of the instruction into the payload, but I don't believe any hardware actually does it. Most programming languages do not generally model NaN with greater fidelity than "there is a NaN value" or maybe "there is a distinction between qNaN and sNaN."
deleted 4y ago
[deleted]
mkeeter 4y ago
Thanks, fixed!
marcosdumay 4y ago
Yes, it's commutative. But it is associative. Make a number with 3 bits of mantissa, and go add a thousand repetitions of 1. You can get hundreds of different results depending on the order you add them up.
- wizzwizz4 4y ago
  > But it is associative. You're describing a non-associative operation.
  - marcosdumay 4y ago
    Ops. Yes, you are right.
  - ogogmad 4y ago
    Exactly. See the definition: https://mathworld.wolfram.com/Associative.html https://mathworld.wolfram.com/Associative.html
- deleted 4y ago
  [deleted]
lmm 4y ago
It's not commutative; -0.0 + 0.0 = -0.0 but 0.0 + -0.0 = 0.0.
- jcranmer 4y ago
  Um, IEEE 754 specifies that -0.0 + 0.0 is 0.0, not -0.0. It's still commutative.

Minor erratum: Floating point addition actually is commutative; it's in fact non-associative.

dekhn 4y ago

with some significant exceptions, such as NaNs.

recursive 4y ago
Can you think of some `x` where `x + NaN` is not identical to `NaN + x`? I can't.
- dekhn 4y ago
  you mean, like 1 + NaN = NaN and NaN + 1 = NaN, but NaN != NaN? (I'm not a numerical expert, just repeating what others have told me)
  - CountSessine 4y ago
    Yes. An NaN in IEEE754 has all 1’s in the exponent, and then the high bit of the mantissa determines whether it’s quiet or signalling, but then rest of the mantissa is/can be a “payload”.
    - bruce343434 4y ago
      Sign bit determines signalling
      - robocat 4y ago
        Please double check your facts before disagreeing with somebody so abruptly. Sign bit is NOT the signalling/quiet bit. Bit 51 (edit or bit 50 - damn ***** IEEE for not publishing important standards for free public access) is according to the first result I looked at: https://craftinginterpreters.com/optimization.html https://craftinginterpreters.com/optimization.html Edit 2 from IEEE 754 (2008 version): 6.2.1 NaN encodings in binary formats This subclause further specifies the encodings of NaNs as bit strings when they are the results of operations. When encoded, all NaNs have a sign bit and a pattern of bits necessary to identify the encoding as a NaN and which determines its kind (sNaN vs. qNaN). The remaining bits, which are in the trailing significand field, encode the payload, which might be diagnostic information (see above). All binary NaN bit strings have all the bits of the biased exponent field E set to 1 (see 3.4). A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0. If the first bit of the trailing significand field is 0, some other bit of the trailing significand field must be non-zero to distinguish the NaN from infinity. In the preferred encoding just described, a signaling NaN shall be quieted by setting d1 to 1, leaving the remaining bits of T unchanged. 6.3 The sign bit When either an input or result is NaN, this standard does not interpret the sign of a NaN. Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand. The logical predicate totalOrder is also affected by the sign bit of a NaN operand. For all other operations, this standard does not specify the sign bit of a NaN result, even when there is only one input NaN, or when the NaN is produced from an invalid operation. When neither the inputs nor result are NaN, the sign of a product or quotient is the exclusive OR of the operands’ signs; the sign of a sum, or of a difference x−y regarded as a sum x+(−y), differs from at most one of the addends’ signs; and the sign of the result of conversions, the quantize operation, the roundTo- Integral operations, and the roundToIntegralExact (see 5.3.1) is the sign of the first or only operand. These rules shall apply even when operands or results are zero or infinite. When the sum of two operands with opposite signs (or the difference of two operands with like signs) is exactly zero, the sign of that sum (or difference) shall be +0 in all rounding-direction attributes except roundTowardNegative; under that attribute, the sign of an exact zero sum (or difference) shall be −0. However, x + x = x − (−x) retains the same sign as x even when x is zero. When (a×b)+c is exactly zero, the sign of fusedMultiplyAdd(a, b, c) shall be determined by the rules above for a sum of operands. When the exact result of (a × b) + c is non-zero yet the result of fusedMultiplyAdd is zero because of rounding, the zero result takes the sign of the exact result. Except that squareRoot(−0) shall be −0, every numeric squareRoot result shall have a positive sign. I.e. you are definitely wrong. The sign bit can be + or - for NaN (presumably a side-effect of the encoding for +/-Infinity ). And then that leads to a bunch of arse (section 6.3) because the spec needs to decide what happens to the sign bit in a bunch of different situations. PS: fucking infinity. Infinity should have been NaN. Infinity ≠ Infinity, except in in the egghead-land IEEE (side note: egghead is a compliment IMHO). Mind you, easy to see mistakes in retrospect, but corner cases are shit in programming. I do like NaN, although reading comments here, and the IEEE spec, forces me to learn how little I now about NaN encodings. Oh, and any NaN should equal any other NaN. Mathematically obviously not, but logically yes and IEEE is for programming. NaN is already defined as a nonsense, so at least keep the nonsense consistent. Changing if = to if ≠ should not introduce subtle logic bugs. Ranting edit #755: and while we are at it, -0 is an abomination in the eyes of the Great Architect in the Matrix - it should never have been allowed - perhaps -0 should have been NaN with signalling bits in the exponent (even though that would prevent some language virtual machine optimisations where 53 bits of NaN get used to pack other information, but the win would be compelling because reducing bugs due special cases is huge IMHO). How many developers understand IEEE corner cases: fuck all in my long experience.
        bruce343434 4y ago
        The source I had in my head as I was replying was https://posithub.org/docs/Posits4.pdf https://posithub.org/docs/Posits4.pdf pages 31/32 which implies that the sign bit is responsible for signalling-ness. Neither of these are a primary source however. A random stackoverflow answer without sources seems to confirm your pov. Now I don't know what to believe. How is the sign bit used in NaNs? Would they really waste that bit?
        stephencanon 4y ago
        Hi, former IEEE 754 committee member here: languages and architectures are allowed to choose how they encode signalingness, but they cannot use the sign bit to do it. The most common choice is to use the high-order but of the significand field, but most choices you might make is represented by some architecture.
        robocat 4y ago
        Awesome! So the important part of section 6.2.1 (2008) is the “should” is not a “must”? “A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0.“ Or is it that some implementations before 2008 used other bits? PS: I might be complaining, but I do sincerely thank you for your hard work. I certainly would not want to be on a standards committee, so I sincerely appreciate the efforts of the committed whom fight so hard to make things better. Your comment just goes to show how many corner cases there are to the corner cases!!
        jcranmer 4y ago
        Traditionally, PPC used a different encoding of qNaN than, well, everybody else. PPC itself would later include a hardware mode that aligned to the more universal interpretation of qNaN.
        4y ago
- MaulingMonkey 4y ago
  If x is another NaN with a different payload, the result is likely a NaN with a payload corresponding to the left side of the addition.
  - raphlinus 4y ago
    That is correct, here is a playground link which shows that result: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=5ca91830039cb3ac1a2f97b12de7cfe0 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - stephencanon 4y ago
    This varies tremendously across architectures and uarches and compilers. The result will be a quiet NaN, and you can’t say anything beyond that.
- jcranmer 4y ago
  It depends on your model of NaN. If you think there is only one NaN value, then the two values return the same result. If there are multiple distinct NaN values (i.e., you distinguish between NaNs with different payloads), then the resulting payload of an arithmetic operation is... not well-specified. Most hardware architectures (x86, ARM fall into this category) pick the rule that the payload is the Nth operand (usually first, sometimes second) when multiple inputs are NaN. I believe there's some hardware where the lesser of the payloads (converted to an integer) is picked instead. RISC-V dispenses with NaN payload propagation entirely. There is theoretically the ability for hardware to generate a new unique NaN with the hardware address of the instruction into the payload, but I don't believe any hardware actually does it. Most programming languages do not generally model NaN with greater fidelity than "there is a NaN value" or maybe "there is a distinction between qNaN and sNaN."

deleted 4y ago

[deleted]

mkeeter 4y ago

Thanks, fixed!

marcosdumay 4y ago

Yes, it's commutative. But it is associative. Make a number with 3 bits of mantissa, and go add a thousand repetitions of 1. You can get hundreds of different results depending on the order you add them up.

wizzwizz4 4y ago
> But it is associative. You're describing a non-associative operation.
- marcosdumay 4y ago
  Ops. Yes, you are right.
- ogogmad 4y ago
  Exactly. See the definition: https://mathworld.wolfram.com/Associative.html https://mathworld.wolfram.com/Associative.html
deleted 4y ago
[deleted]

lmm 4y ago

It's not commutative; -0.0 + 0.0 = -0.0 but 0.0 + -0.0 = 0.0.

jcranmer 4y ago
Um, IEEE 754 specifies that -0.0 + 0.0 is 0.0, not -0.0. It's still commutative.