Re: [boost] Fixed point implicity

Subject: Re: [boost] Fixed point implicity
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-07-02 09:01:22

Hi Soren,

Soren Holstebroe wrote:
> I'm generalizing my fixed point class and have come across a few
> design decisions.
>
> 1. Return type of additive arithmetic operation between integers and
> fixed points
[etc.]

I had a couple of guidelines that I tried to follow in my implementation:

- Behave similarly to the built-in types, e.g. int+float => float.  
This helps with the "principle of least surprise" idea.

- Hope that the compiler will do useful optimisations, e.g.
     fixed<32> a, b, c;
     c = a + b;
   Here the temporary result of a+b needs 33 bits, but the 
expensive-to-compute 33rd bit is discarded in the assignment to c.  If 
we are lucky, the compiler will realise this and not compute it in the 
first place.  I never did any experiments to determine whether this 
actually does happen though.

> Example: a 16 bit integer is added to a 16 bit fixed point with 8 bit fraction.
> I see three possible return types: 16 bit integer, 16:8 fixed point
> and promoted 32:8 fixed point
> If return type is 16 bit integer, the fraction is lost. Clearly not an option.
> If return type is 16:8 fixed point overflow is possible.
> A return type of 32:8 would eliminate overflow, but promotion quickly
> becomes problematic for larger integer types, lets say a 32 bit
> integer added to a fixed point. In that case we would need a 64 bit
> integer which could cripple performance on many systems.
> Another problem with promotion is that the arithmetic expression
> typically would be in a context where the expression is assigned to a
> fixed point of the type present in the expression. In that case we
> have an overflow problem again.
>
> I think I favor keeping the return type in 16:8. The user would then
> have to use an explicit cast to avoid overflow.

I would prefer to keep all the bits.

> 2. Return type of additive arithmetic operation between float and fixed points
>
> Example: fixed_point<int, 16>(10.5) + 5.5f  (integer is representing
> type, 16 bit is the bit reserved for the fraction)
> What would you expect the return type to be?
> I think I favor returning a float. The accuracy of the fixed point is
> compromised anyway.

Yes, return a float.

> 3. Return type of additive arithmetic operation between different
> fixed point types
> Example: fixed_point<int, 16>(10.5) + fixed_point<int, 8>(10.5)
> Like in case 1 there is the choice between losing precision, risking
> overflow or promoting (ex. to fixed_point<boost::int_t<16 + 8>::fast,
> 16>)
>
> I think I favor to simply disallow implicit arithmetic between
> different fixed point types. This would require the user to cast
> either type. The problem with that choice is less transparent use of
> the fixed_point type, since changing a type could break existing code
> where the previous type was in a valid arithmetic operation with
> another fixed point type.

No, I would prefer to return a type that keeps all the bits.

> 4. Similar problems exist for multiplication and division
> If a fixed_point is multiplied with an integer there is a risk of overflow.
> If a fixed_point is multiplied with another fixed_point there is a
> risk of overflow and precision will be lost.

You can return a type that has enough bits for the exact result.
You can get a problem when you need more than 64 bits though.  "Big 
Ints" (note, fixed-size big ints not variable-size ones) would fix this.

> If a fixed_point is divided by an integer there is a risk of loss of precision.
> If a fixed_point or integer is divided by another fixed_point there is
> a risk of overflow and loss of precision.

I remember getting to division and my brain seized up trying to work 
out how many bits are needed....

As Ravi points out, different applications will have different 
requirements.  And it is hard to implement a library that is totally 
flexible because there is nowhere in the syntax of the expression "a+b" 
to specify all the possible options.

Perhaps what is needed is a "meta-library" that can be instantiated to 
provide fixed point types with different characteristics.  Something 
like a layer on top of Boost.Operators.  Thoughts anyone?

Regards,  Phil.