Re: [boost] [fixed_point] Request for interest in a binary fixed point library

Subject: Re: [boost] [fixed_point] Request for interest in a binary fixed point library
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2013-02-02 00:09:02

Vicente J. Botet Escriba wrote:
> Hi,
>
> the recent discussion on the MultiplePrecission Arithmetic library has
> show that some people has its ow fixed point library.
>
> Is there an interest in a Boost library having as base
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
>
> I have started a prototype
> http://svn.boost.org/svn/boost/sandbox/fixed_point (there is no doc yet
> but the basic goal is quite close to the N3352 C++ proposal). This
> prototype should allow you to play a little bit with.
>
> If yes, what would you like to be changed, added or improved in n3352?
> Next follows some design decisions that IMO need to be decided before hand.
>
> * Should integers and reals be represented by separated classes?
> * Should signed and unsigned be represented by separated classes?
> * Should the library use a specific representation for signed numbers
> (separated sign, 2-complement? Let the user choose?
> * Should the library provide arbitrary range and resolution and allocators?
> * Should the library be open to overflow and rounding or just implement
> some of the possible policies? and in this case which ones?
> * Should fixed_point be convertible to/from integer/float/double?
> * Could the result of an arithmetic operation have more range and
> resolution than his arguments?
> * Is there a need for a specific I/O?
> * is there a need for radix other than 2 (binary)?
> * Should the library implement the basic functions, or should it
> imperatively implement the C++11 math functions? Could a first version
> just forward to the c++11 math functions?
> * Should the library support just one of the know ways to name a
> fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to
> another?
> * Could expect the same/better performances respect to hand written code?
> * What should be the size used by a fixed_point instance? _fast? _least?
> Should the user be able to decide which approach is better for his needs?
> * Which should be the namespace? boost? boost/fixed_point?
> boost/binary_fixed_point? boost/bfp?
> ...
> * others you can think of.
>
> Please, replay if you are interested, have some experience in the
> domain, good ideas, ..
>
> Best regards,
> Vicente
>

Missed this thread, only just came across it while catching up on things.

I think fixed-point is a very worthwhile thing although in past 
discussions it seems like the functionality that everyone agrees upon is 
a very small subset of what people need in their fixed point types.

I worked with fixed-point numbers for embedded systems without FPUs for 
a few years. Mostly doing real time 3d software rendering with fixed 
point numbers.

I always imagined a boost fixed point library would use some expression 
template patterns probably built on boost proto and be a drop in 
replacement for float with no abstraction penalty. That way you could 
preserve full precision until the end of the full expression. 
Unfortunately I had neither the time or the TMP expertise to pull it 
off. Trig functions should be implemented with CORDIC-based algorithms.

Here's the fixed point abstraction I used for reference.

http://www.mikemarcin.com/media/programming/fixed.7z

The main class acts as a drop in replacement for float.

template< std::size_t MagnitudeBits, std::size_t FractionalBits >
class fixed;

The fixed class includes:
  - various converting constructors from integers, floating point, and 
different precision fixed-point types
  - comparison operators
  - arithmetic operators
  - some mixed type arithmetic operators (like fixed * int)
  - some really simple expression templates for multiplication

as_fixed() function which takes an integral type and returns a type 
convertible to a fixed-point type
i.e.
fixed<16,16> a = as_fixed( 1<<16 );
assert( a == fixed<16,16>(1) );

numeric_limits is specialized for fixed types

some math functions:
  - abs
  - fmod
  - floor
  - ceil
  - ceil_int
  - sqrt
  - sign_equal
  - sign_not_equal
  - *missing* true fixed-point trig functions

conversion functions:
  - to_integer
  - to_float
  - to_double

lame stream operators (convert to/from float):
  - std::istream& operator>>(std::istream& stream, fixed<M,F>& x)
  - std::ostream& operator<<(std::ostream& stream, const fixed<M,F>& x)

Here's some interesting fixed-point resources

Anthony Williams wrote an interesting article on fixed-point math.
http://www.justsoftwaresolutions.co.uk/news/optimizing-applications-with-fixed-point-arithmetic.html

Nils Pipenbrinck wrote an interesting article of fixed-point math which 
all but disappeared unfortunately.
http://web.archive.org/web/20080704062813/http://www.devmaster.net/articles/fixed-point-optimizations
Discussion:
http://web.archive.org/web/20071220190103/http://www.devmaster.net/forums/showthread.php?t=9531

Ken Turkowski's fixed-point square root algorithm
http://www.realitypixels.com/turk/computergraphics/FixedSqrt.pdf

ARM code inverse square root routines
http://www.finesse.demon.co.uk/steven/invsqrt.html

Good luck,

Michael Marcin