Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Tree [r4] /
History



File Date Author Commit
README 2010-10-01 sven-ola [r4] added +- MAX
fpm.c 2010-09-30 sven-ola [r3] corrections
fpm.h 2010-09-30 sven-ola [r3] corrections
fpmtest.c 2010-10-01 sven-ola [r4] added +- MAX
license.txt 2010-09-30 sven-ola [r2] doc, test program

Read Me

Fixed Point Math C Library, Copyright (c) 2009, Sven-Ola()gmx.de

While recent CPUs are real number crunchers with their integrated FPUs,
using floating point math on embedded devices such as MIPS or ARM may
be very slow. Especially if -msoft-float is used. Thus, replacing 
floating point math by some integer math can speed up a program. This
is an old trick, e.g. I've stubled across this programming technique while
creating a graphics lib (lines, circles etc.) for Apple ][ in the 1980's.

You define a part of an integer to act as the "digits behind the point".
This part is predefined, hence the name "Fixed Point Math". For example,
you can convert 2 floats -> fpm. Now it's possible to do fpma+fpmb which
effectively adds two integers. If you reverse the conversion on the
integer outcome, you get (mostly) the same number as when adding floata+
floatb. The same is true e.g. for a multiplication or division - these
operations require some additional integer-shifting magic but the function
is similar. 

The Drawback: a typical integer present the same number space than a float
or double. For example: 20 bit + 12 bit can hold +/-524287 with a resolution
of 1/4096 (around 0.0002).

History
-------

I'm a wireless mesh network activist, which involves me with the
olsr.org routing daemon project. The first versions of this daemon
extensively use standard floating point math, e.g. to calculate
the routing path costs. This in turn causes a high CPU load,
especially on small and slow embedded devices (WLAN routers).

Using integer-based math instead was a solution to optimize the
CPU load in this case. While poking through the net, searching
for a sufficiently licensed lib to replace the floats/doubles with
something more efficient, I do not find anything usable. Offered
libs are all [a] very specific to a respective project or [b] not
sufficient licensed (olsr.org daemon has BSD-style license).

If one can find nothing to grab, it's DIY. During the conversation
within the project, someone mentions the idea of putting aside a 
generally usable FPM lib to the public. After asking the olsr.org
devel community for permission to publish separately, I needed 
some time to find a quiet hour to upload that stuff herein to SF.

Usage
-----

You need to define how many bits you want to spend for the "digits
behind the point". Change the default #define FPM_BIT 12 in fpm.h
for this. When using 12 bits, you have 32-12 bits for "digits before
the point" which gives you numbers from to.

Simply change and compile the test program. Do "make" and run the
resulting ./fpmtest binary that compares the speed. You can specify
the following compiling options:

USE_FPM=0:	does not use FPM (typedef float fpm)
USE_FPM=1:	switches to FPM (typedef int fpm)
DEBUG:		if defined, uses functions for FPM (with assert)
		if undefined uses #defines for FPM

Updates
-------

Don't expect frequent updates to this stuff. You may use subversion
to checkout files. The general command for this is:

svn co https://fpmlib.svn.sourceforge.net/svnroot/fpmlib fpmlib