Hi Friends,
Welcome to the 195th issue of the Polymathic Engineer newsletter.
This week, we will start talking about floating-point numbers.
Let’s be honest: every software engineer has struggled with them at some point. You open a Python shell, type 0.1 + 0.2, and the answer is 0.30000000000000004. You compare 0.1 + 0.2 == 0.3 and get False. And this occurs in pretty much every language.
But this behavior is neither broken nor random. The outcome arises immediately from how the numbers are stored in memory. If you understand the representation, then all the weirdness of floats is predictable, and you can tell in advance when a computation is going to bite you.
In this issue, we build a floating-point number from the ground up: why the binary point has to move, why some fractions can’t be written in binary at all, how the bits are laid out, and what happens when a value doesn’t fit.
The outline is as follows:
Why the point has to float
Fractions in binary
The IEEE 754 layout
Normalized, denormalized, and special values
Rounding
CodeCrafters is a great platform for learning technical skills. You can build your own version of Redis, Kafka, DNS server, SQLite, or Git from scratch using whatever programming language you wish.
Why the point has to float
Integers are the simplest numbers a computer can store, but they, of course, cannot represent any fractional values. Fixed-point formats provide the ability to represent fractional values, but at the expense of the range of integer values you can represent.
You take a binary number and decide that the point sits at a fixed position. For example, with 16 bits you could use 8 bits for the integer part and 8 bits for the fractional part of the number. The integer part can represent values in the range from 0 to 255, and the fractional part can represent the multiples of 1/256. You don't need any hardware support. You add and subtract fixed-point numbers like integers, and only you know where the point is.
The problem is that the split is fixed. Suppose that for a sequence of calculations you only need 2 bits to represent the fractional values, enough for 0.0, 0.25, 0.5, and 0.75. Unfortunately, the other 6 bits in the fractional part go to waste. Wouldn’t it be better to use them in the integer part, extending its upper bound from 255 to 16,383? The opposite happens too for calculations that need a lot of precision below 1 and little above. Well, the floating-point representation exists basically to solve such challenges.
In a floating-point value, the binary point can float between digits in the number as needed. If you need only 2 bits of precision for the fractional component, the point moves down, allowing the format to utilize bits 2 through 15 for the integer portion. If you need many fractional bits, the point moves up. To support the format, the numeric representation needs one extra field: a field that specifies where the point is within the number.
That extra field is equivalent to the exponent when using scientific notation. When you write 9,876,543,210 as 9.88 × 10^9, you keep a few significant digits and a power of ten that tells you where the point goes. Floating-point formats represent real numbers in the same way. They use some number of bits to represent a mantissa and a smaller number of bits to represent an exponent. The mantissa is a base value that usually falls within a limited range (e.g., between one and two). The exponent is a multiplier that, when applied to the mantissa, produces values outside this range. The standard refers to the mantissa as the significand, but most engineers still refer to it as the mantissa, and that’s what we’ll do here.
The consequence of splitting the number into these two parts is that floating-point numbers can only represent numbers with a specific number of significant digits. Let’s consider a toy decimal format: a mantissa with 3 significant digits and a 2-digit exponent, both signed. This format can represent values across a wide range (as large as 9.99 × 10^99). However, it cannot represent all the values in this range exactly, since that would take 100 digits. 9,876,543,210 becomes 9.88 × 10^9, which is 9,880,000,000, off by about 3.5 million. On top of that, the format wastes some of its bit patterns, since it can provide multiple representations for the same value. For example, 1.00e+1 and 0.10e+2 are different representations of the same value. Every float works the same way: the exponent buys you range, and the mantissa sets how many digits you can trust.
Fractions in binary
The first step to understanding floating-point numbers is to consider binary numbers that have fractional values. Let’s first look at the more familiar decimal notation. In a number like 12.34, the weighting of the digits is defined relative to the decimal point symbol, meaning that digits to the left are weighted by non-negative powers of 10, giving integral values, while digits to the right are weighted by negative powers of 10, giving the fractional part: 1 × 10 + 2 × 1 + 3 × 1/10 + 4 × 1/100.
Binary numbers work the same way, with powers of two. The symbol “.” now becomes a binary point. The positions to the left of it are weighted by 1, 2, 4, 8, and so on, and the positions to the right by 1/2, 1/4, 1/8, and so on. For example, 101.11 represents 1 × 4 + 0 × 2 + 1 × 1 + 1 × 1/2 + 1 × 1/4, which is 5.75.
Notice what happens if you shift the binary point. One can easily see that moving the binary point one position to the left has the effect of dividing the number by 2: 10.111 is 2.875. Similarly, moving the binary point one position to the right multiplies the number by 2: 1011.1 is 11.5. This is the mechanism behind the floating point of the previous section. Moving the point is the same as multiplying or dividing by a power of two, which is precisely what the exponent does.