memcpy moves the four bytes without converting anything. That is why we can look at them.
Doubling adds one to the exponent. Halving takes one away. The mantissa never moves.
Negating changes one bit and nothing else.
Type this one out. It is the instrument for the rest of the hour and it takes two minutes.
Last session we refused to use two of these. Count what that costs.
256
values the 8 bit exponent can take
254
actually used as exponents
33,554,432
bit patterns sitting under those two
0.78%
of everything a float can be
the question for this hour
Two exponent values, times 223 mantissas, times two signs, is 33,554,432 patterns.
Is a bit under one percent of the type a fair price? We will answer that at the end, once we know what it bought.
Have them do the multiplication. 2 x 8388608 x 2. Then hold the question open until the last slide.
What each type does when you go one past the top.
/* 02-edges.c */#include<stdio.h>int main(void)
{
int i = 2147483647;
printf("int max = %d\n", i);
printf("int max + 1 = %d\n", i + 1);
float f = 3.4028235e38f;
printf("float max = %g\n", f);
printf("float max * 2 = %g\n", f * 2);
return0;
}
int max = 2147483647
int max + 1 = -2147483648
float max = 3.40282e+38
float max * 2 = inf
remember
Both types have an edge at the top. Neither can hold the next value.
The int wraps to the most negative number and says nothing.
The float produces a value that means "this went past the end". It is the only type in C that reports its own overflow.
Ask for both predictions first. Most expect the int to wrap and the float to either wrap or crash.
Exponent all ones with a zero mantissa is infinity.
Exponent all ones with any other mantissa is NaN, not a number.
One mantissa bit is the whole difference between them.
Any nonzero mantissa works, so there are 16,777,214 NaN patterns.
Argue about 0/0 for a minute first. Some will say 0, some 1, and both cases are reasonable, which is the point.
A NaN does not go away.
/* 05-spread.c */#include<stdio.h>int main(void)
{
float x = 0.0f / 0.0f;
for (int i = 1; i <= 5; i++) {
x = x * 2.0f + 1.0f;
printf("step %d x = %g\n", i, x);
}
return0;
}
step 1 x = -nan
step 2 x = -nan
step 3 x = -nan
step 4 x = -nan
step 5 x = -nan
remember
Any arithmetic on a NaN gives a NaN.
This is deliberate. A bad value stays visible instead of turning into a plausible number.
Compare with Class 1, where four machines carried on with wrong values and told nobody.
Short slide. The output is five identical lines and that is the whole content.
Comparisons against a NaN are all false, including equality.
/* 06-compare.c */#include<stdio.h>float largest(float *d, int n)
{
float m = d[0];
for (int i = 1; i < n; i++)
if (d[i] > m) m = d[i];
return m;
}
int main(void)
{
float nan = 0.0f / 0.0f;
printf("nan == nan %s\n", nan == nan ? "true" : "false");
printf("nan < 1 %s\n", nan < 1 ? "true" : "false");
printf("nan >= 1 %s\n", nan >= 1 ? "true" : "false");
float a[5] = { 3, 7, nan, 9, 2 };
float b[5] = { nan, 3, 7, 9, 2 };
printf("largest {3, 7, nan, 9, 2} = %g\n", largest(a, 5));
printf("largest {nan, 3, 7, 9, 2} = %g\n", largest(b, 5));
return0;
}
nan == nan false
nan < 1 false
nan >= 1 false
largest {3, 7, nan, 9, 2} = 9
largest {nan, 3, 7, 9, 2} = -nan
remember
A NaN is the only value not equal to itself. That is how isnan used to be written.
x < 1 and x >= 1 are both false at once, which your branches assume cannot happen.
Same function, same data, different order, different answer. A NaN in the middle gets skipped. A NaN first poisons the result.
The two array orders are the useful part. This is the shape of every NaN bug they will meet.
Now the other reserved exponent. Start with zero.
/* 07-zero.c */#include<stdio.h>#include<string.h>void show(char *label, float v)
{
unsigned u;
memcpy(&u, &v, 4);
printf("%-8s ", label);
for (int i = 31; i >= 0; i--) {
putchar(u >> i & 1 ? '1' : '0');
if (i == 31 || i == 23) putchar(' ');
}
printf(" %g\n", v);
}
int main(void)
{
float p = 0.0f;
float n = -0.0f;
show("+0.0f", p);
show("-0.0f", n);
printf("p == n %s\n", p == n ? "true" : "false");
printf("1.0f / p = %g\n", 1.0f / p);
printf("1.0f / n = %g\n", 1.0f / n);
return0;
}
+0.0f 0 00000000 00000000000000000000000 0
-0.0f 1 00000000 00000000000000000000000 -0
p == n true
1.0f / p = inf
1.0f / n = -inf
remember
Zero has to be a special case. Every normal float is 1.something, so no exponent and mantissa can produce zero.
There are two zeros. They compare as equal but they are different patterns.
Divide by each and the sign shows up again, as opposite infinities.
In Class 5 we rejected sign magnitude for having two zeros. Here we accept it. Ask why the trade is different.
Measure what sits either side of the smallest float.
/* 08-hole.c */#include<stdio.h>#include<math.h>int main(void)
{
float small = 1.17549435e-38f;
float above = nextafterf(small, 1.0f);
printf("smallest normal = %.4e\n", small);
printf("the one above it = %.4e\n", above);
printf("step upwards = %.4e\n", above - small);
printf("step down to 0 = %.4e\n", small);
printf("the drop is = %.0f times wider\n",
small / (above - small));
return0;
}
smallest normal = 1.1755e-38
the one above it = 1.1755e-38
step upwards = 1.4013e-45
step down to 0 = 1.1755e-38
the drop is = 8388608 times wider
remember
If the all zero exponent only ever meant zero, there would be nothing at all between zero and 1.1755e-38.
That gap is 8,388,608 times wider than every other gap nearby.
8,388,608 is 223. The hole is exactly as wide as the mantissa is deep.
Ask them to guess the ratio before running it. Nobody guesses eight million.
Two neighbours, subtracted.
/* 09-guarantee.c */#include<stdio.h>#include<math.h>int main(void)
{
float b = 1.17549435e-38f;
float a = nextafterf(b, 1.0f);
printf("a = %.4e\n", a);
printf("b = %.4e\n", b);
printf("a != b %s\n", a != b ? "true" : "false");
printf("a - b = %.4e\n", a - b);
printf("a - b == 0 %s\n",
a - b == 0.0f ? "true" : "false");
return0;
}
a = 1.1755e-38
b = 1.1755e-38
a != b true
a - b = 1.4013e-45
a - b == 0 false
remember
Their difference is smaller than the smallest normal float, so it lands in that hole.
It comes out nonzero, which means something lives in the hole after all.
The rule being protected: a minus b is zero only when a equals b. Numerical code assumes this everywhere.
Do not explain what fills the hole yet. Next slide.
What the all zero exponent actually means.
If the exponent field is all zeros and the mantissa is not zero, read the leading digit as 0 instead of 1, and hold the exponent at 2−126.
So the value is 0.mantissa × 2−126 rather than 1.mantissa × 2e.
remember
These are called subnormals.
They fill the hole with 8,388,606 evenly spaced values between zero and the smallest normal float.
The spacing down there is constant, the same 1.4013e-45 all the way.
The cost: each step down loses one bit of precision, because the leading zeros are not carrying information.
One of only two slides in the hour without a program. Keep it to two minutes.
Halve the smallest normal float, twenty four times.
/* 10-walk.c */#include<stdio.h>#include<string.h>void show(int step, float v)
{
unsigned u;
memcpy(&u, &v, 4);
printf("step %-3d ", step);
for (int i = 31; i >= 0; i--) {
putchar(u >> i & 1 ? '1' : '0');
if (i == 31 || i == 23) putchar(' ');
}
printf(" %g\n", v);
}
int main(void)
{
float v = 1.17549435e-38f;
for (int i = 0; i <= 24; i++) {
show(i, v);
v = v / 2.0f;
}
return0;
}
The exponent walks down until it hits zero and then stops.
After that the single 1 moves one place right per halving. That is the leading digit being lost.
Twenty four halvings from the smallest normal float to zero, which is exactly how many digits a float has.
Run the full output, not the abridged version on the slide. Watching all twenty five lines scroll is worth the ten seconds.
The same thing, one press at a time.
value
1.1754944e-38
family
normal
bits of precision
24
halvings so far
0
S
EXPONENT
MANTISSA
Give the button to a student. Twenty four presses.
Identical arithmetic, at two different magnitudes.
/* 11-speed.c */#include<stdio.h>#include<time.h>volatilefloat sink;
double run(float start)
{
clock_t t0 = clock();
for (int r = 0; r < 200; r++) {
float v = start;
for (int i = 0; i < 200000; i++)
v = v * 0.999f + start * 0.001f;
sink = v;
}
return (double)(clock() - t0) / CLOCKS_PER_SEC;
}
int main(void)
{
double normal = run(1.0f);
double tiny = run(1.0e-40f);
printf("normal numbers %.3f s\n", normal);
printf("subnormal numbers %.3f s\n", tiny);
printf("ratio %.1f times slower\n",
tiny / normal);
return0;
}
normal numbers 0.097 s
subnormal numbers 1.741 s
ratio 17.9 times slower
remember
Same instructions, same loop count. Only the size of the numbers is different.
A normal float has its leading one in a known place. A subnormal does not, so the hardware has to find it and shift.
On many processors that is not the fast path. Ten to a hundred times slower is normal.
A loop can slow down because the numbers got small, with no change to the code.
Run it on your own machine beforehand. The ratio varies and showing your own number is better than showing mine.
The same program, compiled twice.
$ gcc 09-guarantee.c -o g -lm
$ ./g
a != b true
a - b = 1.4013e-45
a - b == 0 false
$ gcc 09-guarantee.c -o g -lm -ffast-math
$ ./g
a != b true
a - b = 0.0000e+00
a - b == 0 true
remember
The flag switches on flush to zero, which throws subnormal results away rather than computing them.
The guarantee from program 9 is gone. Two values are unequal and their difference is zero.
Audio, graphics and machine learning code all do this, and are usually right to, because it is faster and most of the time nothing bad happens.
Two commands, live. Same source, same machine, two different answers about the same two numbers.
Now just count every pattern there is.
/* 12-census.c */#include<stdio.h>int main(void)
{
unsignedlonglong normal = 0, sub = 0,
zero = 0, inf = 0, nan = 0;
for (unsignedlonglong u = 0; u <= 0xFFFFFFFF; u++) {
unsigned e = u >> 23 & 0xFF;
unsigned m = u & 0x7FFFFF;
if (e == 0xFF) { if (m) nan++; else inf++; }
elseif (e == 0) { if (m) sub++; else zero++; }
else normal++;
}
printf("normal %12llu\n", normal);
printf("subnormal %12llu\n", sub);
printf("zero %12llu\n", zero);
printf("infinity %12llu\n", inf);
printf("not a number %12llu\n", nan);
printf("total %12llu\n",
normal + sub + zero + inf + nan);
return0;
}
normal 4261412864
subnormal 16777214
zero 2
infinity 2
not a number 16777214
total 4294967296
remember
Five families, and every one of the 4,294,967,296 patterns belongs to exactly one.
16,777,214 of them are NaN, so about sixteen million bit patterns name no number at all.
This is not a proof, it is a loop. The machine counted its own type in about three seconds.
Run it live. Three and a half seconds of silence while a machine enumerates every float that exists.
The 33,554,432 patterns we set aside at the start.
Add the last four rows on the board. 16,777,214 twice plus two plus two is 33,554,432, which is the number from slide three.
What a float looks like end to end.
Underflow was made gradual. Overflow was not. Ask which end they would have spent the patterns on if they could only afford one.
So: was 0.78% of the type a fair price?
what it bought
A value that says an overflow happened, instead of wrapping in silence like an int.
A value that says a question had no answer, and stays visible for the rest of the computation.
Zero, which the format otherwise cannot express at all.
8.4 million steps between zero and the smallest normal float, which keeps a minus b zero only when a equals b.
what it cost
33,554,432 patterns, of which sixteen million name nothing.
A slow path in the hardware that can cost a factor of twenty.
One bit of precision per step once you are in the subnormal range.
Two zeros, which have to compare as equal everywhere.
You have both columns now. Next session is what a float costs you in the middle, where none of this applies.
Do not tell them the answer. Take a vote if there is time.