4 ms·

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.

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.