Date: Thu, 13 Oct 2016 20:41:27 +0000 (UTC) From: Christopher Kormanyos
I discuss P0106R0 (a revision to N3352) in my paper, the latest draft of which is always available here: https://github.com/ johnmcfarlane/fixed_point/blob/master/doc/p0037.md#p0106 I'm honestly not sure which approach is preferable overall. The set of features and qualities requested during SG14 and SG6 meetings is large and conflicting. It includes minimal build times, minimal run-time overhead, every rounding and overflow strategy listed in P0105, decimal radix and support for specialized fixed-point instructions on embedded architectures. Hi John. Thanks for visiting this thread.
My recommendation would be to limit the scope of the proposal
to a realistic level in the SGs so that we can end up with anything
at all within a reasonable time scale. We could consider back porting
some (but probably not all) of SG14's specified interface to Boost
if that helps move anything along.
A second pair of implementor eyes would be a huge help. I should point out that although it hasn't seen much attention lately, P0106 may still be active. (Frankly, the evolution of my design has been largely a process of slowly copying or facilitating all the most popular from Lawrence's proposal!) One problem P0037 faces - even if it were to be standardized - would be that alone, it only provides fixed-point arithmetic. It's designed to work with types that also solve arbitrary width, rounding and overflow but those types are not part of any proposal. In particular, without an arbitrary-width integer type, it's very difficult to use fixed_point<> safely.
I was also wondering about decimal radix, but I don't know if it
might simply be better to identify those 80% of the most popular use cases and simply specify these. At least it would get the library
moving forward and people could use fixed-point in C++. This is basically what we tried to do with the GSoC project.
That makes sense. I at least want to have a solution which doesn't close the door on decimal in future additions. Here's my current plan: https://github.com/johnmcfarlane/fixed_point/blob/master/doc/p0037.md#non-bi...
In your work I've been experiencing some trouble with>> the division routine. Can you elaborate? Was this recently? I've been trying out numerous strategies for arithmetic operators. My current preferred approach is to pad the left-hand operand before performing the division but that's only been checked in for a few months.
I'm not sure about the design, and error on my side is
a likely possibility. But division operator in the master branch seems like it does not pad before divide. This might give the wrong result.
I hope that's not the case but it's a tough operator to get right - especially with 32-bit operands. If you ever find a good example of this happening I'd be very interested in it. At least when using the elastic alias, precision loss should be avoidable (beyond inevitable approximation of rational numbers and x/0). tl;dr: The details of padding in the division operator follow... The padding is done on this line: https://github.com/johnmcfarlane/fixed_point/blob/91c3f2e272f9fd5e33ffb4dc2d... It's on display in this test: https://github.com/johnmcfarlane/fixed_point/blob/1cc7ceaaff5422667ae962995a... In the above test, the two operands have a single fractional digits. If operator/ did not pad the LHS, then the integer operation would be 126/8 which would lose precision. Instead, the LHS is promoted and shifted left by 8 bits. Then, integer division occurs and the value is stored with (hopefully!) no further shifts.
For division, I have used the following approach.
* handle sign * extend n bits to 2n bits
* shift left by radix split plus one round bit
* divide 2n / n -> n bits
* handle round and sign So you're right this requires 64-bit extension for a 32-bit fixed-point
unless you tackle the problem of two-component division, which I have done using a simplified version of Knuth long division. At the moment, this is only in develop branch. The compiler switch is BOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATH.
This is core to the difference in approach between P0037 and P0106. I guarantee to use built-in integer math for any type specialized on built-in integers. I believe that types with arbitrary width can then be built upon this foundation using novel integer types. Here is an example using Boost.Multiprecision to express a Googol: http://johnmcfarlane.github.io/fixed_point/#boost fixed_point<> uses the same algorithm regardless of whether the `Rep` integer is an uint8_t or a 400-bit custom type.
I also had some problems compiling
on VC12 (but you don't target that
compiler anyway). So that's no big deal.
You will need a C++11-compliant compiler as sg14::fixed_point<> creates literal types. Lack of support for features like constexpr constructors is the main obstacle to compiling under VC++ 2013 and earlier. I actually agree with that approach. Either it uses C++11 or
it does not. I don't see the need to cater to a specific older compiler for new library work.
It's a pragmatic choice. Three reasons are: * C++11 has everything I need to implement (with difficulty) a literal type. In particular, I can write most of my unit tests using `static_assert` which is the best thing ever! * Once you start returning novel specializations from your arithmetic operators, `auto` type deduction is essential to usability. * Many of my target users in SG14 are stuck with compilers which are behind the curve.
In your work you are using wrapped versions of elementary transcendental functions designed for built-in float. You might appreciate our hand-crafted functions designed to be highly efficient in several digit ranges.
Yes! I would be very interested in seeing if I could adapt those function. We worked hard on these. And there are many good
algorithms available in boost/fixed_point/fixed_point_negatable_cmath.hpp
Having spent a non-trivial amount of time writing the simplest sqrt I
could find, I appreciate the effort this must have involved.
Mine are placeholders and I've deliberately postponed the non-trivial task
of adding cmath equivalents. It's come up - maybe a couple of times - whether these functions are desired and the response has been to just keep the proposal narrow so they are not included.
There are interesting questions regarding how to implement some functions. For example, you surely don't always want the same inputs and outputs from functions involving angles. And hopefully these functions can be constexpr - unlike existing functions. I agree. Also, how have you approached the trade-off between speed and accuracy? I went for a very simple sqrt function which is adequate if the value is calculated at compile time but is likely not desirable at run-time. This isn't a problem that floating-point variants face.
The elementary transcendental functions use many techniques
including polynomial approximation, Pade approximation, Taylor series,
Newton iteration. For low digit counts, mostly polynomial approximation. We express the coefficients directly as integral values of the fixed_point representation and avoid as much as possible full division and multiply, favoring integer div and mul. These functions are quite efficient. We have not constexpr-ed them. But it looks like there is potential for that.
Writing constexpr functions in C++11 can be a big challenge.
I have also benched our fixed_point on bare-metal embedded systems both 8-bit and 32-bit with very satisfying efficiency results. This is a key feature for our embedded users that might also be interesting for SG14.
My current aim is to match integer performance for common arithmetic operations when using built-ins. This leads to some situations where overflow is a big problem - but no worse than dealing with raw integers. I'm curious how you deal with multiplying two int-sized values together without resorting to wider, slower types.I was under the impression that P0106 types always widen to fit their values. We have resorted to wider integer for internal mul and div or used higher level algorithms when the compiler switch BOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATH is activated as mentioned above (develop branch only). In our approach, full multiplication requires:
* sign conversion
* left shift for round bit
* multiply n*n --> 2n bits
* right shift and round * sign conversion
On a 32-bit system, a full 32*32 -> 64 mul is required. This full multiplication approach can not achieve your desired efficiency goal on 8-bit and 32-bitCPUs. Division uses similar approach.
Multiplication and division with plain int or unsigned can achieve the efficiency goal --- if it were not for handling rounding and overflow.
In my current branch, I'm actually trying to get even closer to integer-level efficiency. No longer does 32-bit multiplication result in 64-bit results on systems with 32-bit integer. This means that overflow on 32-bit arithmetic operations is even more common. The solution is explicit casting to 64-bit or use of an integer type which auto-widens: http://johnmcfarlane.github.io/fixed_point/#elastic
This is the toughest design issue I face - especially when combined with division.
Thank you and best regards, Chris And thank you. Keep up the good work! John Thanks again and best regards, Chris
Cheers,
John