5 ms·
I've stated some notes on Floats before, and I think this blogpost is pretty good overall. The one thing that trips up a lot of people (that wasn't mentioned i
by dragontamer 9y ago
I've stated some notes on Floats before, and I think this blogpost is pretty good overall.
The one thing that trips up a lot of people (that wasn't mentioned in this post) is that Floats are non-associative. Try the following in Python (or whatever language that uses Doubles):
>>> 1 + 1 + (2. * * 53)
> 9007199254740994.0
>>> 1 + (1 + (2. * * 53))
> 9007199254740992.0
claytonjy noted a point of confusion, the above statement has been edited for clarity.
The number 53 is chosen, because there's 53 bits in the double mantissa. Which is when "+1" will become too small and drop-off of the Double.
In the first case, 1+1 becomes 2 (which is large enough to be added to 2. * * 53). So you end up with the "correct" answer. But (2. * * 53 + 1) rounds down (because the 1 drops off), and the additional +1 afterwards also drops off due to rounding error.
Therefore, Floating Point math is commutative but NOT Associative. And that's really what makes things confusing for most people, in my experience.
x86 with the x87 coprocessor actually performs 80-bit floats to deal with this issue. So you can afford to lose a fair number of bits under older x86 platforms. But modern C++ / C code typically compiles to the faster SSE2 instructions, which only keep 64-bits per operation. This only demonstrates that rounding behavior is not only architecture-specific, but also compiler-option specific !!
- wruza 9y ago2. 53 should read as 2^53 here (HN markup eaten star characters)
- dragontamer 9y agoThanks, I just edited it.
- Atrix256 9y agogood point. That's interesting!
- colejohnson66 9y agoIs there a way to force 80 bit floats if you need them?
- wruza 9y agoThere is a way to politely ask for it and be careful to what you get. https://en.wikipedia.org/wiki/Long_double https://en.wikipedia.org/wiki/Long_double
- gct 9y agoIf you want a guarantee, use something like gmp that'll do them in software.
- dragontamer 9y agoWell, it seems odd to me that anybody would want "exactly 80 bit floats". 1. In the case of "doubles", it seems like its more important that your code works the same on all platforms. So you can enable precise IEEE754 behavior, to ensure that your rounding errors and whatnot are the same from platform to platform. You'll still need to somehow ensure that all of your operations occur in the same order however, IEEE754 only specifies when and how 64-bit numbers get rounded. So sorting your numbers, adding them up from smallest magnitude to largest magnitude is important still. 2. In the case that 64-bits is insufficient precision, you should be using something more precise but also consistent across different platforms. In case #1: its usually more important that all code "makes the same rounding errors", as opposed to "some code rounds more poorly than other code". In case #2: you'll want ALL your code to have better rounding behavior. And "Long Double" is still implementation specific. Its probably best to go to a pure software solution (ie: BigNums of some kind) if precision is important to you. The case #3: some people don't care about the precision, and are willing to have lower precision as long as the results are "nearly correct". Video Game programmers are far more interested in speed for example, so the "fast inverse square root" barely even has 10-bits of precision for example, but the far greater speed wins out in most video game situations.
- claytonjy 9y agoThe second equation confused me a bit as a math-first, cs-second person; looks like a commutative transform, not an associative one. The trick is one must already trust these ops are commutative. The second equation might be more clearly written as: >>> 1 + (1 + (2. * * 53)) to avoid hiding the associativity behind the assumption of commutativity.
- dragontamer 9y agoYou're right. Sorry for the confusion. I'll edit it to make it more clear.
- gct 9y agoI believe the x87 uses 80 bits internally, but it only runs operations until it has sufficient precision to do the rounding (which is hard to do in general, see: http://perso.ens-lyon.fr/jean-michel.muller/Intro-to-TMD.htm http://perso.ens-lyon.fr/jean-michel.muller/Intro-to-TMD.htm)
- kraghen 9y agoIt gets even worse: (1 + 2 ^ 53) - 2 ^ 53 evaluates to 0 while 1 + (2 ^ 53 - 2 ^ 53) evaluates to 1 (the correct result), which means that even the operation of adding three floating point numbers has unbounded relative error in the general case. This is a great source of frustration in computational geometry, where this turns from a quantitative issue to a qualitative one, since if we get the sign of an expression wrong our data structures might no longer reflect the actual topology of the problem.
- dragontamer 9y ago> which means that even the operation of adding three floating point numbers has unbounded relative error in the general case. Its not quite "in the general case". In "any case with subtraction", there is unbounded relative error. And remember that addition with negative numbers can become subtraction. Error-management is very important. But if you can GUARANTEE that your operations have the same sign, and that you're only using addition, multiplication, and division... then error is easier to track. Its that subtraction (aka: cancellation error) that gets ya.
- zmonx 9y agoIt is true that cancellation errors are often the source of wrong results. However, computations involving IEEE floating point arithmetic can go horribly wrong even if there is no addition and no subtraction whatsoever, no divisions, and only a very small number of rounding errors. Here is one such example: http://people.eecs.berkeley.edu/~wkahan/WrongR.pdf http://people.eecs.berkeley.edu/~wkahan/WrongR.pdf Even professional users working in this domain will have a hard time to locate the cause of such problems involving IEEE floating point arithmetic. The format is extremely error-prone to use for casual users and experts alike.
- dragontamer 9y agoEhhh... I think that paper kinda "tricks" you with point #3. > Only 257 algebraic operations, so no hordes of rounding errors Rounding errors in Floating-point math grows exponentially in the common case. So 257 operations is more than enough to wipe out 53-bits of precision. Its not "hordes" of rounding errors that cause issues. Its the exponential nature of rounding errors, exponentially increasing every step of the way.