15. Converting Decimal Fractions to Binary (And Why Some Never Terminate)

The concept

Lesson 14 Example 4 found 0.8125's bit pattern by trial: check whether each place value (1/2, 1/4, 1/8, ...) fits into what's left, same as Lesson 2's whole-number method. That worked because 0.8125 happens to be an exact sum of powers of two. Most decimal fractions aren't that cooperative, and trial-by-place-value doesn't scale to bit 20 either. What's needed is a mechanical procedure that works for any fraction at all.

Here it is: repeatedly double the fraction. Doubling a fractional value is exactly Lesson 6's left shift applied to the point instead of a whole number — it moves every position one slot more significant. If the doubled value is 1.0 or more, that means the position now sitting just left of the point held a 1; record a 1 bit, subtract the 1 back off, and keep going with what's left. If the doubled value stays under 1.0, record a 0 and keep going with the whole thing. Read the bits in the order they were produced.

Some fractions never hit a remainder of exactly 0, no matter how long you keep doubling — the process just repeats the same block of bits forever. This isn't a flaw in binary; the same thing already happens in decimal. 1/3 = 0.333... never terminates either. A fraction terminates in a given base exactly when its denominator's prime factors all divide that base: decimal's base is 10 = 2 x 5, so any fraction reducing to a denominator built only from 2s and 5s terminates (tenths, fifths, twentieths); 1/3 doesn't, because 3 is neither. Binary's base is 2, with only one prime factor, so only denominators built from 2s alone terminate — halves, quarters, eighths, sixteenths, and so on. Plenty of ordinary, clean-looking decimal fractions (0.1, 0.2, 0.3) fail that test and repeat forever in binary.

Example 1 — doubling a fraction that terminates: 0.375

0.375 x 2 = 0.750   ->  bit 0   (stays under 1, keep 0.750)
0.750 x 2 = 1.500   ->  bit 1   (crossed 1; subtract, keep 0.500)
0.500 x 2 = 1.000   ->  bit 1   (crossed 1; remainder is 0 — done)

Reading top to bottom: 0.011. This is the same value Lesson 14 Exercise 2 built by the place-value trial method (5.375's fractional part) — the two methods agree, as they must.

Example 2 — doubling a fraction that never terminates: 0.1

0.1 x 2 = 0.2   ->  bit 0
0.2 x 2 = 0.4   ->  bit 0
0.4 x 2 = 0.8   ->  bit 0
0.8 x 2 = 1.6   ->  bit 1   (remainder 0.6)
0.6 x 2 = 1.2   ->  bit 1   (remainder 0.2 — already seen after step 1)

Once a remainder repeats, the process is trapped: doubling 0.2 always produces the same next steps, forever, because the procedure is entirely determined by the current remainder alone. 0.1 in binary is 0.0001100110011..., the block 1100 repeating without end. There is no exact binary bit pattern, of any length, equal to one-tenth.

Example 3 — why 0.2 never terminates

0.2 reduces to 1/5. Its denominator's only prime factor is 5, which never divides 2, so the termination rule from the concept section already predicts this will repeat before any doubling happens at all. Confirming it:

0.2 x 2 = 0.4   ->  bit 0
0.4 x 2 = 0.8   ->  bit 0
0.8 x 2 = 1.6   ->  bit 1   (remainder 0.6)
0.6 x 2 = 1.2   ->  bit 1   (remainder 0.2 — back to the starting value)

The remainder returned to 0.2 itself — the exact value doubling started with — so the whole four-step block repeats from here on with nothing left over, ever: 0.2 = 0.0011001100110011.... Compare against 0.375 (Example 1) or 0.8125 (Lesson 14 Example 4, 0.1101): both of those reduce to a denominator that's a power of two alone, which is exactly why they terminated and 0.2 doesn't.

Example 4 — what a machine actually stores: truncating 0.1 to 8 bits

Example 2 showed 0.1 repeats forever, but no machine has infinite bits. Suppose only 8 bits after the point are available — take the first 8 bits of 0.1's expansion and stop:

0.1's expansion:     0.0001100110011...
first 8 bits kept:   0.00011001

Reading those 8 bits back by place value (Lesson 14's method): 1/16 + 1/32 + 1/256 = 0.0625 + 0.03125 + 0.00390625 = 0.09765625. The machine doesn't store 0.1 at all — it stores 0.09765625, off by 0.1 - 0.09765625 = 0.00234375. More bits would shrink that error, but never make it exactly 0, since the true expansion never terminates. This is a genuinely practical consequence, not a curiosity: it's a first look at why fixed-width fractional storage (and, later, floating point) can't represent every decimal value exactly, no matter how many bits are spent.