
Boost : 
Subject: Re: [boost] [fixed_point] Request for interest in a binary fixed point library
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 20130202 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.openstd.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, 2complement? 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
> fixedpoint, 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 fixedpoint 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 fixedpoint 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 CORDICbased 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 fixedpoint 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 fixedpoint 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 fixedpoint 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 fixedpoint resources
Anthony Williams wrote an interesting article on fixedpoint math.
http://www.justsoftwaresolutions.co.uk/news/optimizingapplicationswithfixedpointarithmetic.html
Nils Pipenbrinck wrote an interesting article of fixedpoint math which
all but disappeared unfortunately.
http://web.archive.org/web/20080704062813/http://www.devmaster.net/articles/fixedpointoptimizations
Discussion:
http://web.archive.org/web/20071220190103/http://www.devmaster.net/forums/showthread.php?t=9531
Ken Turkowski's fixedpoint 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk