This came during my OMSCS Game AI course as an example of the dangers of using floats to represent game object location. If you get further from the origin point (or another game element you are referencing from) you are losing precision as the float needs to use more of the significand to store the larger value.
Maybe I am too mathematically enclined, but this was not easy to understand.
The ELI5 explanation of floating point: they approximately give you the same accuracy (in terms of bits) independently of the scale. Whether your number if much below 1, around 1, or much above 1, you can expect to have as much precision in the leading bits.
This is the key property, but internalizing it is difficult.
My favorite FP Fun Fact is that float comparisons can (almost) use integer comparisons. To determine if a > b, reinterpret a and b as signed ints and just compare those like any old ints. It (almost) works!
The implication is that the next biggest float is (almost) always what you get when you reinterpret its bits as an integer, and add one. For example, start with the zero float: all bits zero. Add one using integer arithmetic. In int-speak it's just one; in float-speak it's a tiny-mantissa denormal. But that's the next float; and `nextafter` is implemented using integer arithmetic.
Learning that floats are ordered according to integer comparisons makes it feel way more natural. But of course there's the usual asterisks: this fails with NaNs, infinities, and negative zero. We get a few nice things, but only a few.
For what it's worth, here's the Rust std implementation [1] of the total (as in, makes NaNs comparable) comparison algorithm given by IEE 751:
let mut left = self.to_bits() as i32;
let mut right = other.to_bits() as i32;
// In case of negatives, flip all the bits except the sign
// to achieve a similar layout as two's complement integers
left ^= (((left >> 31) as u32) >> 1) as i32;
right ^= (((right >> 31) as u32) >> 1) as i32;
left.cmp(&right)
The real shocking fact about floating point is that they are even used at all.
It's throwing out of the window the most basic property operations on number should have : "associativity" and all that for a gain in dynamic range which is not necessary most of the time.
The associativity we expect to hold is (a+b)+c == a+(b+c) and (ab)c == a(bc) and these don't hold for floats even though most math formulas and compiler optimizations rely on these to hold. It's a sad miracle that everything somehow still works out OK most of the time.
You lose determinism most of the time with respect to compiler optimizations, and platform reproducibility if processor don't exactly respect IEE-754 (or is it IEE-854).
The real problem comes when you want to use parallelism. With things like atomic operations and multiple processor doing things out of order, you lose determinism and reproducibility, or add a need for synchronisation or casting operations everywhere.
Even more problematic, is that because number operations are used so often, they are set in "stone", and are implemented at the hardware level. And they use much more transistor because they are more complex than integer arithmetic.
Real programmers don't use floating points, only sloppy lazy ones do.
Real programmers use fixed point representation and make sure the bounds don't overflow/underflow unexpectedly.
Let's ban all hardware floating-point implementation : Just imagine future alien archeologists having a laugh at us when they look at our chips and think "no wonder they were doomed they can't even do a+b right : its foundations were built on sand".
> these don't hold for floats even though most math formulas and compiler optimizations rely on these to hold.
Most compilers have an option like -fassociative-math that explicitly allows optimization under the assumption of associativity and distributivity.
> Real programmers use fixed point representation and make sure the bounds don't overflow/underflow unexpectedly.
So you complain that floating-point is bad because it's not associative but then suggest that we use fixed-point instead (which is also nonassociative), but it's okay, because it's fine as long as you do thing that programmers rarely do.
> Let's ban all hardware floating-point implementation : Just imagine future alien archeologists having a laugh at us when they look at our chips and think "no wonder they were doomed they can't even do a+b right : its foundations were built on sand".
Ah, you're the kind of person who sees that 0.1 + 0.2 != 0.3 and decides to go on a crusade against floating-point because of it. By the way, fixed point has that exact same bug: it's a fault that is caused by the base being different more than the other principles of the floating-point type.
Floating-point has trade-offs; a good programmer understands the trade-offs of floating-point and will not ask more of it than it can provide.
"FatRat" is a hilarious name for a numeric type (and I mean this in a purely positive way). I've always had an impression of Perl as a language with a bit of a quirky, fun community, and it's nice to see that might have carried over to Raku as well.
Good job on showing the hexadecimal version. I recently had a challenging C bug where I was using printf("%a") to show the underlying representation, which uses hexadecimal, and it was a little confusing at first. This site would have been helpful.
One problem I was struggling with: What's the shortest, unambiguous decimal representation of a float?
For example, if you use single precision floats, then you need up to 9 digits of decimal precision to uniquely identify a float. So you would need to use a printf pattern like %.9g to print it. But then 0.1 would be output as 0.100000001, which is ugly. So a common approach is to round to 6 decimal digits: If you use %.6g, you are guaranteed that any decimal input up to 6 significant digits will be printed just like you stored it.
But you would no longer be round-trip safe when the number is the result of a calculation. This is important when you do exact comparisons between floats (eg. to check if data has changed).
So one idea I had was to try printing the float with 6 digits, then scanning it and seeing if it resulted in the same binary representation. If not, try using 7 digits, and so on, up to 9 digits. Then I would have the shortest decimal representation of a float.
This is my algorithm:
int out_length;
char buffer[32];
for (int prec = 6; prec<=9; prec++) {
out_length = sprintf(buffer, "%.*g", prec, floatValue);
if (prec == 9) {
break;
}
float checked_number;
sscanf(buffer, "%g", &checked_number);
if (checked_number == floatValue) {
break;
}
}
I wonder if there is a more efficient way to determine that shortest representation rather than running printf/scanf in a loop?
Don't worry about negative comments, yes, this is not the best way, but (if there's no error, I didn't analyze it thoroughly) it's often good enough; if it works, then it works.
I once wanted to find a vector for which Euler rotation (5°, 5°, 0) will result with the same vector, so I just ran a loop of million iterations or so which would take a starting vector, translate it randomly slightly (add a small random vector) and see if after rotation it's closer to original than the previous vector would be after rotation, if not, discard the change otherwise keep it. The script ran for a couple seconds on Python and with decreasing translation vector based on iteration number, I got perfect result (based on limited float precision of the vector). 2s would be terribly slow in a library but completely satisfying for my needs :D
I read a bit more about the topic, and it seems that the issue with my approach is that the decimal representation might end up exactly halfway between two floats, and then the result of parsing it depends on the rounding mode that the parser uses. (By default scanf should use round-to-even, but I'm not sure all implementations do so)
In the PostgreSQL docs I found a curious fact: They use an algorithm that makes sure the printed decimal is never exactly half way between two representable floats, so the result of scanning the decimal representation doesn't depend on the rounding mode.
Far too superficial because it lacks explanation of non-normal conditions (denormals, zeroes, infinities, sNaNs, and qNaNs) and the complete mapping of values. This isn't properly educational.
"An sNaN (signaling Not-a-Number) is a special floating-point value that is designed to trigger a hardware trap or exception when it is used in an arithmetic operation. This differs from a qNaN (quiet Not-a-Number), which propagates through calculations without causing an immediate exception. Handling sNaNs requires a more deliberate approach that involves enabling floating-point traps and writing a custom trap handler."
I'm glad this exists, except for the fact that IEEE754 is the devil, and posits are better (not assuming hardware support). (Even better than both are bignum rationals, but those are the slowest.)
It would be nice if the site had an explanation why the decimal 0.1 has no finite representation in base-2 system. In short it's about factorization of the base of the system - base-2 lacks 5 that is present in base-10. It is analogous to 1/3 or 1/7 not having a finite representation in base-10 dot notation of a fraction.
33 comments
[ 4.4 ms ] story [ 57.4 ms ] threadThe ELI5 explanation of floating point: they approximately give you the same accuracy (in terms of bits) independently of the scale. Whether your number if much below 1, around 1, or much above 1, you can expect to have as much precision in the leading bits.
This is the key property, but internalizing it is difficult.
https://www.h-schmidt.net/FloatConverter/IEEE754.html
This one has the extra feature of showing the conversion error, but it doesn't support double precision.
The implication is that the next biggest float is (almost) always what you get when you reinterpret its bits as an integer, and add one. For example, start with the zero float: all bits zero. Add one using integer arithmetic. In int-speak it's just one; in float-speak it's a tiny-mantissa denormal. But that's the next float; and `nextafter` is implemented using integer arithmetic.
Learning that floats are ordered according to integer comparisons makes it feel way more natural. But of course there's the usual asterisks: this fails with NaNs, infinities, and negative zero. We get a few nice things, but only a few.
It's sometimes fun to have these kinds of edge cases up your sleeve when testing things.
The real shocking fact about floating point is that they are even used at all.
It's throwing out of the window the most basic property operations on number should have : "associativity" and all that for a gain in dynamic range which is not necessary most of the time.
The associativity we expect to hold is (a+b)+c == a+(b+c) and (ab)c == a(bc) and these don't hold for floats even though most math formulas and compiler optimizations rely on these to hold. It's a sad miracle that everything somehow still works out OK most of the time.
You lose determinism most of the time with respect to compiler optimizations, and platform reproducibility if processor don't exactly respect IEE-754 (or is it IEE-854).
The real problem comes when you want to use parallelism. With things like atomic operations and multiple processor doing things out of order, you lose determinism and reproducibility, or add a need for synchronisation or casting operations everywhere.
Even more problematic, is that because number operations are used so often, they are set in "stone", and are implemented at the hardware level. And they use much more transistor because they are more complex than integer arithmetic.
Real programmers don't use floating points, only sloppy lazy ones do.
Real programmers use fixed point representation and make sure the bounds don't overflow/underflow unexpectedly.
Let's ban all hardware floating-point implementation : Just imagine future alien archeologists having a laugh at us when they look at our chips and think "no wonder they were doomed they can't even do a+b right : its foundations were built on sand".
Most compilers have an option like -fassociative-math that explicitly allows optimization under the assumption of associativity and distributivity.
> Real programmers use fixed point representation and make sure the bounds don't overflow/underflow unexpectedly.
So you complain that floating-point is bad because it's not associative but then suggest that we use fixed-point instead (which is also nonassociative), but it's okay, because it's fine as long as you do thing that programmers rarely do.
> Let's ban all hardware floating-point implementation : Just imagine future alien archeologists having a laugh at us when they look at our chips and think "no wonder they were doomed they can't even do a+b right : its foundations were built on sand".
Ah, you're the kind of person who sees that 0.1 + 0.2 != 0.3 and decides to go on a crusade against floating-point because of it. By the way, fixed point has that exact same bug: it's a fault that is caused by the base being different more than the other principles of the floating-point type.
Floating-point has trade-offs; a good programmer understands the trade-offs of floating-point and will not ask more of it than it can provide.
https://raku.org defaults to Rationals (Rats) and provides FatRat for arbitrary precision
otherwise even relatively normal calculations (eg what’s the mass of electron in quectogram) fail
These types of visualizations are super useful.
[1] - https://cidr.xyz
For example, if you use single precision floats, then you need up to 9 digits of decimal precision to uniquely identify a float. So you would need to use a printf pattern like %.9g to print it. But then 0.1 would be output as 0.100000001, which is ugly. So a common approach is to round to 6 decimal digits: If you use %.6g, you are guaranteed that any decimal input up to 6 significant digits will be printed just like you stored it.
But you would no longer be round-trip safe when the number is the result of a calculation. This is important when you do exact comparisons between floats (eg. to check if data has changed).
So one idea I had was to try printing the float with 6 digits, then scanning it and seeing if it resulted in the same binary representation. If not, try using 7 digits, and so on, up to 9 digits. Then I would have the shortest decimal representation of a float.
This is my algorithm:
I wonder if there is a more efficient way to determine that shortest representation rather than running printf/scanf in a loop?I once wanted to find a vector for which Euler rotation (5°, 5°, 0) will result with the same vector, so I just ran a loop of million iterations or so which would take a starting vector, translate it randomly slightly (add a small random vector) and see if after rotation it's closer to original than the previous vector would be after rotation, if not, discard the change otherwise keep it. The script ran for a couple seconds on Python and with decreasing translation vector based on iteration number, I got perfect result (based on limited float precision of the vector). 2s would be terribly slow in a library but completely satisfying for my needs :D
I read a bit more about the topic, and it seems that the issue with my approach is that the decimal representation might end up exactly halfway between two floats, and then the result of parsing it depends on the rounding mode that the parser uses. (By default scanf should use round-to-even, but I'm not sure all implementations do so)
In the PostgreSQL docs I found a curious fact: They use an algorithm that makes sure the printed decimal is never exactly half way between two representable floats, so the result of scanning the decimal representation doesn't depend on the rounding mode.
Yes, just `printf("%f", ...);` will get you that.
The actual algorithms to do the float->string conversion are quite complicated. Here is a recent pretty good one: https://github.com/ulfjack/ryu
I think there's been an even more recent one that is even more efficient than Ryu but I don't remember the name.
Just learned something. Thanks.