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:

• Speed: If you're using a processor that doesn't have fast floating point hardware, such as the ARM or the Microchip PIC or the Atmel AVR or the Intel 386 (without a coprocessor), floating point is slow compared to fixed point or integer math.
• Space: the fundamental operations on floating point numbers (add, subtract, multiply, divide) each require a big chunk of program space. Fixed point or integer math can do those operations in less program space. (Note that this only needs to be done once, though -- if you have 20 divides in your program, they all call the one divide routine, and those 20 calls take the same space no matter if you choose floating-point or fixed-point).

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:

• Wikipedia: Fixed-point arithmetic
• j_doin explains fixed-point math
• Microchip AN617: Fixed Point has lots of nice code
• Microchip AN575: IEEE 754 Compliant Floating Point Routines ""in a modified IEEE 754 32-bit format together with versions in 24-bit reduced format." ... "float to integer conversion,integer to float conversion,normalize,add/subtract,multiply,divide.
• Microchip AN660: Floating Point Routines "in a modified IEEE 754 32-bit format together with versions in 24-bit reduced format." ... "square root function, exponential function, base 10 exponential function, natural log function, common log function, trigonometric sine function trigonometric cosine function trigonometric sine and cosine functions power function, floor function, largest integer not greater than x, as float, floating point logical comparison tests"
• Fixed Point Fractions and Arithmetic by Douglas W. Jones
• IEEE-754 Floating-Point Conversion
• Two's Complement and Binary Math by Andrew Warren (includes "SUBTRACTION: ADDITION'S EVIL TWIN" )