Didn't everyone learn scientific notation in high school? It's pretty much exactly that, and you could put the coefficient/exponent into whatever bit pattern you'd like.
There is no easy way to make it work in decimal. So you need to learn how fractional parts work in binary, then move up to scientific notation in binary. Then you probably noticed that all numbers start with 1, so you can knock it off to save space. Oh, and add a special case for zero, because it is the only number that doesn't start with 1, and if you are feeling adventurous, there are subnormal numbers.
That's why I find the explanation in the article absolutely brilliant. By treating the exponent as a window, not only you don't need to bother with scientific notation in binary, but zero and subnormal numbers fit very nicely.
In fact, I've been working for years with floating point numbers and feel stupid for not realizing it works just as described in the article. And feeling stupid after reading something is usually a very good sign. I clicked, expected an article I could dismiss in a typical Hacker News fashion, but no, not this time.
Demo: #include <stdio.h>
int
main ()
{
volatile float v;
float acc = 0;
float den = 1.40129846432e-45;
for (size_t i; i < (1ul<<33); i++) {
acc += den;
}
v = acc;
return 0;
}
With -O0: $ gcc float.c -o float -O1 && time ./float ./float 20.60s user 0.00s system 99% cpu 20.610 total
/tmp>cat t.c
#include <stdio.h>
int main() {
float acc = 0;
float den = 1.40129846432e-45;
for (size_t i = 0; i < (1ul<<33); i++) acc += den;
printf("%g\n", acc);
return 0;
}
/tmp>gcc -O3 t.c && time ./a.out
2.35099e-38
./a.out 5.94s user 0.00s system 99% cpu 5.944 total
/tmp>gcc -O3 -ffast-math t.c && time ./a.out
0
./a.out 1.50s user 0.00s system 99% cpu 1.502 total
EDIT That one is interesting too
/tmp>clang -O3 t.c && time ./a.out
2.35099e-38
./a.out 6.04s user 0.00s system 99% cpu 6.044 total
/tmp>clang -O3 -ffast-math t.c && time ./a.out
0
./a.out 0.10s user 0.00s system 99% cpu 0.101 total
I've been fighting the compiler to generate a minimal working example of the subnormals, but didn't have any success.
Some things take need to be taken in account (from the top of my head):
- Rounding. You don't want to get stuck in the same number. - The FPU have some accumulator register that are larger than the floating point register. - Using more register than the architecture has it not trivial because the register renaming and code reordering. The CPU might optimize in a way that the data never leaves those register.
Trying to make a mwe, I found this code:
#include <stdio.h>
int
main ()
{
double x = 5e-324;
double acc = x;
for (size_t i; i < (1ul<<46); i++) {
acc += x;
}
printf ("%e\n", acc);
return 0;
}
gcc double.c -o double -O0
gcc double.c -o double -O1
I also manage to create a code that sometimes run in 1s, but in others would take 30s. Didn't matter if I recompiled.
Floating point is hard.
$ gcc-9 -Wuninitialized -O0 float.c # NO WARNINGS!!!
$ gcc-9 -O1 float.c # NO WARNINGS!!!
$ gcc-9 -Wuninitialized -O1 float.c
float.c: In function 'main':
float.c:9:5: warning: 'i' is used uninitialized in this function [-Wuninitialized]
9 | for (size_t i; i < (1ul << 33); i++) {
| ^~~ $ gcc hn.c -O0 -o hn
for (size_t i; i < (1ul<<46); i++) {
printf ("%zd\n",i);
acc += x;
break;
}
$ gcc hn.c -O0 -o hn
for (size_t i; i < (1ul<<46); i++) {
printf ("%zd\n",i);
acc += x;
}The window and offset explanation naturally accounts for the leading bit, whereas the scientific notation explanation needs further explanation to explain how the leading bit works.
In short, 10^2 * .001 is not allowed in floating point. You can't have a mantissa that starts with 0. The leading bit means all mantissas must be greater than 1.
Without this understanding you won't have an intuitive understanding of the range and precision of floating point, which is why I think the window+offset explanation is much more natural.
In binary, we always know the first non-zero digit of any number - so there's no need to write it down. We know it's 1 because, well, binary.
So we don't waste space, and only write down all the other digits, and then use the exponent to put the 'point' into the right place.
We save a bit of space doing this.
The mantissa can only be a value from [1,2).
i.e. in scientific notation: exponent * mantissa, the mantissa cannot be less than 1, or >= 2 in floating point.
So given that the mantissa can go from 000000 to 111111, what should the values represnet? Obviously it should represent the values from [1,2). Calling it a leading bit is more confusing than it needs to be. Its better to just call it an assumed minimum value.
When I was taught scientific notation in middle school, high school, and at college, it was always explicitly stated that:
1. You can have only one digit before the decimal point.
2. That digit cannot be 0 (unless your number is 0, of course). So 0.3 * 10^5 is not scientific notation.
This is no different. The "twist" is that there is only one possible non-zero bit, whereas in decimal it could be [1-9].
I think this explanation is neat. However, the "usual" formulation is just scientific notation, with the optimization that one bit is redundant.
Personally, I prefer the alternative notation: M * 2^(exponent-precision+1), with M being a p-bit integer. It's easier to work with when you know that M is always an integer, and you don't need to deal with fractions in base 2. In fact, FP made a lot more sense when I took this formulation in decimal, and worked with that.