Re: [boost] GSOC 2013

Subject: Re: [boost] GSOC 2013
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2013-04-22 22:24:24

Le 23/04/13 00:35, Dmitriy Gorbel a écrit :
> Vicente Botet wrote
>> Your proposal must state clearly whether you want to implement binary or
>> decimal fixed points.
> I propose the binary fixed-point type. I will emphasize it in the proposal.
Great.
>
> Vicente Botet wrote
>> What would you add to the C++1y proposal?
> I want to add some math functions, include ceil, floor, sqrt, sin, cos, exp,
> fabs, etc.
> Functions must work similar to standard C function with same name, but with
> fixed point numbers.
> I think it would be useful for end user.
This is not on your proposal. What would be the result type of these 
operations? Do you know efficient algorithms for these operations for 
fixed-point numbers? Do you think you will have enough time. Could you 
categorize the features of your library with MUST/SHOULD/COULD so that 
we have an idea of the priorities.
>
> Vicente Botet wrote
>> Why the range and resolution must be static? Which advantages would have
>> a run-time range and/or resolution? On which context each approach is
>> preferable?
> I think run-time range and resolution more 	
> comfortable and useful, but require more resources.

Template meta-programming is not easy. Would you be more comfortable to 
implement a run-time solution before the static one?
>
>
> Vicente Botet wrote
>> What kind of problems have floating point types? Are you aware of the
>> problems fixed point numbers have respect to floating point numbers?
>>
>> How fixed-point number solves the problems fixed-point numbers have?
> Floating point arithmetic has a lot of problems, really.
> For example limited exponent range, loss of significance, unsafe standard
> operations.
> For exploring floating point problems I read
> http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems
> and http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
Could you complete your proposal with the problems mentioned?
> I think main advantage of the  fixed-point numbers - customizable range and
> resolution, hence more efficient.
Determinism?
Could you complete your proposal with the problems fixed-point resolves?
>
>
> Vicente Botet wrote
>> Why do you say that "undefined behavior after signed integer arithmetic
>> overflow".
> I mean that signed integer overflow causes undefined behavior.
Humm, I'm not sure this is undefined behavior. Could you point me where 
in the standard you have find this?
>
>
> Vicente Botet wrote
>> Are you aware of the limitations of the C++11 proposal?
Could you answer this question independently of embedded systems?
>> Could it be used
>> on embedded systems?
> I think it depends on concrete embedded system and software developer.
> For example, templates are useful for making generic classes or functions.
> But they may increase the program size, which is critical for embedded
> systems applications.
Humm, this argument doesn't convince me. At least for fixed-point with 
no more precision than the word machine. I would expect in these cases 
code close to integer arithmetic which would not increase the program size.

I was thinking much more on the precision of the fixed point numbers.
In embedded systems the precission of the fixed-points numbers is 
usually bounded and limited to the machine word.
The C++1y proposal arithmetic is open, and build fixed-point types that 
can be bigger and bigger.
How the user of an embedded system can manage with this explotion?
Should the library provide closed arithmetic for these cases so that
   T+T->T
?
>   
> Furthermore, templates may increase the time of compilation.
Well this is a general problem not specific to embedded systems ;-)
>
> I know that some embedded developers avoid templates, namespaces,
> exceptions,
> virtual inheritance, etc.
>
I don't see any major reason to don't use templates and namespaces in 
such systems. Do you?
> Vicente Botet wrote
>> What would be the result of
>> nonnegative<8,-4>+nonnegative<8,-4>?
>>
>> There are clearly several possibilities. Should your library provide the
>> user with the capacity to choose? If yes, how? if not why?
> The range and resolution of the result calculate by(for addition and
> subtraction):
> nonnegative<max(range1,range2)+1, min(resolution1, resolution2)>
>
> So type of the result: nonnegative<9,-4>
>
> User can create new variable and set any capacity. I think it is enough.
IMO, a lot off the people interested in fixed-point numbers use them for 
embedded systems, and they are requesting a closed arithmetic (see other 
fixed-point threads on this ML) as no dynamic memory should be used by 
the fixed-point numbers, so the precision must be bounded.
I don't think they will accept a fixed point library that don't allows 
them to work with closed arithmetic.
>
>
> Vicente Botet wrote
>> You talk about the need to round for division. Do you know of other
>> cases where rounding is needed?
> Oh rounding needed in many cases.
> Rounding(or truncating) needed always when representation can't accumulate a
> number precisely.
> I said about division because division may have special result, with
> infinite fractional part.
> For example 1/3 = 0.333333333...
Yes, but if as is the case of the C++1y proposal, the arithmetic is 
open, the result type is always precise enough. So in which other cases 
there could be a lost of resolution?
>
> Vicente Botet wrote
>> Would the conversion of fixed points with different range and resolution
>> be implicitly/explicitly convertibles? And respect to C++ built-in
>> types? Would you provide some kind of cast between numbers?
> In comments for your library you note about conversion policy
> when user can choose between  implicitly/explicitly conversion.
> I will try to implement both variants.
Could you add it to the proposal?
>
>
> Vicente Botet wrote
>> What would be the size associated to a fixed-point type? Should it be
>> defined by the library or should the library let the user give some
>> hints to use the storage for the user.
>> Should the classes constructor have allocators for arbitrary large
>> fixed-point types?
> Do you mean size of the representation? I think, good way when user can set 	
> needed size. In this case allocators will be used. But also must be
> reasonable maximum size.
This is where I wanted to go. If  there is a maximum size the arithmetic 
can not be open and
T + T -> T
> What's your opinion?
There are users/context with different needs. The library author must 
know how to manage the different needs and must choose the scope to 
implement. And it is better to implement one thing at a time.
>
>
> Vicente Botet wrote
>> Do you think that it is enough to use just an enum to define the
>> rounding policies or it would be better to let the user to define its
>> strategy?
>> The same question for overflow.
> C++1y proposal require enum for rounding and overflow mode.
> I think it is enough.
Does this mean that the library must evolve when a user request a 
different kind of rounding?
>
>
> Vicente Botet wrote
>> What external resources have you read in addition to the C++1y proposal?
>> have you read the Boost ML archives respect to this subject?
> Yea, I read Boost ML, and  external resources.
> I really liked this introduction to  fixed-point  arithmetic.
> http://www.digitalsignallabs.com/fp.pdf
Great. This paper explains clearly the arithmetic.
>
> Vicente Botet wrote
>> There are several notations for fixed point numbers that don't use range
>> and precission. There are people that use to use these notations. How
>> your library will let them to use their preferred notation?
> I think notation in the proposal clean and easy for understanding.
> What is your advice  about this issue?
I agree the notation is clear (at least for me). There are however other 
users that use to use other notations. If the library doesn't provide a 
solution to this notational problem, they will either noyt use your 
library or try to make use change of notation. How to manage with this 
problem?
>
> Vicente Botet wrote
>> Are you confident with the implementation of the prototype in the
>> sandbox? Do you find it is too complex? if yes, why? would you start
>> from the prototype on the sandbox or would you start from zero?
> Yes, I'm confident with the prototype. Honestly, it took some time for
> exploring it.
> Not very complex, but not simple. Just need time for understand.
>
> I would start from zero, but I will keep near the prototype.
Humm, starting from zero could help you to understand the basics of the 
problem domain. But I don't think you will have enough time to finish 
the library by the end of the summer. If you pas 3/4 of your time to go 
until the current state of my prototype the boost community will not get 
a major improvements to the fixed-point library at the end of the summer.
Note that starting from my prototype is not a MUST of the proposal and 
would be ready to mentor it even if you start from zero IF I'm confident 
you would be able to do it.
What do you think?
>
> Vicente Botet wrote
>> Do you prefer to implement something well defined even with some
>> limitations or explore the domain and see what could/should be done?
> Ohh this is hard question. I would look for middle way.
Great. Does it means that you could explore some of the limitations of 
the C++1y proposal and try to solve some of them?
> About the notation, what can I do for improve it and not 	
> break notation from the proposal?
>
> I will send new version of the proposal as soon as possible.
>
> P.S. Please, don't judge strictly my English, it really isn't very good.
> Sorry...
> I will try to write clearly and carefully.

I'm also in the same case. Thanks Dmitriy for taking the time to answer 
my questions. Please, take the time to improve your proposal with some 
of the concerns of these exchanges.
Maybe you would need to spent the 2 first weeks to explore the problem 
domain, the alternatives, and make a design choice before starting the 
iterative phase code-test-doc.

Best,
Vicente