4 ms·

The order in which you sum a large collection of floating-point numbers is also important, if you want the result to be stable.

77pt77 2y ago
Sum smaller absolute value numbers first.
- stabbles 2y ago
  It will still accumulate rounding errors of O(n eps). If you care you can make it O(lg n eps) with pairwise summation or O(eps) with Kahan summation
  - Pesthuf 2y ago
    I just wonder, in situations where precision is so important that these small rounding errors actually matter, aren't floats the wrong tool anyway?
    - owlbite 2y ago
      Sometimes its more about numerical stability than absolute accuracy (numerical stability being defined as not have the property that small changes in input cause large changes in the output).
    - stabbles 2y ago
      In many numerical algorithms it is often that rounding errors add up over iterations / time. Maybe you loose one significant digit in one iteration of your algorithm, let it run longer and rounding errors start to dominate -- the result is garbage. Since performance is important, not using floats is not an option, and you rarely see Kahan summation type of tricks because the heavy lifting is usually done by BLAS libraries (i.e. vectorized linear algebra operations). So, in numerical algorithms the type of tricks is typically using stable matrix decompositions like the QR decomposition A = QR where Q'Q = I (repeated multiplication with Q leaves the quantities roughly the same size, whereas with A things blow up). And there are other tricks, for example if you need to orthogonalize a vector x to this Q, in full precision you compute y = x - Q * (Q' * x), so that Q' * y = 0. The Q' * x computation is a reduction, so it can accumulate O(n eps) errors in finite precision. Instead of doing a more stable reduction (e.g. Kahan summation etc), you can instead repeat the computation: z = y - Q * (Q' * y). The idea is that the second orthogonalization step kills the rounding error noise introduced by the first step. So in short: you can still get accuracy and decent performance with floats, you just have to know the tricks. [Another somewhat interesting point is that on GPUs reductions are by necessity implemented with O(ln n eps) error, and the naive but vectorized CPU implementation has an error O(n/k eps) where k is the vector width]
    - TeMPOraL 2y ago
      They are, but that didn't stop people from using them. They're convenient, they're bounded, and as such, ended up having decades of hardware optimization behind then. When precision turns out to be really important, it's often cheaper to get some smart people to restructure computation as to mitigate the errors, than it is to switch to arbitrary-precision math and deal with consequences. There's a whole field of CS that's spent the last half century or more developing ways to deal with floating point math problems - extending the scope of their use, and making alternatives even less economical. There's an interesting case of it today: LLMs. In theory, they should be fully deterministic with "temperature" parameter set to 0, but they aren't - all that matrix multiplication is massively parallelized, so with floating point math being order-dependent, partial results quickly accumulate non-deterministic errors.
  - SideQuark 2y ago
    You can also use multiple layered Kahan, just like the double double and quad double tricks. Adding just one more layer and letting hardware cover more bits precision is often much faster to get precision than any larger lib. If you're overflowing the exponent, then you need more than hardware magics. But for precision I've used these multi-double tricks with the same guarantees as IEEE style formats, but with as much precision as I want.
- kardos 2y ago
  Sorting is costly though! This summing problem is solved by xsum: https://gitlab.com/radfordneal/xsum https://gitlab.com/radfordneal/xsum There is room for more work here to make it faster or use less memory though.
  - 77pt77 2y ago
    sorting is nlogn in general and faster for numerics. Plus after sorting you can use SIMD to sum everything much faster. But yes, xsum and the like are more accurate.
stabbles 2y ago
This is more relevant than overflow
SideQuark 2y ago
Bingo. Higham's (recently died!) book on numerics has an excellent coverage of a massive amount of summation knowledge and algorithms.

77pt77 2y ago

Sum smaller absolute value numbers first.

stabbles 2y ago
It will still accumulate rounding errors of O(n eps). If you care you can make it O(lg n eps) with pairwise summation or O(eps) with Kahan summation
- Pesthuf 2y ago
  I just wonder, in situations where precision is so important that these small rounding errors actually matter, aren't floats the wrong tool anyway?
  - owlbite 2y ago
    Sometimes its more about numerical stability than absolute accuracy (numerical stability being defined as not have the property that small changes in input cause large changes in the output).
  - stabbles 2y ago
    In many numerical algorithms it is often that rounding errors add up over iterations / time. Maybe you loose one significant digit in one iteration of your algorithm, let it run longer and rounding errors start to dominate -- the result is garbage. Since performance is important, not using floats is not an option, and you rarely see Kahan summation type of tricks because the heavy lifting is usually done by BLAS libraries (i.e. vectorized linear algebra operations). So, in numerical algorithms the type of tricks is typically using stable matrix decompositions like the QR decomposition A = QR where Q'Q = I (repeated multiplication with Q leaves the quantities roughly the same size, whereas with A things blow up). And there are other tricks, for example if you need to orthogonalize a vector x to this Q, in full precision you compute y = x - Q * (Q' * x), so that Q' * y = 0. The Q' * x computation is a reduction, so it can accumulate O(n eps) errors in finite precision. Instead of doing a more stable reduction (e.g. Kahan summation etc), you can instead repeat the computation: z = y - Q * (Q' * y). The idea is that the second orthogonalization step kills the rounding error noise introduced by the first step. So in short: you can still get accuracy and decent performance with floats, you just have to know the tricks. [Another somewhat interesting point is that on GPUs reductions are by necessity implemented with O(ln n eps) error, and the naive but vectorized CPU implementation has an error O(n/k eps) where k is the vector width]
  - TeMPOraL 2y ago
    They are, but that didn't stop people from using them. They're convenient, they're bounded, and as such, ended up having decades of hardware optimization behind then. When precision turns out to be really important, it's often cheaper to get some smart people to restructure computation as to mitigate the errors, than it is to switch to arbitrary-precision math and deal with consequences. There's a whole field of CS that's spent the last half century or more developing ways to deal with floating point math problems - extending the scope of their use, and making alternatives even less economical. There's an interesting case of it today: LLMs. In theory, they should be fully deterministic with "temperature" parameter set to 0, but they aren't - all that matrix multiplication is massively parallelized, so with floating point math being order-dependent, partial results quickly accumulate non-deterministic errors.
- SideQuark 2y ago
  You can also use multiple layered Kahan, just like the double double and quad double tricks. Adding just one more layer and letting hardware cover more bits precision is often much faster to get precision than any larger lib. If you're overflowing the exponent, then you need more than hardware magics. But for precision I've used these multi-double tricks with the same guarantees as IEEE style formats, but with as much precision as I want.
kardos 2y ago
Sorting is costly though! This summing problem is solved by xsum: https://gitlab.com/radfordneal/xsum https://gitlab.com/radfordneal/xsum There is room for more work here to make it faster or use less memory though.
- 77pt77 2y ago
  sorting is nlogn in general and faster for numerics. Plus after sorting you can use SIMD to sum everything much faster. But yes, xsum and the like are more accurate.

stabbles 2y ago

This is more relevant than overflow

SideQuark 2y ago

Bingo. Higham's (recently died!) book on numerics has an excellent coverage of a massive amount of summation knowledge and algorithms.