MathFP

- The Basics -

Introduction

This page describes the basic theory for the fixed point integer math used in the MathFP Java library. The following topics will briefly be discussed:

The Fixed Point

Fixed point integers are basically numbers where the position of the decimal point is fixed. It is as simple as that. For example lets fix the decimal point in a decimal system to allow numbers that are as small as 1/10000. This means that every number we will deal with must have 4 digits behind the decimal point even if there is no fractional part. So if we want to refer to the number 2 then the fixed representation is 2.0000. If you don't have fractions available (e.g. you can only work with integers) then we can think of 2.0000 as 20000 divided by 10000.
So internally we would store the decimal number 2.0000 as 20000 and when we need to display the value we can just take the last four digits as the fraction.

With a binary number we will do exatly the same. Just determine the precision you want and virtually place the decimal point at that position in the binary number. Lets take the following binary number:

00000000000000000000000000000010

Its fixed point integer number using 12 bits for the fraction will be:

00000000000000000010.000000000000 (notice the virtual "binary" point)

So any natural number n that we want to represent as a fixed point integer will be multiplied by a number f that is equal to two to the power of the fractional precision (this is 2 ^ fractional bits).

n * f = nf

The Basic Math Operations

The advantage of this storage format is that we can just do all the basic calculations without any major effort. For example adding and subtracting do not involve any additional code just add or subtract two fixed point numbers.
The next two paragraphs explain how the four basic math operations are implemented in its base form. Each paragraph starts of with two natural numbers and then shows what the end result should be if we converted the known end result to a fixed point integer as explained in the previous paragraph.

Add and Subtract

Lets say we have two natural numbers n and m. The addition of these two numbers would be n + m which in fixed point notation would be

( n + m )f = nf + mf

and similar for subtraction

(n - m )f = nf - mf

This means no adjustments have to be made at all. Just add and subtract fixed point integers.

Multiply and Divisions

Again we have the two natural numbers n and m. Their multiplication would be equal to n * m. The fixed point represetation for this multiplication is (n * m) f. However if we just multiply two fixed point integers we get nf * mf = n * m * f^2. This is a factor f too much. To correct this we must divide the result by f. So the multiplication of nf and mf (two fixed point integers) equals to:

(nf * mf ) / f = (n * m) f

Division works almost the same way. Again take two natural numbers n and m. Their division fixed point integer representation would be (n / m) * f. If we just divide two fixed point integers we get nf/mf which is n/m. This is obviously incorrect. In order to fix this we must multiply the result by f. So the division of two fixed point integers is:

(nf / mf) * f = (n / m) * f = (nf*f)/mf

It is easy to see that we want to multiply the fixed point integer nf by f first to maintain the highest precision.

Overflows

It is easy to see that nf * mf or nf * f quickly generate overflow problems if we implement the fixed point integer in a 32 bits representation with 12 bits for the fraction and 19 bits for the decimal part. In order to compensate for this problem and to increase the size of these fixed point integers some additional math has to be added to strech the domain of a the fixed point integer. This transparent scaling (actually adding floating point behavior), the toString and toFP conversions, performance shortcuts and additional math functions are provided in the MathFP library to make it easy to work with fixed point integers.

MathFP Performance Tips

The following performance tips will shorten your Java program and increase performance:

  1. Instead of the MatFP.add() or MathFP.sub() always just add or subtract fixed point integers as if they were normal integers
  2. To quickly convert to a normal int and dispose of the fraction just shift the fixed point integer the number of precision bits to the right (nf >>pecision).
  3. Multiplying a fixed point integer with a natural number n (this is a normal integer) should not be done by converting the number n to a fixed point using MathFP.toFP(n) and then use the MathFP.mul() instead one should just multiply the fixed point integer with n. For example 3 * mf = mf + mf + mf.
  4. Similar to point 3 dividing by a natural number (a normal int) can be done without converting the natural number to a fixed-point integer. For example mf / 3 = MathFP.div(mf,MathFP.toFP(3)).
  5. Zero in fixed-point representation is 0. So mf = 0 equals mf = MathFP.toFP(0);

 

Onno Hommes, Rochester NY
jScience Technologies
www.jscience.net