GSOC 2013

newer
[operators] What is the correct...

older
Re: [boost] [GSOC] XML library of...

Dmitriy

10 Apr 2013 10 Apr '13

10:19 a.m.

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

Show replies by date

Vicente J. Botet Escriba

10 Apr 10 Apr

4:48 p.m.

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

Michael Marcin

11 Apr 11 Apr

6:23 a.m.

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!

Dmitriy Gorbel

1:23 p.m.

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 -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4645146.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Dmitriy Gorbel

18 Apr 18 Apr

1:39 p.m.

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 -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4645577.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Vicente J. Botet Escriba

20 Apr 20 Apr

12:15 a.m.

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.

Michael Marcin

4:14 a.m.

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

Vicente J. Botet Escriba

22 Apr 22 Apr

4:28 a.m.

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

Dmitriy Gorbel

10:35 p.m.

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 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 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. -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4645863.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Vicente J. Botet Escriba

23 Apr 23 Apr

2:24 a.m.

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.

...

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

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

I don't see any major reason to don't use templates and namespaces in such systems. Do you? 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.

...

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

This is where I wanted to go. If there is a maximum size the arithmetic can not be open and T + T -> T 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

Michael Marcin

4:46 a.m.

...

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

Dmitriy Gorbel

1:14 p.m.

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. -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4645894.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Michael Marcin

4:39 p.m.

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

Dmitriy Gorbel

6:59 p.m.

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 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. -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4645943.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Michael Marcin

10:12 p.m.

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

Vicente J. Botet Escriba

10:24 p.m.

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

Michael Marcin

11:05 p.m.

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& x) - std::ostream& operator<<(std::ostream& stream, const fixed& 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-fix...

...

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

...

Discussion:

http://web.archive.org/web/20071220190103/http://www.devmaster.net/forums/sh...

...

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

Vicente J. Botet Escriba

11:53 p.m.

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

Dmitriy Gorbel

24 Apr 24 Apr

9:59 p.m.

Michael, thanks for the links. As for me, this page also has interesting info(and this page give me idea to provide math functions). http://www.codeproject.com/Articles/37636/Fixed-Point-Class Vicente Botet wrote

...

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?

Yes, of course, boost community should choose the default notation. What is the best way to provide several notations? That is less important issue, but I have question about the file structure. In the prototype all code in one file. But I think file structure may look like this: fixed_point.hpp - top level header fixed_point/cardinal.hpp fixed_point/integral.hpp fixed_point/nonnegative.hpp fixed_point/negatable.hpp fixed_point/functions.hpp fixed_point/common.hpp fixed_point/config.hpp I do not insist, but I think segregation better than one file, and want to know your opinion. P.S. The proposal. proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final. Sincerely, Dmitriy. -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4646027.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Vicente J. Botet Escriba

25 Apr 25 Apr

6:27 a.m.

Le 24/04/13 23:59, Dmitriy Gorbel a écrit :

...

Michael, thanks for the links. As for me, this page also has interesting info(and this page give me idea to provide math functions). http://www.codeproject.com/Articles/37636/Fixed-Point-Class

Vicente Botet wrote

...
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? Yes, of course, boost community should choose the default notation. I would start this as soon as possible as this could take some time. I would start a thread as well for the naming of the different classes. Having to provide several notations let me think that the use of at least a namespace fixed_point is mandatory to don't pollute the Boost namespace.

What is the best way to provide several notations? Template alias?

That is less important issue, but I have question about the file structure. In the prototype all code in one file. But I think file structure may look like this: fixed_point.hpp - top level header fixed_point/cardinal.hpp fixed_point/integral.hpp fixed_point/nonnegative.hpp fixed_point/negatable.hpp fixed_point/functions.hpp fixed_point/common.hpp fixed_point/config.hpp

I do not insist, but I think segregation better than one file, and want to know your opinion. I have no problem with that for a final library and even I encourage you to do it to minimize dependencies if this helps. Please don't use /common.hpp file that has no meaning. Name your files depending on whatever they provide. Move any implementation detail file to fixed_point.hpp. When doing a prototype IMO it is better to put all in one file so that it can be shared easily. P.S. The proposal. proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final.

As you are for using enum for rounding/overflow policies, could you add the policies that you must implement and when these policies will be implemented? I don't see when you would develop the math functions on the planning. Please don't forget to apply to GSoC as soon as possible so that the Mentors starts to evaluate your proposal and how you react to possible improvements. Best, Vicente

Michael Marcin

9:42 a.m.

Also take a look at: http://calypto.com/en/uploads/collateral/ac_types_2.6.zip It comes with quite good documentation. It was recommended years ago by Maurizio Vitale who was working on a proto version of SystemC data types. http://gcc.gnu.org/ml/gcc-help/2007-12/msg00465.html

Christopher Kormanyos

7:18 p.m.

...

...
P.S. The proposal. proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final.

I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project. I strongly suggest limiting the scope of the GSoC fixed-point project to a specific number of digits, such as those that can fit into int8_t, int16_t, int32_t, and int64_t. This can be done with one template and one decimal split. It would allow for fixed-point representations all the way from Q0.63 through Q31.32, up to Q63.0. I recommend this because it will make the project feasible when it comes to any computations of elementary transcendental functions. Consider, for example, our implementation of Boost's floating-point multiprecision back end. This back end is also severely limited to approx. less than 1,000 decimal digits. We can extend it later, but we are happy to have something now, even with its limitations. The same holds true for fixed-point. I think people need a good, well-tested fixed-point class supporting a rich set of transcendental functions much more than they need high-precision fixed-point. I will be very difficult to develop algorithms for sin, cos, log, exp, for an unlimited number of digits extending all the way to the realm of multiprecision. In fact, it would be a remarkable feat to do it in one summer. On the other hand, you could plug fixed-point into multiprecision for digit counts exceeding, say, 64. So it is really up to you guys how you want to deal with this.

...

I don't see when you would develop the math functions on the planning.

You really do need to include elementary functions, such as a all of those or at least a subset of those in <cmath>. Sincerely, Chris.

Vicente J. Botet Escriba

10:36 p.m.

Le 25/04/13 21:18, Christopher Kormanyos a écrit :

...

...
...
P.S. The proposal. proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final. I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project.

You could be the mentor if you want. Best Vicente

Christopher Kormanyos

26 Apr 26 Apr

7:04 p.m.

...

...
...
...
P.S. The proposal.

...

...
...
...
proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final.

...

...
I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project.

...

You could be the mentor if you want. Best Vicente

I would like to contribute something. But I would need help, especially for the architectural considerations and specifically for assistance with rounding issues and testing with Boost.Test. Also, I need to realistically consider my time schedule, since I am already involved in at least one GSoC project, and I have a master's student at my day job (but he is almost done). Maybe we could we team up for co-mentorship with two or three of us in a similar way that is intended for the Boost.Math project. What do you think? Sincerely, Chris.

Vicente J. Botet Escriba

7:30 p.m.

Le 26/04/13 21:04, Christopher Kormanyos a écrit :

...

...
...
...
...
P.S. The proposal. proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final. I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project. You could be the mentor if you want. Best Vicente I would like to contribute something.

But I would need help, especially for the architectural considerations and specifically for assistance with rounding issues and testing with Boost.Test.

Also, I need to realistically consider my time schedule, since I am already involved in at least one GSoC project, and I have a master's student at my day job (but he is almost done).

Maybe we could we team up for co-mentorship with two or three of us in a similar way that is intended for the Boost.Math project.

What do you think?

This could be an excellent idea. Having several mentors could help to define the requirements of a library with different expectations depending on the domain where it is used. Let us discuss it privately under the GSoC comments associated to this proposal. Best, Vicente

Christopher Kormanyos

9:15 p.m.

...

...
...
...
...
...
P.S. The proposal.

...

...
...
...
...
...
proposal_Dmitriy_Gorbel.pdf http://boost.2283326.n4.nabble.com/file/n4646027/proposal_Dmitriy_Gorbel.pdf I think this is final version, or close to final.

...

...
...
...
I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project.

...

...
...
You could be the mentor if you want. Best Vicente

...

...
I would like to contribute something.

...

...
Maybe we could we team up for co-mentorship with two or three of us in a similar way that is intended for the Boost.Math project. What do you think?

...

Let us discuss it privately under the GSoC comments associated to this proposal. Best, Vicente

OK. I am booked on Saturday and most of Sunday. I have read your comments and will try to incorporate them into a sensible thought process, and can contact you later on Sunday or Monday. Sincerely, Chris.

Dmitriy Gorbel

28 Apr 28 Apr

10:23 p.m.

Vicente Botet wrote

...

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

...
Yes, of course, boost community should choose the default notation.

I would start this as soon as possible as this could take some time. I would start a thread as well for the naming of the different classes. Having to provide several notations let me think that the use of at least a namespace fixed_point is mandatory to don't pollute the Boost namespace.

I started a thread at the ML and wait for community feedback. Vicente Botet wrote

...

...
What is the best way to provide several notations? Template alias?

Just for now, if provide only 2 notations(notation from c++1y proposal and Q notation) I can just get absolute value from the resolution parameter. For example, in this two notations types same: negatable<8, -8> for c++1y proposal notation is equal to negatable<8, 8> for Q notation If users really want more than 2 notations, I will have to solve this issue. Vicente Botet wrote

...

As you are for using enum for rounding/overflow policies, could you add the policies that you must implement and when these policies will be implemented?

In the last days I explored closely the prototype, and the closer I get to the prototype the more I like it :) I really like OOP design for rounding and overflow strategies. Moreover, exists strateges comply with the requirements of the c++1y proposal and provide even more features. But c++1y proposal require enum for the strategies, can my proposal slightly break c++1y proposal? Vicente Botet wrote

...

I don't see when you would develop the math functions on the planning.

That's already in the specification and timeline. Vicente Botet wrote

...

Please don't forget to apply to GSoC as soon as possible so that the Mentors starts to evaluate your proposal and how you react to possible improvements.

Link to my proposal on GSOC site http://www.google-melange.com/gsoc/proposal/review/google/gsoc2013/dmitriy/1 Christopher Kormanyos wrote

...

I have a major suggestion. You do not have to accept my suggestion, since I am only an observer of this project.

I strongly suggest limiting the scope of the GSoC fixed-point project to a specific number of digits, such as those that can fit into int8_t, int16_t, int32_t, and int64_t. This can be done with one template and one decimal split. It would allow for fixed-point representations all the way from Q0.63 through Q31.32, up to Q63.0.

I recommend this because it will make the project feasible when it comes to any computations of elementary transcendental functions.

I strongly agree with you. The prototype now work similar to your suggestions. Christopher Kormanyos wrote

...

I will be very difficult to develop algorithms for sin, cos, log, exp, for an unlimited number of digits extending all the way to the realm of multiprecision. In fact, it would be a remarkable feat to do it in one summer. On the other hand, you could plug fixed-point into multiprecision for digit counts exceeding, say, 64. So it is really up to you guys how you want to deal with this.

What if I will use Boost.multiprecision library for numbers with representation larger then 64 bits? Now I correct my proposal, I send new version to this ML and GSOC site as soon as possible. Sincerely, Dmitriy. -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-2013-tp4645089p4646263.html Sent from the Boost - Dev mailing list archive at Nabble.com.

Christopher Kormanyos

24 Apr 24 Apr

10 p.m.

...

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

...

...
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 remember the thread. Fixed-point is one of those things where everyone rolls their own. A reference implementation in Boost would be key. Fixed-point is a tough one, depending on how you do the decimal split, and how much precision should be supported via width of the fractional and integer parts, and how many transcendental functions should be in the mix. I rolled one here: https://github.com/ckormanyos/real-time-cpp/tree/master/ref_app/src/math/fix... It comes from my research with C++ on hard real-time systems. This implementation is simplistic, but may have ideas. Basically, it splits a signed integer (8, 16, 32, or 64 bit) down the middle. There is support for a variety of elementary transcendental functions. It might be of interest when pursuing fixed-point. I favor polynomial expansion based on least squares fit over CORDIC. Sincerely, Chris.

Michael Marcin

23 Apr 23 Apr

4:46 a.m.

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

Vicente J. Botet Escriba

10:24 p.m.

New subject: GSOC 2013 fixed_point

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 i.e. <16,8> instead of <16,-8>.

The problem I see with this notation is that to represent the numbers -65536

...

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

4324

Age (days ago)

4342

Last active (days ago)

List overview

Download

29 comments

5 participants

participants (5)

Christopher Kormanyos
Dmitriy
Dmitriy Gorbel
Michael Marcin
Vicente J. Botet Escriba

GSOC 2013

Dmitriy

Vicente J. Botet Escriba

Michael Marcin

Dmitriy Gorbel

Dmitriy Gorbel

Vicente J. Botet Escriba

Michael Marcin

Vicente J. Botet Escriba

Dmitriy Gorbel

Vicente J. Botet Escriba

Michael Marcin

Dmitriy Gorbel

Michael Marcin

Dmitriy Gorbel

Michael Marcin

Vicente J. Botet Escriba

Michael Marcin

Vicente J. Botet Escriba

Dmitriy Gorbel

Vicente J. Botet Escriba

Michael Marcin

Christopher Kormanyos

Vicente J. Botet Escriba

Christopher Kormanyos

Vicente J. Botet Escriba

Christopher Kormanyos

Dmitriy Gorbel

Christopher Kormanyos

Michael Marcin

Vicente J. Botet Escriba

tags

participants (5)