Quick explanation/tutorial on fixed point math

There has to be plenty of articles that are much better than that one. It sucks. Fixed-point math is pretty simple. Here is a quick summary.

A fixed-point number is an integer that represents a number consisting of a whole part (e.g. 3) and a fractional part (e.g. .14159). The format of a fixed-point number is usually described as "m.n", where m is the number of bits in the whole part and the n is the number of bits in the fractional part. m + n is the total number of bits. For example, "8.24" means a 32-bit integer with an 8-bit whole part and a 24-bit fractional part. To convert a number to fixed point you just multiply it by 2ⁿ. So, 3.14159 as a 8.24 fixed point number is 52707134 (or 0x03243f3e). To convert a fixed point number back, just divide by 2ⁿ. Think shift left n bits and shift right n bits. So that is how they are represented. Now for the math...

Suppose A, B, and C are the fixed-point versions of a, b, and c.

A = a * 2ⁿ
B = b * 2ⁿ

Addition: if c = a + b, then

C = (a + b) * 2ⁿ = (a * 2ⁿ) + (b * 2ⁿ)
C = A + B

In other words, to add two fixed point numbers, you just add them. Subtraction works the same way.

Multiplication: if c = a * b, then
C = (a * b) * 2ⁿ = (a * 2ⁿ) * (b * 2ⁿ) / 2ⁿ
C = A * B / 2ⁿ

In other words, to multiply two fixed point numbers, you multiply them and then divide by 2ⁿ (or shift right n bits). Note that overflow is a problem that has to be dealt with.

Division: if c = a / b, then
C = (a / b ) * 2ⁿ = (a * 2ⁿ) / (b * 2ⁿ) * 2ⁿ
C = A / B * 2ⁿ

In other words, to divide two fixed point numbers, you divide them and then multiply by 2ⁿ (or shift left n bits). Note that underflow is a very serious problem which is usually dealt with by rearranging the order of operations like this:

C = A * 2ⁿ / B

Again, you have an overflow problem that has to be dealt with.

The easiest and safest way to deal with overflow is to use a larger integer size to store intermediate values. For example, you might use 64-bit numbers to do 8.24 fixed-point math. The drawback is that it can be slower, or there might not be a larger integer size available. You could also be clever with rearranging the math (like we did with the divide operation), but that could have drawbacks. If you don't have a larger integer size, you will probably have to use multiprecision math.

I hope this was clear.

[edited by - JohnBolton on March 20, 2004 3:10:17 PM]

Ok, heres the deal with fixed point math. Its an old trick that is very useful on chips without good floating point units. Normally, the computer stores floating point numbers using some exponental techique I don't remember right now. Anyway, it takes longer for the CPU to do floating point math than integer math. Thats where fixed point math comes in. Fixed point math is just a way to make the decimal stay at the same place all the time, so the CPU doesn't have to spend cycles doing conversions.

How to do fixed point math.

1) Choose where the decimal should be. Remember, computers work in binary, so this should always be a power of two.

2) To convert a float to a fixed point number, mulitply by #1

3) Since you picked a power of two, there is a shortcut for converting ints to fixed point numbers. You can shift the bits of the number to the left (<<). The shift is always log base 2 (#1).

4) To convert back, simply shift right (>>) log base 2(#1)

5) Addition and subtraction are done the same way normal addition and subtraction are done

6) Muliplication shifts the decimal too many digits to the left. Thus after muliplication, you must shift digits right (>>) by log base 2(#1)

7) Division shifts the decimal right to many digits. Shift left (<<) by log base 2(#1)

Fixed Point Tutorial


[edited by - Onemind on March 20, 2004 1:38:21 AM]