Gregory Friedman The Greg Wide Web on the name →

Case Study · CS · Number Systems

Bases

2024 · demo · repository

The idea

Bases began as a small Python exercise: a Number class that could read an integer written in any base and write it back in any other, all the way from binary up to base-64. The whole project rests on a single observation that is easy to say and easy to forget, which is that a base is nothing but a choice of how many symbols you are allowed before you have to carry. We happen to carry at ten because of an anatomical accident, but the number itself does not care. Nineteen hundred and twelve is 19121912 in decimal, 778778 in hexadecimal, and 1110111100011101111000 in binary, and these are not three different numbers; they are three spellings of one quantity, each using a different-sized alphabet.

The alphabet is the reason the ceiling is sixty-four. Digits run through the ten Arabic numerals, then the twenty-six uppercase letters, then the twenty-six lowercase, then + and /: sixty-four symbols in all, which is exactly the character set that base-64 encoding uses to smuggle binary data through text-only channels. Past that we would simply run out of things to write with. The plate below is the converter itself, ported from the original class and running entirely in your browser.

= 778

The same number written in seven familiar bases.
BaseNameRepresentation
2 binary 11101111000
8 octal 3570
10 decimal 1912
12 duodecimal 1134
16 hexadecimal 778
60 sexagesimal (Babylon's) Vq
64 base-64 Tu
Plate I Any integer, respelled. Type a number, choose the base it is written in and the base you want it in, and read the result along with the same value in seven familiar bases. When one base is a power of the other, the fast path appears: no division, just regrouping.

How it works

Conversion is one positional identity read in two directions. A string of digits dkdk−1…d1d0d_k d_{k-1} \dots d_1 d_0 in base bb denotes the value

dkbk+dk−1bk−1+⋯+d1b+d0,d_k b^k + d_{k-1} b^{k-1} + \cdots + d_1 b + d_0,

and both halves of the converter are just this equation rearranged. Reading a number in folds that sum with Horner’s rule, one digit at a time: start an accumulator at zero and, for each new digit, multiply what you have by the base and add the digit. Writing a number out runs the same identity backward by repeated division: the remainder modulo bb is the last digit, and dividing by bb shifts everything down one place, so peeling remainders off from the bottom rebuilds the digit string in reverse. Neither step ever needs to know the “value” of the number in some privileged base; decimal is not special here, only familiar.

The one liberty the port takes with the original is arithmetic width. JavaScript’s ordinary numbers lose precision past 2532^{53}, so the whole thing runs on BigInt, which means the converter is exact for integers of any size you care to type rather than quietly rounding a large hexadecimal value. That change is invisible until you need it, and then it is the difference between a right answer and a plausible one.

The nicest part is a shortcut hiding in the arithmetic. When one base is an exact power of the other, conversion needs no division at all. Because 16=2416 = 2^4, every hexadecimal digit is exactly four binary digits, so you can convert between the two by grouping or unfolding four bits at a time, reading each group off a tiny lookup rather than dividing anything. The same is true for octal (8=238 = 2^3) and for base-64 (64=2664 = 2^6), which is precisely why those bases exist as human-readable stand-ins for raw binary. The plate detects the relationship and shows the regrouping whenever it applies, because watching 11101111000 fall into the groups 0111 0111 1000 and become 778 is a better argument than any paragraph that these really are the same number.

Where negative numbers live

Everything so far handles magnitudes: the digits say how big, never whether. On real hardware a number lives in a register of fixed width, say eight or thirty-two bits, with no slot for a minus sign, so representing negatives means spending one of the bits you have. The convention that won is two’s complement, and it is worth seeing because it is both clever and, at first, slightly uncanny.

The idea is to let the top bit carry a negative place value. In an eight-bit number the leading bit is worth −27=−128-2^7 = -128 instead of +128+128, and every other bit keeps its usual positive weight. So 11010110 reads as −128+64+16+4+2=−42-128 + 64 + 16 + 4 + 2 = -42: the same positional sum as always, with one sign flipped. This is why the top bit is called the sign bit, and why a 1 there always means negative. To negate a number you flip every bit and add one, a recipe that looks arbitrary until you notice that flipping all the bits computes −1−x-1 - x in this weighting and the +1+1 corrects it back to −x-x. The plate below runs that recipe live.

Bit width

-42 in 8-bit two's complement is 11010110. The leading bit is the sign bit; here it is 1, so the value is negative. The sign bit carries weight -128, so 11010110 reads as -128 + 86 = -42.

The two encodings

ones' 11010101 = 213 unsigned
two's 11010110 = 214 unsigned

The sign bit is tinted. Flip every bit of one row to get the other; the two's-complement row is the ones'-complement row plus one.

Negation: flip, then add one

+42 00101010 the magnitude
flip 11010101 ones' complement
+1 11010110 = -42
Plate II A number, signed. Pick an integer and a bit width; the plate shows its ones'- and two's-complement patterns with the sign bit tinted, then derives the negative by flipping every bit and adding one. Watch the two's-complement row appear as the ones'-complement row plus one.

The plate shows two encodings, because two’s complement has an older and simpler sibling. Ones’ complement negates a number by flipping its bits and stopping there, with no +1+1. It is easier to explain and was easier to build in early hardware, but it pays for that simplicity twice: it has two different zeros, an all-zeros +0+0 and an all-ones −0-0, and its addition needs an “end-around carry” that folds the overflow bit back into the low end. Two’s complement absorbs both problems. It has a single zero, and ordinary binary addition just works across the sign boundary with no special case, which is exactly why it is what your processor actually uses. The one asymmetry it keeps is a curiosity worth pointing at: an eight-bit two’s-complement byte reaches from −128-128 to +127+127, one more negative value than positive, because the extra pattern that ones’ complement spent on a second zero is here a usable number.

Where the real numbers go wrong

Everything above is exact. An integer has a bit pattern, the bit pattern has a value, and the two agree perfectly at every width. Real numbers are where that stops being true, and the place it stops is worth looking at directly, because almost every programmer meets the consequence years before they meet the cause.

An IEEE 754 double is three fields in sixty-four bits: one sign bit, eleven exponent bits, and fifty-two mantissa bits, read as

(−1)s×1.m×2 e−1023,(-1)^{s} \times 1.m \times 2^{\,e - 1023},

where the leading 11 is implicit and never stored, which buys a free bit of precision. The exponent is biased rather than signed: the stored field is the true exponent plus 1023, so the range −1022-1022 to +1023+1023 is written as 1 to 2046. That choice looks arbitrary and is not. Because the bias keeps the field monotonic, two positive floats compare correctly when you compare their bit patterns as ordinary unsigned integers, which is a small and genuinely elegant piece of design: the hardware gets integer comparison for floats at no cost. The reserved field values at each end pay for it, and buy something back. An all-zeros exponent means there is no implicit leading one, which gives the subnormals, the numbers that fill the gap between the smallest normal float and zero so that a−b=0a - b = 0 implies a=ba = b. An all-ones exponent gives the infinities and the NaNs.

The mantissa is the part that bites. Fifty-two bits after an implicit one is a binary fraction, and a binary fraction can only represent numbers whose denominators are powers of two. One tenth is not one of them: in binary, 0.10.1 is the repeating expansion 0.00011‾0.0\overline{0011}, exactly as 1/31/3 repeats in base ten, and for exactly the same reason. Ten has a factor of five in it, and five is not a power of two. So 0.10.1 is rounded to the nearest double before your program has done anything at all with it, and that nearest double is

0.1000000000000000055511151231257827021181583404541015625,0.1000000000000000055511151231257827021181583404541015625,

which is not an approximation of the stored value. It is the stored value, written out in full. Every finite float is an integer times a power of two, so every finite float has a terminating decimal expansion; it is just far longer than the number you typed. The plate below prints it, using exact big-integer arithmetic rather than floating-point, because a figure about rounding error that computed its own numbers in floating point would be telling you what it was supposed to be showing you.

Format
Specimens

A normal binary64 number. The sign bit is 0, so the value is positive. The exponent field reads 1019; taking off the bias of 1023 leaves an exponent of -4, and the 52 mantissa bits are the fraction after an implicit leading 1. The stored number is exactly 7205759403792794 times 2 to the -56.

The bits, as stored. Click any bit to flip it.

Sign · 0 · positive Exponent · field 1019 − bias 1023 = exponent -4 Mantissa · 0x999999999999A · after an implicit leading 1

0x3FB999999999999A

What those bits mean

Binary scientific
+1.100110011001100110011001100110011001100110011001101₂ × 2⁻⁴
As an integer times a power of two
7205759403792794 × 2⁻⁵⁶
Printed by JavaScript
0.1
Exact decimal value
0.1000000000000000055511151231257827021181583404541015625

Every finite float is an integer times a power of two, so its value in base ten always terminates. It is usually much longer than the decimal that produced it.

What rounding cost

You typed
0.1
Stored
0.1000000000000000055511151231257827021181583404541015625
Difference
0.0000000000000000055511151231257827021181583404541015625
Gap between neighbours here (one ULP)
1.3877787807814457e-17
Miss, in ULPs
0.4000

The stored value is above the decimal you typed. Correct rounding guarantees the miss is at most half the local gap, and no decimal whose denominator has a factor other than 2 can do better.

Why 0.1 + 0.2 is not 0.3

0.1 is stored as
0.1000000000000000055511151231257827021181583404541015625
0.2 is stored as
0.200000000000000011102230246251565404236316680908203125
Their exact sum
0.3000000000000000166533453693773481063544750213623046875
Rounded back to a double
0.3000000000000000444089209850062616169452667236328125
But 0.3 is stored as
0.299999999999999988897769753748434595763683319091796875
So they differ by
0.000000000000000055511151231257827021181583404541015625

Neither 0.1 nor 0.2 nor 0.3 is representable, so all three are already approximations before any addition happens. Their exact sum needs 54 significand bits, more than the 53 a double has, so it is rounded once more, and it lands on the double next door to the one 0.3 rounds to. JavaScript prints the result as 0.30000000000000004. This is not a JavaScript defect: every language with binary floats does the same thing, and the ones that appear not to are hiding it at the printing step.

Plate III A decimal, dissected. Type a number and watch the sixty-four bits it becomes: sign in ochre, exponent in green, mantissa plain. Every reading is derived from the bits, not from what you typed, including the exact decimal value, which terminates for every float and is usually much longer than the input. Click any bit to flip it and the value follows the pattern rather than the other way round; flip the top exponent bit and watch the magnitude jump by a factor of 2^512. The last panel works out 0.1 + 0.2 in exact arithmetic, so the most famous rounding error in programming stops being folklore and becomes six lines of visible cause.

The final panel is the one worth sitting with. It is tempting to say that 0.1+0.20.1 + 0.2 fails because addition is lossy, and that is not quite the story. All three of 0.10.1, 0.20.2 and 0.30.3 are already wrong before any arithmetic happens, each rounded to its own nearest double. The exact sum of the first two stored values needs fifty-four significand bits, one more than a double has, so it is rounded a second time, and it lands on the double immediately next to the one 0.30.3 rounds to. Two roundings, two different destinations, one adjacent pair of representable numbers. The comparison fails by a single ULP, the smallest possible amount, which is why it is so hard to notice and so annoying to debug.

None of this is a defect in JavaScript, and it needs saying plainly because the internet insists otherwise. Every language with binary floating point does the same arithmetic and gets the same bits; the languages that appear not to are formatting the output more aggressively at the printing step, which hides the cause rather than removing it. The real fixes are the same everywhere: compare with a tolerance, or move to a representation whose base matches your data, which for money means integer cents or a decimal type, since currency is defined in base ten and storing it in base two is a category error rather than a precision problem.

What the port added

The original class converted unsigned magnitudes across bases, and the browser port is where the project grew into the subject it was always adjacent to. Two additions carried the most weight. The first was the power-of fast path, which turned the converter from a calculator into an explanation: once you can watch hexadecimal be binary in groups of four, the relationship between the bases stops being a rule to memorize and becomes something you can see. The second was signed integers, which took the project from “how big” to “how big and which way” and pulled in the one genuinely surprising idea in elementary number representation, that you can make subtraction fall out of addition just by choosing the right weighting for a single bit.

Moving to exact BigInt arithmetic was the quiet decision that made the rest trustworthy: a converter that rounds is not really a converter, and doing the math in arbitrary precision meant the demo could make claims a viewer can check to the last digit. What I take from the project is how much depth a deliberately small program can hold. Positional notation is the same identity that Horner’s method evaluates and that radix sort exploits; the sign bit is a first lesson in modular arithmetic wearing work clothes. A converter is a small thing to build, and it holds far more of the subject than its size suggests.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.