[fixed_point] Request for interest in a binary fixed point library
Hi, the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library. Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html? I have started a prototype http://svn.boost.org/svn/boost/sandbox/fixed_point (there is no doc yet but the basic goal is quite close to the N3352 C++ proposal). This prototype should allow you to play a little bit with. If yes, what would you like to be changed, added or improved in n3352? Next follows some design decisions that IMO need to be decided before hand. * Should integers and reals be represented by separated classes? * Should signed and unsigned be represented by separated classes? * Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? * Should the library provide arbitrary range and resolution and allocators? * Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? * Should fixed_point be convertible to/from integer/float/double? * Could the result of an arithmetic operation have more range and resolution than his arguments? * Is there a need for a specific I/O? * is there a need for radix other than 2 (binary)? * Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? * Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another? * Could expect the same/better performances respect to hand written code? * What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? * Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? ... * others you can think of. Please, replay if you are interested, have some experience in the domain, good ideas, .. Best regards, Vicente
Le 04/04/12 23:33, Vicente J. Botet Escriba a écrit :
Hi,
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
I have started a prototype http://svn.boost.org/svn/boost/sandbox/fixed_point (there is no doc yet but the basic goal is quite close to the N3352 C++ proposal). This prototype should allow you to play a little bit with.
If yes, what would you like to be changed, added or improved in n3352? Next follows some design decisions that IMO need to be decided before hand.
* Should integers and reals be represented by separated classes? * Should signed and unsigned be represented by separated classes? * Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? * Should the library provide arbitrary range and resolution and allocators? * Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? * Should fixed_point be convertible to/from integer/float/double? * Could the result of an arithmetic operation have more range and resolution than his arguments? * Is there a need for a specific I/O? * is there a need for radix other than 2 (binary)? * Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? * Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another? * Could expect the same/better performances respect to hand written code? * What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? * Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? ... * others you can think of.
Please, replay if you are interested, have some experience in the domain, good ideas, ..
Hi, it seems that there is no interest or perhaps people are too busy on on vacations Best, Vicente
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Could you explain a bit your idea? By fixed point library do you mean fixed floating-point types (e.g. 1024-bit double)? Regards, Andrii
Andrii Sydorchuk wrote:
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Could you explain a bit your idea? By fixed point library do you mean fixed floating-point types (e.g. 1024-bit double)?
Regards, Andrii
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Sorry, I had not noticed your post. Yes, I'm quite interested.
Andrii Sydorchuk wrote:
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Sorry, I had not noticed your post. Yes, I'm quite interested.
Please, could you give your point of view for some of the points I addressed on my initial post, or others you think the design of the
Le 10/04/12 20:37, Neal Becker a écrit : library should take in account? Which features are mandatory for your needs, which ones are optional, or not needed at all? Thanks in advance, Vicente
Le 10/04/12 19:46, Andrii Sydorchuk a écrit :
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Could you explain a bit your idea? By fixed point library do you mean fixed floating-point types (e.g. 1024-bit double)?
Hi, No. I meant really a fixed, not a floating -point, in which the fractional part is fixed not variable. C++/Boost Chrono is designed in some way as a fixed point time unit, limited to the use of intmax_t type as underlying (which is enough to represent the time we want to represent). My current needs are for small fixed-point, not for arbitrary large fixed-point numbers, so I'll need less than word-bits fractional numbers. You can take a look at http://en.wikipedia.org/wiki/Fixed-point_arithmetic. This will give you the context. This C++ proposal (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html) is quite in line of the design I'm locking for. The domain is quite related to the quantization (see http://en.wikipedia.org/wiki/Quantization_%28signal_processing%29 for a brief overview) where fixed-point is a way of uniform quantization. For the applications I'm working on now, I will need also non-uniform quantizations, as the ones provided by the reverse of a monotonic function or lookup-tables, but this is out of the scope of a fixed-point library. The questions on my initial post are some of the ones we need to answer when designing such a library. Hope this clarifies the intent, Vicente
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html? Vicente
Yes! Absolutely interested! I use fixed-point extensively with hard real-time microcontroller systems. I am particularly interested in stuff like a 7.8 and 15.16 signed split. I always use signed fixed-point and always use a split right down the middle of the representation. It keeps the math simple and fast. Good luck with this project. Looking forward to it. I will look into the prelim code later. Thank you, Vicente. Best regards, Chris.
Le 10/04/12 22:54, Christopher Kormanyos a écrit :
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html? Vicente Yes! Absolutely interested! I use fixed-point extensively with hard real-time microcontroller systems. I am particularly interested in stuff like a 7.8 and 15.16 signed split. What 7.8 stands for? 7 bits for the integer part and 8 for the fractional part? I guess you prefer a specific class for signed fixed_points and not a template parameter.
sfp<7,8> versus fp<int16_t, 7,8> Do you mind if the library propose some meta-function to specify different formats, e.g. format_i_f<7,8>::type and format_i_f<15,16>::type An alternative design is to have a format parameter, so for example the user could use specific formats fp<i_f<7,8>> a; fp<r_r<7,-8>> b; where i_f has as parameters the number of integral and fractional bits and r_r has as parameters the range and resolution. Currently my prototype and the C++ proposal uses this r_r format. Others use the total number of bits (width including the sign) and the fractional w_f fp<w_f<16,8>> b; The advantage of the meta-function is that the library is open to unknown formats. The liability is the need of ::type (not realy with template aliases) The liability of the format template parameter is that while fp<i_f<7,8>> and fp<r_r<7,-8>> are equivalent they are not the same type and again ::type should be needed. My preference is of course the implicit r_r format and the use of meta-functions for the other formats.
I always use signed fixed-point and always use a split right down the middle of the representation. It keeps the math simple and fast. Do you mind if the rounding strategy is a template parameter? An enumeration or and open policy?
Do you have any preferences for the namespace and class names?
Good luck with this project. Looking forward to it. I will look into the prelim code later.
Any comment is welcome. Best, Vicente
A value of a fixed-point data type is essentially an integer<http://en.wikipedia.org/wiki/Integer> that is scaled by a specific factor determined by the type.
So isn't it possible to implement this functionality as a simple wrapper around Boost Multiprecision fixed int type (cpp_int) with properly overloaded operators? Thanks, Andrii
So isn't it possible to implement this functionality as a simple wrapper
around Boost Multiprecision fixed int type (cpp_int) with properly overloaded operators? Thanks, Andrii
Maybe, for big digit counts this could be a brilliant implementation detail. But don't even think of losing performance for a tiny 7.8 signed split that we will use on an 8-bit CPU! Chris.
Le 11/04/12 23:12, Christopher Kormanyos a écrit :
So isn't it possible to implement this functionality as a simple wrapper around Boost Multiprecision fixed int type (cpp_int) with properly overloaded operators? Thanks, Andrii Maybe, for big digit counts this could be a brilliant implementation detail. But don't even think of losing performance for a tiny 7.8 signed split that we will use on an 8-bit CPU!
I will not forget that, Vicente
Yes! Absolutely interested!
I use fixed-point extensively with hard real-time microcontroller systems. I am particularly interested in stuff like a 7.8 and 15.16 signed split.
What 7.8 stands for? 7 bits for the integer part and 8 for the fractional part? I use 7.8, for example, for a signed 16-bit type with one sign bit, seven mantissa binary digits and eight binary fractional digits.
I guess you prefer a specific class for signed fixed_points and not a template parameter. sfp<7,8> versus fp<int16_t, 7,8>
Do you mind if the library propose some meta-function to specify different formats, e.g. format_i_f<7,8>::type and format_i_f<15,16>::type An alternative design is to have a format parameter, so for example the user could use specific formats
where i_f has as parameters the number of integral and fractional bits and r_r has as parameters the range and resolution. Currently my prototype and the C++ proposal uses this r_r format. Others use the total number of bits (width including the sign) and the fractional w_f I can use anything. The great advantage of your selected convention is that it is absolutely clear how many digits
<snip> there are in mantissa and fraction. I like it.
Do you mind if the rounding strategy is a template parameter? An enumeration or and open policy? Do we even really need a rounding policy? I honestly don't know. I thought the whole deal with fixed-point was to free us from the burdens of formal floating-point representation and obtain efficiency and exactness via near-integer representation. Maybe others have a clear, or more formal, suggestion here.
Do you have any preferences for the namespace and class names? Yes, in other post, "boost/fixed_point".
Any comment is welcome. I'll try on the weekend.
Best regards, Chris.
Le 11/04/12 23:21, Christopher Kormanyos a écrit :
Yes! Absolutely interested! I use fixed-point extensively with hard real-time microcontroller systems. I am particularly interested in stuff like a 7.8 and 15.16 signed split. What 7.8 stands for? 7 bits for the integer part and 8 for the fractional part? I use 7.8, for example, for a signed 16-bit type with one sign bit, seven mantissa binary digits and eight binary fractional digits. I see so, it corresponds to the i_f format.
I guess you prefer a specific class for signed fixed_points and not a template parameter. sfp<7,8> versus fp<int16_t, 7,8> Do you mind if the library propose some meta-function to specify different formats, e.g. format_i_f<7,8>::type and format_i_f<15,16>::type An alternative design is to have a format parameter, so for example the user could use specific formats <snip> where i_f has as parameters the number of integral and fractional bits and r_r has as parameters the range and resolution. Currently my prototype and the C++ proposal uses this r_r format. Others use the total number of bits (width including the sign) and the fractional w_f I can use anything. The great advantage of your selected convention is that it is absolutely clear how many digits there are in mantissa and fraction. I like it. I will try introducing the format as a parameter on my prototype soon.
Do you mind if the rounding strategy is a template parameter? An enumeration or and open policy? Do we even really need a rounding policy? I honestly don't know. I thought the whole deal with fixed-point was to free us from the burdens of formal floating-point representation and obtain efficiency and exactness via near-integer representation. Maybe others have a clear, or more formal, suggestion here.
Converting from fixed_point numbers with different resolution needs rounding. Divide request also a resolution to which round. Best, Vicente
I see so, it corresponds to the i_f format. Your format is fine. Yours is already good.
Converting from fixed_point numbers with different resolution needs rounding. Divide request also a resolution to which round. Oh, I see. Thanks for the clarification.
Best regards, Chris.
<snip> First up, one might want to consider some top-level requirements. - How might fixed-point fit with an extended complex class? - If Boost.Multiprecision or a multiprecision type is ever specified, how might fixed-point fit with it. - If a multiprecision integer type ever gets specified, should the representation of fixed-point be allowed to use it for mantissa and decimal parts?
* Should integers and reals be represented by separated classes? I don't see the need for integers in the first place.
* Should signed and unsigned be represented by separated classes? Yes, in my opinion.
* Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? Very good question. A separate bool flag for sign slows down the library and increases storage requirements. The sign of the left-most limb could be the sign. But this breaks down for all-fractional types. I guess, perhaps, the separate sign information might be a necessity. But I'm not sure.
* Should the library provide arbitrary range and resolution and allocators? Unfortunately, the allocator seems necessary for high digit counts. But perhaps a hybrid container with compile-time width for low limb-count and allocation for a (specifiable, zero allowed) higher limb count could be used here. But be sure to make fixed-point fast for low digit counts, possibly using template specialization when the fixed-point can be represented by a built-in integer type (in assiciation with "get my int type" compile-time helper templates). This is what I have done in the past. Low digit counts is the key range for fixed.
* Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? Where do you start, where do you stop? This is like the sign bit. Do you want extra information for the sub-normals or use some magic values?
* Should fixed_point be convertible to/from integer/float/double? Yes, absolutely, in my opinion.
* Could the result of an arithmetic operation have more range and resolution than his arguments? No. But copy construction and copy assign maybe, whereby the LHS dictates the digit count.
* Is there a need for a specific I/O? Yes.
* is there a need for radix other than 2 (binary)? Coming from a guy who has written *a lot* of specialized number classes... I have always been haunted by radix-10. Never again for me. Radix-2 and don't look back (my opinion).
* Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? It should fit in with Boost.Multiprecision, if there ever is such a thing. Users like me who need a tiny set of trig functions for, say, an 8-bit controller can roll-their-own via template specialization. Don't even get started with cordic, Chebyshev, polynomial expansion, Pade, Taylor, Newton-Raphson, FFT multiplication, AGM, etc., etc., etc. and the rest. Just make the numbers! We will be happy for that because it's really a lot. C++ should have the templated math functions and an extended complex type elsewhere. You just need to make the number types.
* Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another?
* Could expect the same/better performances respect to hand written code? It's implementation-dependent. But if your 7.8 and 15.16 signed splits are slower than single-precision float on an 8-bit core, you will get flack for it.
* What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? It's implementation defined. For small digit counts, I would try to fit it in a built-in type. For medium digit counts, a fixed, optionally fixed-hybrid container of std::uint_fast32_t. For very high counts, use an established fast integer representation with its own fast-multiply (like a potential Boost.Multiprecision).
* Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? For me, boost/fixed_point
it seems that there is no interest or perhaps people are too busy on on vacations Sorry for the late response in this detail. I was really busy. Thank you.
Best regards, Chris.
<snip>
First up, one might want to consider some top-level requirements. - How might fixed-point fit with an extended complex class? Yes, I need this also, but I don't see any major issue. Do you? - If Boost.Multiprecision or a multiprecision type is ever specified, how might fixed-point fit with it. The goals are different, so I think different libraries are needed. One can question if interaction is needed. - If a multiprecision integer type ever gets specified, should the representation of fixed-point be allowed to use it for mantissa and decimal parts? I don't see any problem on using it as underlying representation. My
Le 11/04/12 23:03, Christopher Kormanyos a écrit : prototype has as parameter the underlying type, so this should be possible. Of course, I'm not saying it works now ;-)
* Should integers and reals be represented by separated classes? I don't see the need for integers in the first place.
I'm wondering if the library will be simpler as the operations are not the same. If we have only one class, enable_if should be used to make the difference.
* Should signed and unsigned be represented by separated classes? Yes, in my opinion.
I agree also, even if my prototype use only one class.
* Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? Very good question. A separate bool flag for sign slows down the library and increases storage requirements. The sign of the left-most limb could be the sign. But this breaks down for all-fractional types. I guess, perhaps, the separate sign information might be a necessity. But I'm not sure.
I think that when a single word is enough to represent the fixed-point 2's complement is the bets choice. When more than a word is needed, having the sing on all the word is a lost of space, and as you say whether it is represented represented by left-most word/limb or as a separated data should be an internal decision. In this case using more space seems IMO to be a minor issue.
* Should the library provide arbitrary range and resolution and allocators? Unfortunately, the allocator seems necessary for high digit counts. But perhaps a hybrid container with compile-time width for low limb-count and allocation for a (specifiable, zero allowed) higher limb count could be used here. But be sure to make fixed-point fast for low digit counts, possibly using template specialization when the fixed-point can be represented by a built-in integer type (in assiciation with "get my int type" compile-time helper templates). This is what I have done in the past. Low digit counts is the key range for fixed.
I agree, performances must be preserved for small fixed-points (in width).
* Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? Where do you start, where do you stop? This is like the sign bit. Do you want extra information for the sub-normals or use some magic values?
No, I don't think not-a-fixed-point is something desirable. Implementing a close design could open some optimizations that the open design could forbids ;-) But some one said already that premature optimization is root of all evil, isn't it? Other said KISS.
* Should fixed_point be convertible to/from integer/float/double? Yes, absolutely, in my opinion.
Implicit or explicit conversion?
* Could the result of an arithmetic operation have more range and resolution than his arguments? No. But copy construction and copy assign maybe, whereby the LHS dictates the digit count.
* Is there a need for a specific I/O? Yes.
have you any requirements?
* is there a need for radix other than 2 (binary)? Coming from a guy who has written *a lot* of specialized number classes... I have always been haunted by radix-10. Never again for me. Radix-2 and don't look back (my opinion).
I prefer also to concentrate on Radix-2 and let Radis-10 for another library.
* Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? It should fit in with Boost.Multiprecision, if there ever is such a thing. Users like me who need a tiny set of trig functions for, say, an 8-bit controller can roll-their-own via template specialization. Don't even get started with cordic, Chebyshev, polynomial expansion, Pade, Taylor, Newton-Raphson, FFT multiplication, AGM, etc., etc., etc. and the rest. Just make the numbers! We will be happy for that because it's really a lot. C++ should have the templated math functions and an extended complex type elsewhere. You just need to make the number types.
I hope others share your opinion here.
* Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another? * Could expect the same/better performances respect to hand written code? It's implementation-dependent. But if your 7.8 and 15.16 signed splits are slower than single-precision float on an 8-bit core, you will get flack for it.
I don't have access to this kind of processors. I will contact you once I have confidence with the performances on general purpose processors.
* What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? It's implementation defined. For small digit counts, I would try to fit it in a built-in type.
For medium digit counts, a fixed, optionally fixed-hybrid container of std::uint_fast32_t. For very high counts, use an established fast integer representation with its own fast-multiply (like a potential Boost.Multiprecision). I don't know if I forgot this question. Could the first version of the
Ye, but which one? the faster, the smaller or let the user choose? library be limited to only one builtin underlying representation?
* Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? For me, boost/fixed_point
+1. And the name classes?
it seems that there is no interest or perhaps people are too busy on on vacations Sorry for the late response in this detail. I was really busy. Thank you.
Thanks for your detailed comments, suggestions and opinion. That will help me a lot. Best, Vicente
For medium digit counts, a fixed, optionally fixed-hybrid container
of std::uint_fast32_t. For very high counts, use an established fast integer representation with its own fast-multiply (like a potential Boost.Multiprecision).
I don't know if I forgot this question. Could the first version of the library be limited to only one builtin underlying representation?
Vicente, we can talk all day---and the next and the next. But right now, we don't have any clarity in fixed-point in the community. And we definitely need it! I think that we will be happy to get a basic start---any start---with the boost quality. I truly believe that you can begin with one (and only one) signed fixed-point class based on a single template parameter that is a signed fixed-width built-in integer type. Remember, we don't have anything. And we should welcome getting something with the boost quality. Check out my code for signed 3.4, 7.8, 15.16, 31.32. It's fast. It might give you ideas about simplicity and efficiency. (Although the division and sqrt need improvement.) It also has a sample for sin(x) and exp(x) for small-argument. It supports std::numeric_limits. I am so busy right now that I got to go on with other stuff. My opinion: Don't aim too high at first. Give the community something. Maybe improve it later. Best regards, Chris.
Le 12/04/12 01:13, Christopher Kormanyos a écrit :
For medium digit counts, a fixed, optionally fixed-hybrid container of std::uint_fast32_t. For very high counts, use an established fast integer representation with its own fast-multiply (like a potential Boost.Multiprecision). I don't know if I forgot this question. Could the first version of the library be limited to only one builtin underlying representation? Vicente, we can talk all day---and the next and the next. But right now, we don't have any clarity in fixed-point in the community. And we definitely need it! I think that we will be happy to get a basic start---any start---with the boost quality.
I truly believe that you can begin with one (and only one) signed fixed-point class based on a single template parameter that is a signed fixed-width built-in integer type. Remember, we don't have anything. And we should welcome getting something with the boost quality.
Check out my code for signed 3.4, 7.8, 15.16, 31.32. It's fast. It might give you ideas about simplicity and efficiency. (Although the division and sqrt need improvement.) It also has a sample for sin(x) and exp(x) for small-argument. It supports std::numeric_limits.
I am so busy right now that I got to go on with other stuff.
My opinion: Don't aim too high at first. Give the community something. Maybe improve it later.
Thanks for your advice. My intent is to know what are the expectations so that the library I could propose to Boost has a better change to be accepted. I prefer discussing some time now and try to address the most important requirements. Maybe at the end we conclude what you are saying now. You are welcome to come back to the discussion later on if your too busy now ;-) but the ones you have give are already quite useful. Please let me know from where I can upload your implementation. Sure this will be very useful. Thanks for all, Vicente
Please let me know from where I can upload your implementation. Sure
this will be very useful.
Thanks for all, Vicente
Thanks Vicente. It was an attachment to a previous e-mail. It's in this e-mail again. I've run my code on a variety of 8-bit, 16-bit and 32-bit and 64-bit micros. It's a bare-bones implementation. There may be some ideas of use in there for you. Looking at your code, though, your off to a great start! I am looking forward to your progress with fixed_point. Again, good luck with the project. Best regards, Chris.
I'm afraid I don't understand n3352 (and don't have a lot of time to study it now). I don't understand why there are 4 different types. I would expect fixed point to have at most 2 types: signed and unsigned. I see no point in distinguishing integral and fractional types: the integral type is just setting the binary point to 0? * signed and unsigned must both be supported. Whether that is done via 2 different classes is a design issue. There does have to be some way to support mixed arithmetic between them, but explicit conversion is OK. * Most work in signal processing will use 2's complement arithmetic, since it simplifies hardware implementation in most cases. * It is OK if maximum size is set by some base integer size. Fixed point means, use some underlying base integral type for internal representation (and arithmetic), but interpret the binary point in the appropriate position. This base integral type should probably be a template parameter. * fixed point <-> flt should be provided. fixed.as_double() for example. Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. * I don't need/want automatic conversion of widths with arithmetic operations. I'm not even sure if this can be done in a way that is always correct. * No need for any special I/O, other than some way to pretty print the result. For I/O, and for serialization, it is sufficient to make the required internal members accessible. * c++11 math functions? You mean trig, etc? No need/desire. * Performance is very important. Vicente J. Botet Escriba wrote:
Hi,
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
I have started a prototype http://svn.boost.org/svn/boost/sandbox/fixed_point (there is no doc yet but the basic goal is quite close to the N3352 C++ proposal). This prototype should allow you to play a little bit with.
If yes, what would you like to be changed, added or improved in n3352? Next follows some design decisions that IMO need to be decided before hand.
* Should integers and reals be represented by separated classes? * Should signed and unsigned be represented by separated classes? * Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? * Should the library provide arbitrary range and resolution and allocators? * Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? * Should fixed_point be convertible to/from integer/float/double? * Could the result of an arithmetic operation have more range and resolution than his arguments? * Is there a need for a specific I/O? * is there a need for radix other than 2 (binary)? * Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? * Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another? * Could expect the same/better performances respect to hand written code? * What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? * Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? ... * others you can think of.
Please, replay if you are interested, have some experience in the domain, good ideas, ..
Best regards, Vicente
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I'm afraid I don't understand n3352 (and don't have a lot of time to study it now). I don't understand why there are 4 different types. I would expect fixed point to have at most 2 types: signed and unsigned. I see no point in distinguishing integral and fractional types: the integral type is just setting the binary point to 0? You are right. I guess that the integral types are there to make evident
Le 11/04/12 14:37, Neal Becker a écrit : that the operations applicable to these types are different.
* signed and unsigned must both be supported. Whether that is done via 2 different classes is a design issue. There does have to be some way to support mixed arithmetic between them, but explicit conversion is OK.
The problem appears even if we define a single class with a template parameter for the sign, as the classes will be different types and the class need to take care of mixed arithmetic.
* Most work in signal processing will use 2's complement arithmetic, since it simplifies hardware implementation in most cases.
I'm used to work with 2's complement also.
* It is OK if maximum size is set by some base integer size. Fixed point means, use some underlying base integral type for internal representation (and arithmetic), but interpret the binary point in the appropriate position. This base integral type should probably be a template parameter.
My prototype use the underlying type to manage the size and the sign at once. n3352 uses two classes and has no constraint on the used underlying type type other than it must be large enough, with the possibility to uses several chunks.
* fixed point<-> flt should be provided. fixed.as_double() for example.
Should the fixed point -> flt conversion take care of the rounding policy?
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please?
* I don't need/want automatic conversion of widths with arithmetic operations. I'm not even sure if this can be done in a way that is always correct. Well I guess we can do it correctly;-)
* No need for any special I/O, other than some way to pretty print the result. For I/O, and for serialization, it is sufficient to make the required internal members accessible. I understand that providing access to the underlying type open possible extensions, but the internals would be quite complex when managing chunks of words. Should the library be limited to builtin underlying types without chunks?
* c++11 math functions? You mean trig, etc? No need/desire.
* Performance is very important.
Thanks for your comments, Vicente
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ...
* fixed point<-> flt should be provided. fixed.as_double() for example. Should the
fixed point -> flt conversion take care of the rounding policy?
In my prototype code, every time a right shift is used, rounding policy is applied. rounding policy is a template parameter, with one default (the only one I care about). The default is, template<typename base_type=int> struct rnd { static base_type apply (base_type x, int frac_bits) { return ((x >> (frac_bits-1)) + 1) >> 1; } }; To shift right by 'frac_bits' places, with rounding, we shift right 1 less place, add 1, then shift 1 more place. When followed by saturation, this is the most common rounding operation I use for 2's complement hardware.
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please?
I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ...
* fixed point<-> flt should be provided. fixed.as_double() for example. Should the
fixed point -> flt conversion take care of the rounding policy?
In my prototype code, every time a right shift is used, rounding policy is applied.
rounding policy is a template parameter, with one default (the only one I care about).
The default is, template<typename base_type=int> struct rnd { static base_type apply (base_type x, int frac_bits) { return ((x>> (frac_bits-1)) + 1)>> 1; } };
To shift right by 'frac_bits' places, with rounding, we shift right 1 less place, add 1, then shift 1 more place. When followed by saturation, this is the most common rounding operation I use for 2's complement hardware. I want the library to avoid myself to apply these explicit operations. I don't want to see on my code a shift to apply a round. IMO rounding should be applied when the resolution decreases during a conversion and
Le 12/04/12 00:25, Neal Becker a écrit : the shift must depend on the difference and the rounding policy.
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor? Regards, Vicente
Vicente J. Botet Escriba wrote:
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ...
* fixed point<-> flt should be provided. fixed.as_double() for example. Should the
fixed point -> flt conversion take care of the rounding policy?
In my prototype code, every time a right shift is used, rounding policy is applied.
rounding policy is a template parameter, with one default (the only one I care about).
The default is, template<typename base_type=int> struct rnd { static base_type apply (base_type x, int frac_bits) { return ((x>> (frac_bits-1)) + 1)>> 1; } };
To shift right by 'frac_bits' places, with rounding, we shift right 1 less place, add 1, then shift 1 more place. When followed by saturation, this is the most common rounding operation I use for 2's complement hardware. I want the library to avoid myself to apply these explicit operations. I don't want to see on my code a shift to apply a round. IMO rounding should be applied when the resolution decreases during a conversion and
Le 12/04/12 00:25, Neal Becker a écrit : the shift must depend on the difference and the rounding policy.
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor?
Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Le 12/04/12 01:34, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 00:25, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ...
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor?
Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Do you really need a run-time fixed-point library? If yes, what is your context of use. Vicente
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:34, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 00:25, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ...
Also, fixed (double, integer_bits, frac_bits) constructor, or something like it. Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor?
Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Do you really need a run-time fixed-point library? If yes, what is your context of use.
I use if with python, but for the purpose of this discussion, we can probably ignore run-time.
Le 12/04/12 01:45, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:34, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 00:25, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 11/04/12 14:37, Neal Becker a écrit : ... > Also, > fixed (double, integer_bits, frac_bits) constructor, or something like > it. Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor?
Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Do you really need a run-time fixed-point library? If yes, what is your context of use.
I use if with python, but for the purpose of this discussion, we can probably ignore run-time. Oh, I remember it now.Yes, I would prefer we concentrate in a compile-time solution.
Vicente
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:45, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:34, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 00:25, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
> Le 11/04/12 14:37, Neal Becker a écrit : ... >> Also, >> fixed (double, integer_bits, frac_bits) constructor, or something like >> it. > Could you be more precise, please? I want to be able to construct a fixed from a float, specifying the number of integer and fractional bits (or equivalent).
I don't understand. If the fixed_point type conveys the number of integer and fractional bits, why do you want to give them as parameters of the constructor?
Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Do you really need a run-time fixed-point library? If yes, what is your context of use.
I use if with python, but for the purpose of this discussion, we can probably ignore run-time. Oh, I remember it now.Yes, I would prefer we concentrate in a compile-time solution.
Vicente
Having said that, my main use case will be run-time, because I'm primarily using hybrid python-c++ systems. So while we can plan a design of compile-time, I want to always keep run-time in mind. If the boost solution does not support run-time, I will need to convert it by hand. Hopefully that will not be difficult. At least whatever solution is proposed for boost, I hope some thought is given to how it could be used or modified for runtime, and that would not be made more difficult than necessary.
Le 12/04/12 12:44, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:45, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 01:34, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
Le 12/04/12 00:25, Neal Becker a écrit : > Vicente J. Botet Escriba wrote: > >> Le 11/04/12 14:37, Neal Becker a écrit : Sorry for the confusion: my comment was about run-time specified fixed point type. If using compile-time specification of integer and fractional bits, then you're correct - no need for those constructor parameters.
Do you really need a run-time fixed-point library? If yes, what is your context of use.
I use if with python, but for the purpose of this discussion, we can probably ignore run-time. Oh, I remember it now.Yes, I would prefer we concentrate in a compile-time solution.
Vicente
Having said that, my main use case will be run-time, because I'm primarily using hybrid python-c++ systems. So while we can plan a design of compile-time, I want to always keep run-time in mind. If the boost solution does not support run-time, I will need to convert it by hand. Hopefully that will not be difficult.
At least whatever solution is proposed for boost, I hope some thought is given to how it could be used or modified for runtime, and that would not be made more difficult than necessary.
I will try to take your concern in account, but this clearly duplicates the library, even if the run-time design should be easier. Best, Vicente
Vicente J. Botet Escriba wrote: ...
I want the library to avoid myself to apply these explicit operations. I don't want to see on my code a shift to apply a round. IMO rounding should be applied when the resolution decreases during a conversion and the shift must depend on the difference and the rounding policy.
I think we're saying the same thing here. In order to do arithmetic on fixed point types, (at least, addition/subtraction), we need to first align the binary points. This aligning of the binary points is 'shift', is is not? It may be followed by applying a rounding policy.
Le 12/04/12 01:38, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
I want the library to avoid myself to apply these explicit operations. I don't want to see on my code a shift to apply a round. IMO rounding should be applied when the resolution decreases during a conversion and the shift must depend on the difference and the rounding policy. I think we're saying the same thing here. In order to do arithmetic on fixed
... point types, (at least, addition/subtraction), we need to first align the binary points. This aligning of the binary points is 'shift', is is not? It may be followed by applying a rounding policy.
Yes, I guess. I wanted just to be sure that these are implementation details. Regards, Vicente
Vicente J. Botet Escriba wrote:
... I understand that providing access to the underlying type open possible extensions, but the internals would be quite complex when managing chunks of words. Should the library be limited to builtin underlying types without chunks?
builtin underlying types is sufficient for anything I've ever needed. If I ever need >64 bits, I can always resort to chunking myself. If chunking can be implemented without substantial cost, then go for it. But, I don't want to pay for what I don't use.
Le 12/04/12 00:29, Neal Becker a écrit :
Vicente J. Botet Escriba wrote:
... I understand that providing access to the underlying type open possible extensions, but the internals would be quite complex when managing chunks of words. Should the library be limited to builtin underlying types without chunks? builtin underlying types is sufficient for anything I've ever needed. If I ever need>64 bits, I can always resort to chunking myself. If chunking can be implemented without substantial cost, then go for it. But, I don't want to pay for what I don't use.
Neither me. I think that it is a good compromise to provide only the underlying representation when the user has a way to master it or when it is not an implementation detail. When the fixed point is small enough to fill in a builtin the class can provide a underlying function that get it. It is more difficult to provide it when the class need to use chunks. I could understand that the user could need a way to get all the chunks without any associated semantic, but not the direct representation except if the representation is not an implementation detail. Best, Vicente
Hi Vicente, Vicente J. Botet Escriba wrote:
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
You might like to review old discussions of fixed point, e.g.: http://thread.gmane.org/gmane.comp.lib.boost.devel/157744 http://thread.gmane.org/gmane.comp.lib.boost.devel/158019 http://thread.gmane.org/gmane.comp.lib.boost.devel/178257 and several other threads.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
Thanks for pointing out that doc which I'd not seen before. I've not yet read it properly. FWIW, my view is that: - Some people conflate fixed point with features like saturation, which I would prefer to decouple. Fixed-point arithmetic without saturation is useful, as is integer arithmetic with saturation. So I'd prefer to make them orthogonal, but compatible, concepts. - There are difficult decisions to make about the result types of arithmetic operations, analogous to this: int32_t a, b; int64_t c; c = a+b; // oops. It is tempting to make the return type of e.g. operator+ large enough to accommodate the largest possible sum, and to truncate only when the assignment occurs. But I think this will have an unavoidable runtime overhead. Some will argue that expression templates can be used to work around this, but that dramatically increases the complexity of the library. - There are also difficult decisions to make about implicit and explicit conversions. These are some of the same questions that you asked in your post. Different people will have different requirements. It is perhaps because of this that everyone tends to "roll their own", and no standard implementation has emerged. Regards, Phil.
<snip>
There are difficult decisions to make about the result types of arithmetic operations, analogous to this:
int32_t a, b; int64_t c; c = a+b; // oops.
<snip>
It is tempting to make the return type of e.g. operator+ large enough to accommodate the largest possible sum, and to truncate only when the assignment occurs. <snip>
Well, everyone dies, as mentioned below, roll-their-own fixed-point. There will be lots of valid opinions on this one. But I have had good results from the following policy: 1) Forbid binary arithmetic among fixed-points with non-like parameter types. 2) Support copy construction and copy assignment of differing types, whereby *this and the LHS of copy-assign, respectively, determine the digits in the result --- be it larger or smaller (compile-time enable_if is handy here). <snip>
It is perhaps because of this that everyone tends to "roll their own", and no standard implementation has emerged.
Which, quite frankly, I have done one time too many. I definitely crave fixed-point support. Good luck on the project. Best regards, Chris.
Hi Vicente,
Vicente J. Botet Escriba wrote:
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
You might like to review old discussions of fixed point, e.g.:
http://thread.gmane.org/gmane.comp.lib.boost.devel/157744 http://thread.gmane.org/gmane.comp.lib.boost.devel/158019 http://thread.gmane.org/gmane.comp.lib.boost.devel/178257
and several other threads. Thanks for pointing to these threads. I will read them carefully.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
Thanks for pointing out that doc which I'd not seen before. I've not yet read it properly.
FWIW, my view is that:
- Some people conflate fixed point with features like saturation, which I would prefer to decouple. Fixed-point arithmetic without saturation is useful, as is integer arithmetic with saturation. So I'd prefer to make them orthogonal, but compatible, concepts. Would the overflow::ignore policy responds to your needs?
- There are difficult decisions to make about the result types of arithmetic operations, analogous to this:
int32_t a, b; int64_t c; c = a+b; // oops.
It is tempting to make the return type of e.g. operator+ large enough to accommodate the largest possible sum, and to truncate only when the assignment occurs. But I think this will have an unavoidable runtime overhead. Are you referring to the fact that a and b must be promoted before? or
Le 11/04/12 20:23, Phil Endecott a écrit : that the operation is done on the promoted type? Or maybe both? The promotion is not really needed always. For example fp<int64_t,32,0> a,b; fp<int64_t,33,0> c; c=a+b; No promotion needed in this case, but the operation is done on int64_t.
Some will argue that expression templates can be used to work around this, but that dramatically increases the complexity of the library.
An alternative is to define functions that have the result type as template parameter, so if what you want is fp<int32_t,32,0> a,b; fp<int32_t,32,0> c; c=a+b; you use instead c = plus<fp<int32_t,32,0>>(a,b); here plus could be optimized and don't promote to fp<int64_t,33,0>. I have not implemented this yet, but I expect this to be as efficient as if we did int32_t a, b; int32_t c; c = a+b; in the case overflow is ignored. Of course, and implementation should be needed to probe the expectations.
- There are also difficult decisions to make about implicit and explicit conversions. Are you referring to the conversion between fixed-point types with different rand or resolution? Yes, this is a conflicting point and has a deep impact on the design of the library. I don't know if we can manage by providing both.
My prototype as well as the C++ proposal allows implicit conversions when there is no loss of data and requires some kind of fixed point cast if information could be loss. { unsigned_number<2,-3> n1((index(1))); unsigned_number<2,-2,round::negative> n2; n2=number_cast<unsigned_number<2,-2,round::negative> >(n1); } An explicit convert function could also be used to avoid repeating the target type convert_to(n1, n2);
These are some of the same questions that you asked in your post. Different people will have different requirements. It is perhaps because of this that everyone tends to "roll their own", and no standard implementation has emerged.
You are surely right and perhaps we can not provide something that satisfy all the requirements. This was the main reason of my post, to know the expectations of the Boost community. I hope however that we can have a Boost library that solves some of the major issues, whether the library could be used as a base for standardization is something that we could discuss later, if a library emerge and is accepted in Boost. Thanks again, Vicente
Le 11/04/12 23:19, Vicente J. Botet Escriba a écrit :
Le 11/04/12 20:23, Phil Endecott a écrit :
Hi Vicente,
Vicente J. Botet Escriba wrote:
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
You might like to review old discussions of fixed point, e.g.:
http://thread.gmane.org/gmane.comp.lib.boost.devel/157744 http://thread.gmane.org/gmane.comp.lib.boost.devel/158019 http://thread.gmane.org/gmane.comp.lib.boost.devel/178257
and several other threads. Thanks for pointing to these threads. I will read them carefully. Hi,
I have take a look at these threads and in particular to your fixed.h file. Next follows some reactions // Meaning of ++ and -- // -------------------- // // It could be argued that the meaning of ++ and -- is unclear: do they add/subtract // 1, or do they add/subtract the type's delta? (...there is an example of something // where they do delta...). I note, however, that the built-in floating point types // add and subtract 1, as does the proposed "Embedded C" fixed-point type. // Therefore, ++ and -- are defined to do that for fixed and ufixed. N3352 don't include them at all. From one side, I consider you are right and we should follow the builtin float semantics.
From the other side, there is a precedent with chrono::duration that defines them increasing the representation. While fixed_point is closer to the chrono design the goal of fixed_points is not to provide units but just another way to work with 'reals" so increasing the delta is not the good solution.
++x; and x+=1; should be equivalent when both are provided. Note that chrono doesn't allow the preceding operation. The user needs to specify what is been added, seconds, milliseconds, ... I believe the best is to define the operator++ as if we did +=1. // Fixed Point Constants // --------------------- // // It would be ideal if code such as // // const ufixed<2,14> pi = 3.1415926; // // could have no run-time overhead. To be investigated... The library could provide a constructor from ratio (conversion) constexpr ufp<2,14> pi(ratio<31415926,10000000>); While this is more verbose, it seams acceptable and there should not be run-time overhead. // Overflow and Saturation // ----------------------- // // Users of fixed-point arithmetic sometimes want to detect overflow, or for // operations to saturate when overflow would occur. However, users of // floating-point and integer arithmetic also sometimes want these features, but they // are not provided by the built-in C/C++ types. The approach taken in this // implementation is to follow the behavior of the built-in types, i.e. to not // handle overflow; values will wrap-around. This is inline with the design of Chrono. I will see how I can change my prototype so that overflow is managed by the underlying type. Does this mean that the library should provide an integer class with an overflow template parameter? Been there, why not define a class with a range and overflow parameter. The cardinal and integral classes defined in n3352 correspond quite closely to the needs. // Division By Zero // ---------------- // // compare with int and float... // // embedded C fixed is undefined What about just asserting when dividing by 0? // Benchmarks // ---------- // // The following results are based on the benchmark programs in the ... directory. Could I have access to these benchmarks? Just a comment on your implementation. It seems that the implementation expect the integral and fractional parts to be unsigned (see the use of static_unsigned_max) even if the template parameters are signed (int). This is way I don't like the i-f format, as it is not evident to say the the number of integral or fractional bits is -3. I guess you don't use it never this way. template<int XWB, int XFB, typename X_VAL_T, int YWB, int YFB, typename Y_VAL_T> pbe::fixed<boost::static_unsigned_max<XWB,YWB>::value, boost::static_unsigned_max<XFB,YFB>::value> operator+(pbe::fixed<XWB,XFB,X_VAL_T> x, pbe::fixed<YWB,YFB,Y_VAL_T> y) { typedef pbe::fixed<boost::static_unsigned_max<XWB,YWB>::value, boost::static_unsigned_max<XFB,YFB>::value> result_t;
- There are difficult decisions to make about the result types of arithmetic operations, analogous to this:
int32_t a, b; int64_t c; c = a+b; // oops.
It is tempting to make the return type of e.g. operator+ large enough to accommodate the largest possible sum, and to truncate only when the assignment occurs. But I think this will have an unavoidable runtime overhead.
Are you referring to the fact that a and b must be promoted before? or that the operation is done on the promoted type? Or maybe both?
The promotion is not really needed always. For example
fp<int64_t,32,0> a,b; fp<int64_t,33,0> c; c=a+b;
No promotion needed in this case, but the operation is done on int64_t.
Some will argue that expression templates can be used to work around this, but that dramatically increases the complexity of the library.
An alternative is to define functions that have the result type as template parameter, so if what you want is fp<int32_t,32,0> a,b; fp<int32_t,32,0> c; c=a+b;
you use instead
c = plus<fp<int32_t,32,0>>(a,b);
here plus could be optimized and don't promote to fp<int64_t,33,0>. I have not implemented this yet, but I expect this to be as efficient as if we did
int32_t a, b; int32_t c; c = a+b;
in the case overflow is ignored. Of course, and implementation should be needed to probe the expectations.
After reading the post of M. Vitale here (http://thread.gmane.org/gmane.comp.lib.boost.devel/158019) the concern related to the type of the arithmetic operations I think that there are two different contexts: C1- Arbitrary large fixed_points types (as used in N3352) In this case the result is large enough to don't loss information so the type can be deduced. Any overflow and rounding policy are good as no applied. The liability is a loss of performance on the arithmetic operation. Note that here the use of expression templates could improve the performances if the result type needs several chunks. C2- Bounded fixed-point types. We can not in a general case avoid overflow checking during the operation itself, but the rounding can be any. I see two options: O1 - expression templates that will apply the arithmetic operation with the knowledge of the result type. 'implementation defined expression template' operator+(A, B); E.g. if int64_t is available ufp<63,0> a, b; ufp<64,0> c,d; c=a+b; // OK and possibly direct c=d+b; // OK, returns ET and apply overflow policy of c c=a+d; // OK, returns ET and apply overflow policy of c While this works at first level things start to be more complex when there are two operators ufp<64,0> c,d,e,f; c=d+e+f; Should partial overflows be taken in account? O2- don't define the operation in this case (compile fail) and let the user specify the result type using a different function. 'fixed_point class deduced from A and B operator+(A, B); // when the result is representable without overflow. template <typename RT, typename A, typename B> RT add(A, B); E.g. if int64_t is available ufp<63,0> a, b; ufp<64,0> c; c=a+b; // OK c=c+b; // compile fail c=a+c; // compile fail c=c+b; // compile fail c=add<ufp<64,0,OV>>(a,c); // Ok, applying the OV policy. My particular preference is for O2. I don't see how a single class could take in account the context C1 and C2 without adding a new template parameter, as in some domains the fixed_point class must be bounded, while in others it is more important the precision than the efficiency. I would say that we need two family classes * fixed but arbitrary wide (N3352). * fixed and bounded by the widest integer builtin type or even by the user (something like my prototype).
- There are also difficult decisions to make about implicit and explicit conversions. Are you referring to the conversion between fixed-point types with different range or resolution? Yes, this is a conflicting point and has a deep impact on the design of the library. I don't know if we can manage by providing both.
My prototype as well as the C++ proposal allows implicit conversions when there is no loss of data and requires some kind of fixed point cast if information could be loss.
{ unsigned_number<2,-3> n1((index(1))); unsigned_number<2,-2,round::negative> n2; n2=number_cast<unsigned_number<2,-2,round::negative> >(n1); }
An explicit convert function could also be used to avoid repeating the target type
convert_to(n1, n2);
Do you have any comment on this implicit/explicit conversion approach? // fixed<15,16> f1, f2; // Signed fixed-point values with 15 bits of integer part // // and 16 bits of fractional part. // f1 = 1.2345; // Conversion from floating point. // f2 = f1 - 2; // Mixed arithmetic with integers. // f2 = f1 / f2; // Arithmetic on fixed-point values. This should need a explicit conversion with my approach, as we reduce the range and/or the resolution. f1 = fixed<15,16>(1.2345); f2 = fixed<15,16>(f1 - 2); f2 = fixed<15,16>(f1 / f2); or f2 = substract<fixed<15,16> >(f1,2); f2 = divide<fixed<15,16> >(f1,f2); It is clear from these examples that safety has a cost. Would this syntax be convenient? Or, do we need something intermediary as f1 = convert(1.2345); f2 = convert(f1 - 2); f2 = convert(f1 / f2); The template function convert will return a wrapper of its parameter that is accepted as an implicit conversion. template <typename T> struct convert_tag; template <typename T> convert_tag<T> convert(T const&); fixed(convert_tag<float>); // implicit template <int I,int F> fixed(convert_tag<fixed<I,F>>); // implicit My prototype contains already an index function and a index_tag<T> template that is used to construct a fixed point from a valid and unchecked representation. Best, Vicente
<big snip>
Would this syntax be convenient? Or, do we need something intermediary as f1 = convert(1.2345); f2 = convert(f1 - 2); f2 = convert(f1 / f2);
The template function convert will return a wrapper of its parameter that is accepted as an implicit conversion.
<snip>
Best, Vicente
As always, good luck with a project of such importance and complexity. I'm relatively new here. But I am concerned about the above-mentioned dialog. Perhaps I have not understood this dialog because the discussion was at a relatively high level of C++ abstraction. But boost already has a policy on mixing specialized numeric types with built-in types. As far as I know, a specialized type in boost is supposed to seamlessly interact with all built-in types on both the left-hand as well as the right-hand side of all expressions. I believe that boost mandates implicit conversion to built-in types *without* a conversion-wrapper. This means that if the user selects to lose performance by mixing, say, double with fixed_point, then the user did it---willingly, that is on purpose! About converting fixed_point<unsigned bits_mantissa, signed bits_fraction> from one mantissa/fraction representation to another, I say don't ever do it without explicit ctor call or assignment operator. If you don't do this, then the code amount blows up beyond what it reasonably should. You might have this: fixed_point<15, -16> radius<123, 100>(); // Ratio of approx. 1.23 And you want to go to this: fixed_point<15, -16> result1 = pi_rep<15, -16>() * (radius * radius); // Should work! OK. But if you want to go to this: fixed_point<7, -8> result2 = pi_rep<15, -16>() * (radius * radius); // Should not work! In my opinion, it should not work. The user should explicitly convert to the other fixed-point type with copy-construct. But this should work: fixed_point<15, -16> result3 = 3.141592654 * (radius * radius); // Should work! And if you ever get into stuff like this: fixed_point<8, -1024> high_precision_decimal<1, 3>(); ... Then you may want to consider interaction with boost.math. Best regards, Chris.
Le 16/04/12 23:44, Christopher Kormanyos a écrit :
<big snip>
Would this syntax be convenient? Or, do we need something intermediary as f1 = convert(1.2345); f2 = convert(f1 - 2); f2 = convert(f1 / f2); The template function convert will return a wrapper of its parameter that is accepted as an implicit conversion. <snip> Best, Vicente As always, good luck with a project of such importance and complexity.
I'm relatively new here. But I am concerned about the above-mentioned dialog.
Perhaps I have not understood this dialog because the discussion was at a relatively high level of C++ abstraction. But boost already has a policy on mixing specialized numeric types with built-in types. As far as I know, a specialized type in boost is supposed to seamlessly interact with all built-in types on both the left-hand as well as the right-hand side of all expressions.
I believe that boost mandates implicit conversion to built-in types *without* a conversion-wrapper. This means that if the user selects to lose performance by mixing, say, double with fixed_point, then the user did it---willingly, that is on purpose! I'm seen the alternatives. How the user will use the library is explicit conversion is needed each time there is a lost of range or resolution.
It is clear that coding with this rule and mixing builtins is cumbersome. I could admit that mixin builtins could be take as some kind of implicit conversion and f1-2 could be interpreted as f1 - (decltype(f1))(2) But the conversion of f1 - (decltype(f1))(2) to f2 should be explicit in a open world and implicit in a closed world. (see below).
About converting
fixed_point<unsigned bits_mantissa, signed bits_fraction>
from one mantissa/fraction representation to another, I say don't ever do it without explicit ctor call or assignment operator. If you don't do this, then the code amount blows up beyond what it reasonably should.
You might have this: fixed_point<15, -16> radius<123, 100>(); // Ratio of approx. 1.23
And you want to go to this: fixed_point<15, -16> result1 = pi_rep<15, -16>() * (radius * radius); // Should work!
OK.
Well, it should or not. I think that it should work only if A * A -> A which I pretend is not always a good thing. I'm not saying that in other contexts this is not acceptable. I think that we have two kind of fixed-point arithmetic * open A * A -> 2A * close A * A -> A Each one of these arithmetic should be supported by different class families. We could use the same name in different namespaces. Users using only one of this families will not see the naming difference just adding a using declaration. Do you expect this to work in the closed fixed point-world fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>(); Or should the user need to convert the parameters before to fixed_point<4, -14>? fixed_point<4, -14> result2 = fixed_point<4, -14>(pi_rep<2, -8>()) * fixed_point<4, -14>(pi_rep<2, -6>()); That is, does the closed fixed-point hierarchy define mixed fixed-point arithmetic, other than the one with builtin? A*B->C In my opinion it will be confusing if A*A->A and A*B->C
But if you want to go to this: fixed_point<7, -8> result2 = pi_rep<15, -16>() * (radius * radius); // Should not work!
In my opinion, it should not work. The user should explicitly convert to the other fixed-point type with copy-construct. I agree this conversion must be explicit in any case.
But this should work: fixed_point<15, -16> result3 = 3.141592654 * (radius * radius); // Should work!
In a closed world, yes. Best, Vicente
I believe that boost mandates implicit conversion to built-in types
*without* a conversion-wrapper. This means that if the user selects to lose performance by mixing, say, double with fixed_point, then the user did it---willingly, that is on purpose!
I'm seen the alternatives. How the user will use the library is explicit conversion is needed each time there is a lost of range or resolution.
It is clear that coding with this rule and mixing builtins is cumbersome. I could admit that mixin builtins could be take as some kind of implicit conversion and
It is a lot of coding. It was previously, in fact, my preference to require explicit construction and disallow and implicit mixing of the specialized number type with built-in types. But I later learned that boost.math follows the other strategy. This is the only reason why I keep mentioning this point, because of compatibility with boost.math and a potential boost.multiprecision.
About converting from one mantissa/fraction representation to another, I say don't ever do it without explicit ctor call or assignment operator. If you don't do this, then the code amount blows up beyond what it reasonably should.
Well, it should or not. I think that it should work only if A * A -> A You can never please all of the people all of the time. But my preference is exclusively supporting the closed world. I personally do not like it if results grow-to-size. There will certainly be varying opinions on this.
I think that we have two kind of fixed-point arithmetic * open A * A -> 2A * close A * A -> A It just scares me to think of all the coding you will need. Explicit ctor conversion from one size fixed-point to another and assignment operator should be enough. And you can keep the code amount down. But, again, there will be different opinions on this in the community.
Each one of these arithmetic should be supported by different class families. We could use the same name in different namespaces. Users using only one of this families will not see the naming difference just adding a using declaration. Do you really want to put yourself through this kind of pain?
Do you expect this to work in the closed fixed point-world fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>(); I do. Others might not.
After all I posted, perhaps a simple summary of my thoughts might help. Basically, I recommend the following: * Do support implicit conversion from built-in types (compatibility with strategy of boost.math). * Do not support result resizing or mixed fixed-point *intelligence*. * Do support explicit conversion of mixed fixed-point but *only* via explicit ctor and copy-assign.If you take a moment to consider these top-level design choices, you will find that they, in general, lead to the simplest code and reduce the sources of error for both author and users alike. I finally adopted this strategy with my *third* formal fixed-point class. But again, one person alone can never be right and many experienced developers will have other opinions and, eventually, find the right mix in cooperation. Thanks, Vicente. Best regards, Chris.
Le 17/04/12 22:48, Christopher Kormanyos a écrit :
>>> I believe that boost mandates implicit conversion to built-in types
>>> *without* a conversion-wrapper. This means that if the user selects to
>>> lose performance by mixing, say, double with fixed_point, then
>>> the user did it---willingly, that is on purpose!
>> I'm seen the alternatives. How the user will use the library is explicit
>> conversion is needed each time there is a lost of range or resolution.
>> It is clear that coding with this rule and mixing builtins is
>> cumbersome. I could admit that mixin builtins could be take as some kind
>> of implicit conversion and
> It is a lot of coding. It was previously, in fact, my preference to
> require explicit construction and disallow and implicit mixing
> of the specialized number type with built-in types.
> But I later learned that boost.math follows the other strategy.
> This is the only reason why I keep mentioning this point,
> because of compatibility with boost.math and a potential
> boost.multiprecision.
I think I will implement both, depending on the family (see below).
>
>>> About converting
>>> from one mantissa/fraction representation to another, I say don't ever do
>>> it without explicit ctor call or assignment operator. If you don't do this,
>>> then the code amount blows up beyond what it reasonably should.
>> Well, it should or not. I think that it should work only if
>> A * A -> A
> You can never please all of the people all of the time. But my
> preference is exclusively supporting the closed world. I personally
> do not like it if results grow-to-size. There will certainly be
> varying opinions on this.
Well, the fact is that I need the open world in my application, and I
see that other use to work with the closed world with satisfaction.
>
>> I think that we have two kind of fixed-point arithmetic
>> * open A * A -> 2A
>> * close A * A -> A
> It just scares me to think of all the coding you will need.
> Explicit ctor conversion from one size fixed-point to another
> and assignment operator should be enough. And you can keep
> the code amount down. But, again, there will be different
> opinions on this in the community.
>
>> Each one of these arithmetic should be supported by different class
>> families. We could use the same name in different namespaces. Users
>> using only one of this families will not see the naming difference just
>> adding a using declaration.
> Do you really want to put yourself through this kind of pain?
I have started to add a Family parameter to my prototype. This family
gives some properties as
* if builtins are implicit/explicitly convertible to/from fixed-points,
* if the fixed-point number is implicit/explicitly convertible from
other fixed-points when there is a possible loss of information,
* whether the its arithmetic operations are closed or open,
* whether there is a bound for the underlying type or it is unbounded
and uses chunks when needed.
Users of a fixed-point class could then use template aliases (if
supported) to define the fixed-point numbers adapted to its domain if
the family is always the same.
Note that operations between different families could be possible. We
need just to decide when this has a sense ;-)
IMO closed+open should be open and bounded+unbounded->unbounded. The
conversion axes takes in account just one fixed-point, so there is no
issue for them.
I recognize that this makes more complex the library, but not so much,
but I guess that this will help to provide a fixed-point library that
should please most of people.
Any better name for the family parameter is welcome. Domain?
For example the family/domain I need is explicits conversions even for
builtins, open arithmetic and bounded underlying type even smaller than
the intmax type of the machine.
>
>> Do you expect this to work in the closed fixed point-world
>> fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>();
> I do. Others might not.
>
> After all I posted, perhaps a simple summary of my thoughts might help.
> Basically, I recommend the following:
>
> * Do support implicit conversion from built-in types (compatibility with strategy of boost.math).
> * Do not support result resizing or mixed fixed-point *intelligence*.
So you don't expect the preceding to work
fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>();
> * Do support explicit conversion of mixed fixed-point but *only* via explicit ctor and copy-assign.
Do you find the implicit conversion when there is no loss of information
not useful?
> If you take a moment to consider these top-level design choices,
> you will find that they, in general, lead to the simplest code and
> reduce the sources of error for both author and users alike.
As you can see my needs are different. I understand yours also.
In order to get your design you will need to use implicit builtin
conversion, explicit fixed-points conversions, closed arithmetic and I
don't know if you need bounded or unbounded fixed-points.
>
> I finally adopted this strategy with my *third* formal fixed-point class.
>
> But again, one person alone can never be right and many experienced
> developers will have other opinions and, eventually, find the right
> mix in cooperation.
>
Thanks for all your comments that encourage myself to try to make a
better library. Even if at some points in time it could seem that the
library could be to complex and that I'm building a cathedral I hope at
the end of the walk it will easy of use and efficient.
Best,
Vicnte
Do you expect this to work in the closed fixed point-world
fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>(); I do. Others might not.
So you don't expect the preceding to work fixed_point<4, -14> result2 = pi_rep<2, -8>() * pi_rep<2, -6>();
Thank you for the careful reading, Vicente. I was going too fast and did not see the different bits in pi_rep(). No, I don't expect it to work. I don't even want it to. Others might expect it to work.
Thanks for all your comments that encourage myself to try to make a better library. Even if at some points in time it could seem that the library could be to complex and that I'm building a cathedral I hope at the end of the walk it will easy of use and efficient.
Best, Vicnte
We, in the community, don't have any clearly specified fixed-point implementation. This forces everyone to "roll-their-own", as was posted previously. I believe that we definitely need that solid *first implementation*. You know, the C language actually has a spec for a <7, -23> fixed-point. I use this on Atmel(R) AVR(R) 8-bit processors. Hardly anyone actually knows about it. Maybe you want to consider C-compatibility. (I don't care about C-compatibility, others might). It is here: http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnum... "ISO/IEC TR 18037, Programming languages --- C --- Extensions to support embedded processors" Best regards, Chris.
<big snip>> This should need a explicit conversion with my approach, as we reduce the range and/or the resolution.
f1 = fixed<15,16>(1.2345); f2 = fixed<15,16>(f1 - 2); f2 = fixed<15,16>(f1 / f2);
Would this syntax be convenient? Or, do we need something intermediary as f1 = convert(1.2345); f2 = convert(f1 - 2); f2 = convert(f1 / f2);
The template function convert will return a wrapper of its parameter that is accepted as an implicit conversion.
<snip>
Best, Vicente
As always, good luck with a project of such importance and complexity. I believe that boost mandates implicit conversion to built-in types *without* a conversion-wrapper. I think that this should work: fixed_point<15, -16> result3 = 3.141592654 * (radius * radius); // Should work! And if you ever get into stuff like this: fixed_point<8, -1024> one_third<1, 3>(); ... Then you may want to consider interaction with boost.math or a potential boost.multiprecision. Best regards, Chris.
Vicente J. Botet Escriba wrote:
Hi,
the recent discussion on the MultiplePrecission Arithmetic library has show that some people has its ow fixed point library.
Is there an interest in a Boost library having as base http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?
I have started a prototype http://svn.boost.org/svn/boost/sandbox/fixed_point (there is no doc yet but the basic goal is quite close to the N3352 C++ proposal). This prototype should allow you to play a little bit with.
If yes, what would you like to be changed, added or improved in n3352? Next follows some design decisions that IMO need to be decided before hand.
* Should integers and reals be represented by separated classes? * Should signed and unsigned be represented by separated classes? * Should the library use a specific representation for signed numbers (separated sign, 2-complement? Let the user choose? * Should the library provide arbitrary range and resolution and allocators? * Should the library be open to overflow and rounding or just implement some of the possible policies? and in this case which ones? * Should fixed_point be convertible to/from integer/float/double? * Could the result of an arithmetic operation have more range and resolution than his arguments? * Is there a need for a specific I/O? * is there a need for radix other than 2 (binary)? * Should the library implement the basic functions, or should it imperatively implement the C++11 math functions? Could a first version just forward to the c++11 math functions? * Should the library support just one of the know ways to name a fixed-point, a U(a,b), nQm, ...? Provide some ways to move from one to another? * Could expect the same/better performances respect to hand written code? * What should be the size used by a fixed_point instance? _fast? _least? Should the user be able to decide which approach is better for his needs? * Which should be the namespace? boost? boost/fixed_point? boost/binary_fixed_point? boost/bfp? ... * others you can think of.
Please, replay if you are interested, have some experience in the domain, good ideas, ..
Best regards, Vicente
Missed this thread, only just came across it while catching up on things. I think 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-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 Good luck, Michael Marcin
participants (6)
-
Andrii Sydorchuk -
Christopher Kormanyos -
Michael Marcin -
Neal Becker -
Phil Endecott -
Vicente J. Botet Escriba