A Deep Dive Into Fixed Point Arithmetic: Part 1

Numbers are cool. Did you know there are a lot of them? They can go like, really big. Huge, even. On top of that, add in a minus and you practically doubled the amount there are! What’s more? Take any two of them, say, 1 and 2, and you’ll find there are lots of numbers between these numbers.

Like, one-and-a-half (1.5)? sure! 1.51? why not! π over 2? let me check… yes!

Man, numbers… what can’t they do?

(This post is the first part of a multipart series on fixed point arithmetic and how you can use it today to build extremely efficient programs. I will add links to the other parts when they are done. If you already know how fixed point arithmetic works in general, and only want to see source code, you can skip this part (and maybe even the next one).)

How Humans Math

Assuming you’re not a large language model, you learned in elementary school that the way we write numbers larger than 9 is by adding a new digit to the left, quietly assuming the value represented by the new digit is “tens of”… things, like apples, but usually stackable, colored, plastic blocks. So we learn to count: 8, 9, 1 of ten (or just “ten”), 1 of ten and 1 (“eleven”, or “onety-one”), 1 of ten and 2 (“onety-two”) and so on. The same happens when we reach the hundreds, thousands and so on.

Later we learn that we, in addition of multiplying by ten when going to larger values, can also divide by ten to create values smaller than “one”. We express this with a point (or comma in some locales, annoying the wranglers of csv files for half a century now), adding digits to the right representing tenths, hundredths, thousandths. An enterprising teacher with a hacksaw notwithstanding, this is not taught using those same plastic blocks. Nevertheless, we learn to then express the concept of “half an apple” by instead saying “the amount of apple is 5 times one-tenth of an apple”, which every child adapts to naturally.

So, to recap, in modern everyday (“base 10”) arithmetics, we use numbers comprised of the digits 0 through 9, and assign each digit a base value of 10-to-the-power-of the position of the digit, starting at zero, increasing the exponent by 1 to the left, and decreasing it by 1 to the right. To indicate the position of the 10 to the power of 0 digit, the “one”, we mark it with a point. To avoid unnecessary noise, we don’t put a point when there are no digits with values of negative powers of ten, and assume that the rightmost digit is the “one”.

For example, the number “two-hundred fifty-seven and three tenths”, given as sum over the powers of the base 10:

Can be represented concisely using the decimal notation: $257.3$

Armed with that knowledge and throwing in some SI-prefixes for good measure, we might not be able to emotionally handle whatever modern life throws at us, but at least we can count it and write it down.

Much later, when we learn how to embark on scientific endeavors, we are confronted with having to conceptualize really large or really small numbers. For example, when calculating the numbers of atoms in a gram of a given substance, you will need to use the Avogadro constant, which is in the order of magnitude tens of a thousand of a million of a million of a million. To not look and sound stupid, we learn to use (or, in some cases, tolerate) the so-called scientific notation: By extracting the magnitude of the most significant digit into a multiplication with the power of 10 to the magnitude, effectively re-scaling the number’s digits to the “one” position, we gain the ability to write only the most significant digits in a very large (or small) number, and banish the less signifiant digits to the realm of rounding.

In other words, we “shift” the “one” to the most significant digit, and indicate the actual value of the “new one” digit by a multiplication with the digit’s original magnitude.

Avogadro’s number can thus be expressed as $\mathrm{6.022\; 140\; 76\; \times \; 10²³}$

Or, using the the notation you might be familiar with from when your pocket calculator starts screaming at you: 6.022E23

"EEEEEEE!"

As an aside, I remember as a kid feeling a bit disappointed that my calculator would not go beyond E99. Turns out, that’s a very large number. You might even call it “stupid large”. For example, the units of Planck-Time (5.4E-44 seconds, the shortest possible increment of time) that have passed since the Big Bang (13.8 billion years ago, or 4.355E17 seconds) has a magnitude in the ballpark of just 10⁶²¹. I am now cured of this greed.

An Excursion Into Base-10 Arithmetic, or: “Can You Fit This On a Napkin?”

I just did a bit of a magic trick there. Did I really enter these very small (Planck time) and very large (age of the universe) numbers into a calculator (“EEEEEE!”), dividing one by the other, to find the order of magnitude? I, in fact, did no such thing. There is a rule we can use, that we will meet again later in more depth, but I want to motivate it here, since we won’t be in base-10 when we meet it again later.

When multiplying two decimal numbers given their scientific notational form $\mathrm{a\; \times \; 10^A}$ and $\mathrm{b\; \times \; 10^B}$, we can assume the resulting value in scientific notation has the exponent $\mathrm{A\; +\; B\; (+\; 1)}$ with the additional one being the carry of the multiplication of $\mathrm{a\; ·\; b}$.

This leads to a couple of things we can notice right away:

• When you multiply a number with itself, you generally get “double the exponent” for the most significant digit.
• Negative exponents are handled the same way, “reducing” the exponent of the result.
• When you multiply a number with a number that has the “inverse magnitude” ($\mathrm{a^A\; ·\; b^-A}$) the result has the exponent zero (or one, in case of a carry-out).
• Yes, this is strongly related to the way that multiplication in linear space becomes addition in a logarithmic space.
• Division is handled like multiplication but with a negative exponent, and a carry leading to a reduction by one.

I can also give you a related rule about addition:

When adding two decimal numbers given their scientific notational form $\mathrm{a\; \times \; 10^A}$ and $\mathrm{b\; \times \; 10^B}$, we can assume the resulting value in scientific notation has the exponent $\mathrm{max(A,\; B)\; (+\; 1)}$ with the additional one being the carry of the addition of $\mathrm{a\; +\; b}$ if $\mathrm{A\; =\; B}$. Intuitively, we know this from the observation that when you have a lot of a thing, adding a little of a thing leaves you with still only a lot of the thing, and not a lot more.

The case of subtraction is a bit less intuitive, but you will find that this turns $\mathrm{max(A,\; B)}$ into an upper bound for the exponent’s result.

Given these observations, we find that we can determine the upper bound of the number of digits occuring in the result of an operation, only from the number of digits of the operands. So if someone asks you if you can fit a given formula on a napkin, or the back of an envelope, you can now give a confident and informed answer.

In the next part, we will look into how these rules shape how computers came to represent numbers of all kinds big or small.