Fixed-point routines

Massmind: Methods: Math: Fixed Point Math

Can fixed point math do anything that you can't do with floating point math? No. So why bother?

2 reasons:

So what *is* fixed point math?

It's more a state of mind than something you can really point to. It's a way of using integer math but later *interpreting* the results as non-integers.

Chances are you've used fixed point math without even realizing it: in dollar prices. When you see something priced at $19.99 or $20.01 , it appears to be a fractional amount (of dollars).

But really, whenever you actually pay for something in cash, you end up paying an integral number of pennies, right?

So we can just think of "$19.99" as a peculiar way of formatting the integer value "1 999 pennies", and "$20.01" as the same peculiar way for formatting the integer value "2 001 pennies", right? They both mean the same thing.

So it is with the vast majority of things we deal with in software. There may be some "traditional unit" (analogous to the dollar), but we want finer resolution than 1 of those units. So we figure out how much resolution we *really* need, and make up some new "mythical unit" that's much smaller than the traditional unit.

For example, Instead of measuring angles in terms of "1 rotation" (where we often have "0.5 rotation" = "half turn" and "0.25 rotation" = "quarter turn"), we pick some smaller unit we call the "degree" (so we have the integer "180 degrees" and "90 degrees"). Many times measuring angles to the nearest degree gives plenty of accuracy.

Quite often it simplifies our software if this smaller unit is exactly 2 or 4 or 8 times the larger unit -- some power of 2. (256 times is an especially popular choice, because then the bottom byte of the integer holds the "fractional part", and the rest of the integer holds the "integer part").

Now that I've thoroughly confused you, I need to introduce "Q notation".

[FIXME: put well-written, understandable, yet concise explanation of "Q notation" here.] ...

OK, say I have a byte, and I want it to represent distances somehow related to inches.

My options are:

Q8:0 -- the byte represent integer inches from 0 inch, 1 inch,
  ... 255 inches.
Q7:1 -- the byte represents 0 inch, 1/2 inch, 1 inch, 1+1/2 inch,
  ... 127+1/2 inch.
Q6:2 -- the byte represents 0 inch, 1/4 inch, 1/2 inch, 3/4 inch, 1 inch, 1+1/4 inch,
  ... 63+3/4 inch.
...
Q1:7 -- the byte represents 0 inch, 1/128 inch, 2/128 inch, 3/128 inch,
  ... 1+127/128 inch. (This gives 128 "mythical units" per inch).
Q0:8 -- the byte represents 0 inch, 1/256 inch, 2/256 inch, 3/256 inch,
  ... 255/256 inch.

Q: So which option do I pick? A: Any that gives adequate precision, while also giving a long enough range.

Q: OK, say I need quarter-inch resolution, and I need to measure at least 100 inches long. Which option do I pick? A: There are many options that would work. The most popular choice is to put the integer part in one byte, and the fractional part in the next byte. (Can you see why I don't use a single byte?). So we have

Q8:8
 00 00 = 0 inches
 00 40 = 1/4 inch
 00 80 = 1/2 inch
 00 C0 = 3/4 inch
 01 00 = 1 inch
 01 40 = 1+1/4 inches
 ...
 7F C0 = 127+3/4 inches

The process of mentally keeping track of exactly where the "binary point" is while manipulating fixed-point numbers, is very similar to the process of mentally keeping track of the "decimal point" while calculating on a slide rule.

External links:

(started 2005-10-24 by David Cary)