GSOC 2013

classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

GSOC 2013

Dmitriy Gorbel
Hi folks!

I am Dmitriy Gorbel, a computer science student  at the Kharkiv
Polytechnic University from Ukraine.

I browsed Boost C++ Libraries home page for GSoC and I want to propose
a project to implement of a Fixed Point library.
I read open standard on open-std.org
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html
and tried implementation by Vicente J. Botet Escriba at the
https://svn.boost.org/svn/boost/sandbox/fixed_point/

Now I prepare my proposal.

So I will take implementation by Vicente J. Botet Escriba in the first
place, and I found few more simple implementations, but can anyone
advise me other implementations of Fixed Point arithmetic, which I
must pay attention? Not necessarily in C++, pure C also would be good.

Thanks

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
Le 10/04/13 12:19, Dmitriy a écrit :

> Hi folks!
>
> I am Dmitriy Gorbel, a computer science student  at the Kharkiv
> Polytechnic University from Ukraine.
>
> I browsed Boost C++ Libraries home page for GSoC and I want to propose
> a project to implement of a Fixed Point library.
> I read open standard on open-std.org
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html
> and tried implementation by Vicente J. Botet Escriba at the
> https://svn.boost.org/svn/boost/sandbox/fixed_point/
>
> Now I prepare my proposal.
>
> So I will take implementation by Vicente J. Botet Escriba in the first
> place, and I found few more simple implementations, but can anyone
> advise me other implementations of Fixed Point arithmetic, which I
> must pay attention? Not necessarily in C++, pure C also would be good.
>
Hi Dmitriy,

glad to see you have decided to post on this ML.

I think the goal is to implement something close to the C++ Fixed Point
C++1y proposal. You can look at my prototype to see if you are confident
with the complexity (template meta-programming) needed to solve the
problem at hand.

Of course you can make a proposal for GSoC that is not based on the
C++1y proposal that could imply a simpler implementation, but that would
miss some of the features I'm locking for.

So the fisrt thing you can do is to understand the C++1y proposal,
inspect my prototype and then see if you want to implement the C++1y
proposal independently of my prototype.
If you prefer to go towards a less static type approach for
fixed-points, there are some implementations that you can found on the
web. I don't remember none particularly, but I would replay once I have
found some of them. There is also a lot of mail exchanges that you could
try to digest in the Boost ML.

The make a concrete proposal and send it either directly to GSoc to this
ML or to me.

HTH,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
Vicente J. Botet Escriba wrote:

> Le 10/04/13 12:19, Dmitriy a écrit :
>> Hi folks!
>>
>> I am Dmitriy Gorbel, a computer science student  at the Kharkiv
>> Polytechnic University from Ukraine.
>>
>> I browsed Boost C++ Libraries home page for GSoC and I want to propose
>> a project to implement of a Fixed Point library.
>> I read open standard on open-std.org
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html
>> and tried implementation by Vicente J. Botet Escriba at the
>> https://svn.boost.org/svn/boost/sandbox/fixed_point/
>>
>> Now I prepare my proposal.
>>
>> So I will take implementation by Vicente J. Botet Escriba in the first
>> place, and I found few more simple implementations, but can anyone
>> advise me other implementations of Fixed Point arithmetic, which I
>> must pay attention? Not necessarily in C++, pure C also would be good.
>>

There have been many discussions on fixed point libraries on the list in
the past I would start by searching the mailing list archives and
reading up.

Good luck!


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Dmitriy Gorbel
Michael Marcin-3 wrote
There have been many discussions on fixed point libraries on the list in
the past I would start by searching the mailing list archives and
reading up.

Good luck!
Thanks for your advice, I found many discussions about the fixed point
library in mailing list archive. It come in handy.

Vicente J. Botet Escriba wrote
Hi Dmitriy,

glad to see you have decided to post on this ML.

I think the goal is to implement something close to the C++ Fixed Point
C++1y proposal. You can look at my prototype to see if you are confident
with the complexity (template meta-programming) needed to solve the
problem at hand.

Of course you can make a proposal for GSoC that is not based on the
C++1y proposal that could imply a simpler implementation, but that would
miss some of the features I'm locking for.

So the fisrt thing you can do is to understand the C++1y proposal,
inspect my prototype and then see if you want to implement the C++1y
proposal independently of my prototype.
If you prefer to go towards a less static type approach for
fixed-points, there are some implementations that you can found on the
web. I don't remember none particularly, but I would replay once I have
found some of them. There is also a lot of mail exchanges that you could
try to digest in the Boost ML.

The make a concrete proposal and send it either directly to GSoc to this
ML or to me.

HTH,
Vicente
I want to implement library, of course, based on the C++1y proposal and
your prototype. I just interested about other implementations,
I think they also become useful.

I will send my proposal on your email soon.

Thanks for your help,
Dmitriy
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Dmitriy Gorbel
I want to provide my proposal to the Boost community.

Please, lets discuss it! I will be grateful for your reviews and advices. How can I improve it?
I appreciate any feedback you may have.

proposal_Dmitriy_Gorbel.pdf
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
Le 18/04/13 15:39, Dmitriy Gorbel a écrit :

> I want to provide my proposal to the Boost community.
>
> Please, lets discuss it! I will be grateful for your reviews and advices.
> How can I improve it?
> I appreciate any feedback you may have.
>
> proposal_Dmitriy_Gorbel.pdf
> <http://boost.2283326.n4.nabble.com/file/n4645577/proposal_Dmitriy_Gorbel.pdf>
>
>
>
Hi, I have read carefully your proposal and I have some suggestion to
improve it and a lot of questions for you. I don't pretend that you must
have an answer to all these question now, but your answers will help us
to see if you are really aware of the problems and to improve the scope
of your proposal. Some of your answers should be part of your proposal.

I would suggest you to "quote" any text that is taken exactly from
external resources as e.g wikipedia.

Your proposal must state clearly whether you want to implement binary or
decimal fixed points.

What would you add to the C++1y proposal?

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?

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?

Why do you say that "undefined behavior after signed integer arithmetic
overflow".

Are you aware of the limitations of the C++11 proposal? Could it be used
on embedded systems?

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?

You talk about the need to round for division. Do you know of other
cases where rounding is needed?

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?

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 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.

What external resources have you read in addition to the C++1y proposal?
have you read the Boost ML archives respect to this subject?

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?

Hoping all these questions would not discourage you. The domain is not
too big but large enough. You should know it and choose what you think
is better to implement first and what is implementable under the time frame.

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?

Do you prefer to implement something well defined even with some
limitations or explore the domain and see what could/should be done?

Best,
Vicente

P.S. Please check the syntax and grammar of the text.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
On 4/19/2013 7:15 PM, Vicente J. Botet Escriba wrote:

> Le 18/04/13 15:39, Dmitriy Gorbel a écrit :
>> I want to provide my proposal to the Boost community.
>>
>> Please, lets discuss it! I will be grateful for your reviews and advices.
>> How can I improve it?
>> I appreciate any feedback you may have.
>>
>> proposal_Dmitriy_Gorbel.pdf
>> <http://boost.2283326.n4.nabble.com/file/n4645577/proposal_Dmitriy_Gorbel.pdf>
>>
>
> <snip very good feedback>
>

There is a typo: The range must be *grater* then the resolution

I don't understand your types.

cardinal<16> 0 <= n <= 65536

This seems to be a 16 bit unsigned type but requires 17 bits to store
this range. It should probably be 0 <= n <= 65535.

integral<4> -16 <= n <= 16

Similar here this seem to be a 5 it signed integer but requires 6 bits
to store this range. It should probably be -16 <= n <= 15.

nonnegative<8,-4> -256 < n < 256 in increments of 2^-4 = 1/16

I don't understand how a type nonnegative can store values in (-256,0).


negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
  = 1/ 256

This seems close to a fixed point type as I'm used to seeing it.
Although again the ranges seem wrong.

I'm much more accustom to seeing fixed point number specified as
<Magnitude bits, Fractional Bits> i.e. <16,8> instead of <16,-8>.
Still this representation makes sense because it specifies both
parameters in terms 2^x. It also supports something like <17,1> to give
a 16 bit type that has the range [-131072, 131071] in increments of 2.

Still it might be surprising to those familiar with the more common
fixed-point notation.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
Le 20/04/13 06:14, Michael Marcin a écrit :

> On 4/19/2013 7:15 PM, Vicente J. Botet Escriba wrote:
>> Le 18/04/13 15:39, Dmitriy Gorbel a écrit :
>>> I want to provide my proposal to the Boost community.
>>>
>>> Please, lets discuss it! I will be grateful for your reviews and
>>> advices.
>>> How can I improve it?
>>> I appreciate any feedback you may have.
>>>
>>> proposal_Dmitriy_Gorbel.pdf
>>> <http://boost.2283326.n4.nabble.com/file/n4645577/proposal_Dmitriy_Gorbel.pdf>
>>>
>>>
>>
>> <snip very good feedback>
>>
>
> There is a typo: The range must be *grater* then the resolution
>
> I don't understand your types.
>
> cardinal<16> 0 <= n <= 65536
>
> This seems to be a 16 bit unsigned type but requires 17 bits to store
> this range. It should probably be 0 <= n <= 65535.
>
> integral<4> -16 <= n <= 16
>
> Similar here this seem to be a 5 it signed integer but requires 6 bits
> to store this range. It should probably be -16 <= n <= 15.
>
> nonnegative<8,-4> -256 < n < 256 in increments of 2^-4 = 1/16
>
> I don't understand how a type nonnegative can store values in (-256,0).
>
>
> negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
>  = 1/ 256
>
> This seems close to a fixed point type as I'm used to seeing it.
> Although again the ranges seem wrong.
>
> I'm much more accustom to seeing fixed point number specified as
> <Magnitude bits, Fractional Bits> i.e. <16,8> instead of <16,-8>.
> Still this representation makes sense because it specifies both
> parameters in terms 2^x. It also supports something like <17,1> to
> give a 16 bit type that has the range [-131072, 131071] in increments
> of 2.
>
> Still it might be surprising to those familiar with the more common
> fixed-point notation.
>
>
Dmitriy,
what is your opinion about this?

Best,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Dmitriy Gorbel
Vicente Botet wrote
Dmitriy,
what is your opinion about this?

Best,
Vicente
Sorry for the delay, I was busy at the weekend.
At first thanks for your comments - I really not thought about some issues before reading it.

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.

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.

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.

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

I think main advantage of the  fixed-point numbers - customizable range and resolution, hence more efficient.

Vicente Botet wrote
Why do you say that "undefined behavior after signed integer arithmetic
overflow".
I mean that signed integer overflow causes undefined behavior.

Vicente Botet wrote
Are you aware of the limitations of the C++11 proposal? 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.
Furthermore, templates may increase the time of compilation.

I know that some embedded developers avoid templates, namespaces, exceptions,
virtual inheritance, etc.

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.

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...

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.

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.
What's your opinion?

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.

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 

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?

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.

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.

Michael Marcin-3 wrote
There is a typo: The range must be *grater* then the resolution

I don't understand your types.

cardinal<16> 0 <= n <= 65536

This seems to be a 16 bit unsigned type but requires 17 bits to store
this range. It should probably be 0 <= n <= 65535.

integral<4> -16 <= n <= 16

Similar here this seem to be a 5 it signed integer but requires 6 bits
to store this range. It should probably be -16 <= n <= 15.

nonnegative<8,-4> -256 < n < 256 in increments of 2^-4 = 1/16

I don't understand how a type nonnegative can store values in (-256,0).


negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
  = 1/ 256

This seems close to a fixed point type as I'm used to seeing it.
Although again the ranges seem wrong.

I'm much more accustom to seeing fixed point number specified as
<Magnitude bits, Fractional Bits> i.e. <16,8> instead of <16,-8>.
Still this representation makes sense because it specifies both
parameters in terms 2^x. It also supports something like <17,1> to give
a 16 bit type that has the range [-131072, 131071] in increments of 2.

Still it might be surprising to those familiar with the more common
fixed-point notation.
Here is no mistake in the example. I paste here  part of the C++1y proposal
C++1y proposal wrote
Basic Types

The fixed-point library contains four class templates.
 They are cardinal and integral for integer arithmetic,
and nonnegative and negatable for fractional arithmetic.

These types have a range specified by an integer.
The range of an unsigned number n is 0 <= n < 2g where g is the range parameter.
 The range of an signed number n is 2g < n < 2g. Note that the range interval is
 half-open for unsigned numbers and open for signed numbers.
For example, cardinal<8> has values n such that 0 <= n < 256
 and integral<8> has values n such that -256 < n < 256.

The fractional types have a resolution specified by an integer.
The resolution of a fractional number n is 2s, where s is the resolution parameter.
 For example, negatable<8,-4> has values n such that -256 < n < 256 in increments
 of 2-4 = 1/16.

Both range and resolution parameters may be either positive or negative.
The number of significant bits is g-s. This specification enables representing
 both very small and very large values with few bits. In any event, the range
must be greater than the resolution, that is g>s.
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.

Sincerely,
Dmitriy.
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
In reply to this post by Dmitriy Gorbel
On 4/22/13 5:35 PM, Dmitriy Gorbel wrote:

>
> Michael Marcin-3 wrote
>> There is a typo: The range must be *grater* then the resolution
>>
>> I don't understand your types.
>>
>> cardinal<16> 0 <= n <= 65536
>>
>> This seems to be a 16 bit unsigned type but requires 17 bits to store
>> this range. It should probably be 0 <= n <= 65535.
>>
>> integral<4> -16 <= n <= 16
>>
>> Similar here this seem to be a 5 it signed integer but requires 6 bits
>> to store this range. It should probably be -16 <= n <= 15.
>>
>> nonnegative<8,-4> -256 < n < 256 in increments of 2^-4 = 1/16
>>
>> I don't understand how a type nonnegative can store values in (-256,0).
>>
>>
>> negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
>>    = 1/ 256
>>
>> This seems close to a fixed point type as I'm used to seeing it.
>> Although again the ranges seem wrong.
>>
>> I'm much more accustom to seeing fixed point number specified as
>> <Magnitude bits, Fractional Bits>
>>   i.e. <16,8> instead of <16,-8>.
>> Still this representation makes sense because it specifies both
>> parameters in terms 2^x. It also supports something like <17,1> to give
>> a 16 bit type that has the range [-131072, 131071] in increments of 2.
>>
>> Still it might be surprising to those familiar with the more common
>> fixed-point notation.
>
> Here is no mistake in the example. I paste here  part of the C++1y proposal
>

If these are correct could someone explain them to me.
Especially why a type named nonnegative can have a value of -255.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
In reply to this post by Vicente Botet
>> 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.

The trig functions are difficult to implement generically in my
experience. Most of the fixed point implementations rely on lookup
tables with CORDIC algorithms. The lookup tables would have to be
calculated with metaprogramming when you allow for essentially arbitrary
fixed-point layouts.

>>
>> 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?

This would certainly be a deal breaker for most (all?) embedded use cases.

>> 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.

Yep that would include me and my use cases.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Dmitriy Gorbel
Vicente Botet wrote
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.
Michael Marcin-3 wrote
The trig functions are difficult to implement generically in my
experience. Most of the fixed point implementations rely on lookup
tables with CORDIC algorithms. The lookup tables would have to be
calculated with metaprogramming when you allow for essentially arbitrary
fixed-point layouts.
Some functions(like modf, floor, fabs) really aren't difficult to implement.
But some functions aren't easy to implement. I need some time to
explore the algorithms and make the design. I know that MacLaurin series
can be used in trig functions. I don't familiar with CORDIC algorithms yet,
I just need some time.

List of functions: ceil, floor, sqrt, sin, cos, exp, fabs, fmod, modf, exp.
I think all of this functions must be implemented.
I open to discuss this list, we can add more functions and then rate them by priority.

Vicente Botet wrote
Template meta-programming is not easy. Would you be more comfortable to
implement a run-time solution before the static one?
Sorry, but maybe I understood you wrong.
I should implement library without  
templates, and then with templates?
Why? I think it's not necessary.
Or you suggest me refuse from the templates?

Vicente Botet wrote
Humm, I'm not sure this is undefined behavior. Could you point me where
in the standard you have find this?
I refer to working draft of the Standard, ok?
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf
Working Draft, Standard for Programming Language C++, page 98 wrote
As with any other arithmetic overflow,
if the result does not fit in the space provided, the behavior is undefined.
Vicente Botet wrote
>> Are you aware of the limitations of the C++11 proposal?
Could you answer this question independently of embedded systems?
Vicente Botet wrote
Great. Does it means that you could explore some of the limitations of
the C++1y proposal and try to solve some of them?
We discuss all limitations and problems here :)
I will try to solve limitations, as many as possible.
Main issue independently of embedded systems - make
the notation friendly for most users.
Main issue - make the library useful for embedded systems.

Vicente Botet wrote
>> 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
?
Yes, this is necessary feature, especially for  embedded systems.
Library must provide closed arithmetic for these cases.
I saw that's implemented in your library. I will focus in this issue.

Vicente Botet wrote
I don't see any major reason to don't use templates and namespaces in
such systems. Do you?
I hope the library will be useful for embedded systems - it's main goal.

Vicente Botet wrote
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.
Michael Marcin-3 wrote
Yep that would include me and my use cases.
I think I must implement both cases, where user can choose
closed arithmetic, when precision must be bounded, or opened arithmetic
when range must be extended. I will work with this problem closer.

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?
Yes.

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?
I think I must provide two(or more?) notations.
User should choose from them.

Vicente Botet wrote
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?
I anyway will use your prototype. I will try to prove that
I'm worthy to develop the library.

Summary 

I understood that library must be useful for
embedded systems. It's important.

Also  library must be customizable.
User can choose a notation,
closed or opened arithmetic,
and a rounding policies.

Here is a lot of work :)

Thanks for your feedback.

Sincerely,
Dmitriy.
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
On 4/23/2013 8:14 AM, Dmitriy Gorbel wrote:

>
> Some functions(like modf, floor, fabs) really aren't difficult to implement.
> But some functions aren't easy to implement. I need some time to
> explore the algorithms and make the design. I know that MacLaurin series
> can be used in trig functions. I don't familiar with CORDIC algorithms yet,
> I just need some time.
>
> List of functions: ceil, floor, sqrt, sin, cos, exp, fabs, fmod, modf, exp.
> I think all of this functions must be implemented.
> I open to discuss this list, we can add more functions and then rate them by
> priority.
>

FWIW

http://codepad.org/tidoIWTW


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Dmitriy Gorbel
Michael, thanks for your comments and for the source code.

In the range and resolution examples a lot of mistakes,
you are right. I was careless, sorry.

Michael Marcin-3 wrote
negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
  = 1/ 256
This seems close to a fixed point type as I'm used to seeing it.
Although again the ranges seem wrong.
I'm much more accustom to seeing fixed point number specified as
<Magnitude bits, Fractional Bits> i.e. <16,8> instead of <16,-8>.
I think, I must provide opportunity to choose the notation.

Michael Marcin-3 wrote
Still this representation makes sense because it specifies both
parameters in terms 2^x. It also supports something like <17,1> to give
a 16 bit type that has the range [-131072, 131071] in increments of 2.
If use notation from C++1y proposal,
I plan that value witch set resolution always be negative,
and minimal resolution: 2^-1 = 1/2
I don't plan to implement something like <17,1>.
You think this is really necessary feature?

Sincerely,
Dmitriy.
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
On 4/23/13 1:59 PM, Dmitriy Gorbel wrote:

>
> Michael Marcin-3 wrote
>> Still this representation makes sense because it specifies both
>> parameters in terms 2^x. It also supports something like <17,1> to give
>> a 16 bit type that has the range [-131072, 131071] in increments of 2.
>
> If use notation from C++1y proposal,
> I plan that value witch set resolution always be negative,
> and minimal resolution: 2^-1 = 1/2
> I don't plan to implement something like <17,1>.
> You think this is really necessary feature?
>

No but IMO it was the only cool feature that fell out naturally from the
interface.

Without it I would strongly prefer the fixed< MagnitudeBits,
FractionalBits > interface.

Which more closely aligns with common fixed-point convention:

http://en.wikipedia.org/wiki/Fixed-point_arithmetic#Notation
http://en.wikipedia.org/wiki/Q_(number_format)
http://en.wikipedia.org/wiki/Binary_scaling


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013 fixed_point

Vicente Botet
In reply to this post by Michael Marcin-3
Le 20/04/13 06:14, Michael Marcin a écrit :

> On 4/19/2013 7:15 PM, Vicente J. Botet Escriba wrote:
>> Le 18/04/13 15:39, Dmitriy Gorbel a écrit :
>>> I want to provide my proposal to the Boost community.
>>>
>>> Please, lets discuss it! I will be grateful for your reviews and
>>> advices.
>>> How can I improve it?
>>> I appreciate any feedback you may have.
>>>
>>> proposal_Dmitriy_Gorbel.pdf
>>> <http://boost.2283326.n4.nabble.com/file/n4645577/proposal_Dmitriy_Gorbel.pdf>
>>>
>>>
>>
>> <snip very good feedback>
>>
>
> There is a typo: The range must be *grater* then the resolution
>
> I don't understand your types.
>
> cardinal<16> 0 <= n <= 65536
>
> This seems to be a 16 bit unsigned type but requires 17 bits to store
> this range. It should probably be 0 <= n <= 65535.
>
> integral<4> -16 <= n <= 16
>
> Similar here this seem to be a 5 it signed integer but requires 6 bits
> to store this range. It should probably be -16 <= n <= 15.

The intention of Laurence was to be able to return the same type while
applying the unary minus operator.

With your range the result of -integral<4> is integral<5> or the
operation needs to check for overflow, which is not good neither.
Using an additional bit allows to overcome this deficiency but of course
lost a possible value out of the 2^n. Of course this would needs
consensus on this ML.
> nonnegative<8,-4> -256 < n < 256 in increments of 2^-4 = 1/16
>
> I don't understand how a type nonnegative can store values in (-256,0).
>
Yes this should be 0 < n < 256.
>
> negatable<16,-8> -65536 < n < 65536 in increments of 2^-8
>  = 1/ 256
>
> This seems close to a fixed point type as I'm used to seeing it.
> Although again the ranges seem wrong.
This depend on the definition. With the definition in
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html this
is correct.
>
> I'm much more accustom to seeing fixed point number specified as
> <Magnitude bits, Fractional Bits> i.e. <16,8> instead of <16,-8>.

The problem I see with this notation is that to represent the numbers
-65536<n<65536 in increments of 2^8=256 you need to use a fractional
bits that is negative, which is in some way counterintuitive with the
name of the template parameter, or maybe we need to find a name for
which a negative number is intuitive.
> Still this representation makes sense because it specifies both
> parameters in terms 2^x. It also supports something like <17,1> to
> give a 16 bit type that has the range [-131072, 131071] in increments
> of 2.
>
> Still it might be surprising to those familiar with the more common
> fixed-point notation.
>
As I said there are several notations and there is no real one that
would make happy everyone. So I think that the library should take in
account this point and provide some aliases (c++11)/type traits(c++98)
for the most common notations.

Choosing the default notation is critical and having a consensus on it
would be difficult. Do you think that it is worth proposing several
default notations and request the boost community to choose the default one?

Best,
Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
In reply to this post by Michael Marcin-3
Le 23/04/13 18:39, Michael Marcin a écrit :

> On 4/23/2013 8:14 AM, Dmitriy Gorbel wrote:
>>
>> Some functions(like modf, floor, fabs) really aren't difficult to
>> implement.
>> But some functions aren't easy to implement. I need some time to
>> explore the algorithms and make the design. I know that MacLaurin series
>> can be used in trig functions. I don't familiar with CORDIC
>> algorithms yet,
>> I just need some time.
>>
>> List of functions: ceil, floor, sqrt, sin, cos, exp, fabs, fmod,
>> modf, exp.
>> I think all of this functions must be implemented.
>> I open to discuss this list, we can add more functions and then rate
>> them by
>> priority.
>>
>
> FWIW
>
> http://codepad.org/tidoIWTW
>
>
Michael, I was not aware that you have already a fixed-point library in
http://code.google.com/p/libfixmath/.

Could you give us pointer where this file cross/math/fixed/fixed.hpp is
located?

Best,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Michael Marcin-3
On 4/23/13 5:24 PM, Vicente J. Botet Escriba wrote:
> Michael, I was not aware that you have already a fixed-point library in
> http://code.google.com/p/libfixmath/.
>
> Could you give us pointer where this file cross/math/fixed/fixed.hpp is
> located?
>

Sure I had necro'd a thread a while back but it probably got missed.
Reposting:


On 2/1/13 11:09 PM, Michael Marcin wrote:>
 > 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
 >




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2013

Vicente Botet
Le 24/04/13 01:05, Michael Marcin a écrit :

> On 4/23/13 5:24 PM, Vicente J. Botet Escriba wrote:
>> Michael, I was not aware that you have already a fixed-point library in
>> http://code.google.com/p/libfixmath/.
>>
>> Could you give us pointer where this file cross/math/fixed/fixed.hpp is
>> located?
>>
>
> Sure I had necro'd a thread a while back but it probably got missed.
> Reposting:
>
>
Thanks,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12