×
Namespaces

Variants
Actions

How to use fixed point maths in Java ME

From Nokia Developer Wiki
Jump to: navigation, search

This article shows how to use fixed point maths in Java ME; this is useful on older phone models which don't have support for floating point.

Article Metadata
Article
Created: ed_welch (21 May 2007)
Last edited: hamishwillee (16 Aug 2013)

Contents

Fixed point maths

Some older phone models don't have CLDC 1.1 which includes support for floating point, but this can easily overcome by using fixed point maths.

Fixed point maths we use plain integers but pretend that there is a decimal point. We just take all numbers as multiplied by a common multiplier. Let's just make it 256 for instance. So we convert a normal number to fixed point by multiplying by 256. Therefore we would represent 1 as 256, 2 as 512, 3 as 768, 0.5 as 127, 2.5 as 639.

Similarly we convert from fixed point to normal numbers by dividing by 256.

You're probably wondering why we choose 256 rather than any other number. Well, division happens to be a slow operation on most processors that are used in mobile phones, but there is a trick. If the divisor happens to be a power of two a right shift operation can be used instead. 256 is 2 to the power of 8

   -> n / 256 is equivalent to n >> 8

Similarly, multiplication can be done using a left shift operation:

   n * 256 is equivalent to n << 8

The shift operator are usually carried out in one cycle and are a whole lot faster than division operations.

Also, you can choose any number you like as the divisor, as long as it's a multiple of two. We chose a low number like 256 in this case as usually we are using these fixed point maths to calculate the positions of graphics on the screen and it's easy to get an overflow if the divisor is too high.

Quirks:

There is one small quirk in this technique that you should be aware of: negative numbers are never rounded down to zero.

So:

-2 / 256 = 0 (because it's rounded down)

but

-2 >> 8 = -1 

Usually, this quirk can safely be ignored, but it could cause you some problems in certain cases.

Make sure you always wrap the shift operation in brackets because it has a funny precedence order:

 int result = (fxpNum << 8) +1;

If you hadn't enclosed the shift operation in brackets it would have added 1 to 8 and then shifted, so it's fxpNum << 9. Probably not what you wanted!

How to get remainder

There is another trick to make the remainder function (%) faster by using & 0xff.

For instance if you want to convert a fixed point to a normal number and round up, normally you would do the following:

int result = fxpNum >> 8;
if (fxpNum % 256 > 127) result++;

This is the faster way of doing it:

int result = fxpNum >> 8;
if (fxpNum & 0xff > 127) result++;

Similarly:

fxpNum % 16  = fxpNum & 0xffff, 
fxpNum % 4  = fxpNum & 0xf

How to get square root for integers

I include here a useful function to calculate square roots using only integers:

  // Fast integer square root adapted from algorithm, 
// Martin Guy @ UKC, June 1985.
// Originally from a book on programming abaci by Mr C. Woo.
public static int fastSqrt(int n)
{
/*
* Logically, these are unsigned.
* We need the sign bit to test
* whether (op - res - one) underflowed.
*/

int op, res, one;
op = n;
res = 0;
/* "one" starts at the highest power of four <= than the argument. */
one = 1 << 30; /* second-to-top bit set */
while (one > op) one >>= 2;
while (one != 0)
{
if (op >= res + one)
{
op = op - (res + one);
res = res + (one<<1);
}
res >>= 1;
one >>= 2;
}
return(res);
}

So how would we use this to calculate the square root of a fixed point number, say 10?

Well, if we first multiply by 256 squared (i.e. << 16), the result will be in 256 fixed point:

	int fxpNum = 10 << 16;
int fxpResult = fastSqrt(fxpNum);

How to calculate sin, cos, tan etc.

There is a free fixed point library available, http://sourceforge.net/projects/protheus/files/fpmathlib/


which is free to use for non-commercial applications

Debugging tips:

Once you start using fixed point maths it can be quite difficult to debug your code because you have to use a calculator every time you want to convert the fixed point to normal numbers. For this reason I recommend using 1000, or some multiple of ten, as a divisor while you are still debugging your algorithm. This way you can easily convert the numbers in your head. Then when you get the code working correctly you switch to using 256 as the divisor. Really this is good advise for all programming: always concentrate on getting the code working first and leave the optimisation stuff to the final stage.

Proguard

As an insteresting side note I would like to mention that Proguard 4.0 (still in beta) will do some of these maths tricks automatically, e.g:

n * 2 -> n << 1
n * 4 -> n << 2
n % 4 -> n & 0xf

Naming conventions

It's highly recommended that you name all fixed point numbers in some standard way. The reason being is there is no way to tell them apart from normal integers and this can lead to a lot of confusion. For example you could prefix all fixed point intergers with fxp (like I have done in this artical):

int fxpPosition;        // fixed point
int position; // normal integer
This page was last modified on 16 August 2013, at 07:29.
63 page views in the last 30 days.
×