Re: [boost] [fixed_point] First presentation from GSoC 2015 and more

Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 2016-10-13 16:41:27

>>> I will notify SG14 in case they missed your work too.

>> Thanks for the information.
>> We became aware of your work unfortunately very late inthe project. Much
>> of our fixed_point work stems from myearly prototyping dating from 2011 -
>> 2013.
>> I see a lot of similarities in the two bodies of work.Maybe we could
>> identify the strengths of each work.I don't know if it makes sense to
>> combine them,but maybe share some concepts or interface ideaswould make
>> sense.

> 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 proposalto a realistic level in the SGs so that we can end up with anythingat all within a reasonable time scale. We could consider back portingsome (but probably not all) of SG14's specified interface to Boostif that helps move anything along.

I was also wondering about decimal radix, but I don't know if itmight simply be better to identify those 80% of the most popularuse cases and simply specify these. At least it would get the librarymoving forward and people could use fixed-point in C++. This isbasically what we tried to do with the GSoC project.

>> 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 isa likely possibility. But division operator in the masterbranch seems like it does not pad before divide.This might give the wrong result.
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 rightthis requires 64-bit extension for a 32-bit fixed-pointunless you tackle the problem of two-componentdivision, which I have done using a simplifiedversion of Knuth long division. At the moment,this is only in develop branch. The compiler switchis BOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATH.

>> I also had some problems compilingon 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 orit does not. I don't see the need to cater to a specific oldercompiler for new library work.
>> In your work you are using wrapped versions of elementary transcendental
>> functions designed for built-in float.You might appreciate our hand-crafted
>> functionsdesigned 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 goodalgorithms available inboost/fixed_point/fixed_point_negatable_cmath.hpp

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

>> I have also benched our fixed_point on bare-metalembedded systems both
>> 8-bit and 32-bit with verysatisfying efficiency results. This is a key
>> featurefor our embedded users that might also be interestingfor 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 divor used higher level algorithms when the compiler switchBOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATHis 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 yourdesired efficiency goal on 8-bit and 32-bitCPUs. Division uses similar approach.

Multiplication and division with plain int or unsignedcan achieve the efficiency goal --- if it were not forhandling rounding and overflow.

>> Thank you and best regards, Chris
> And thank you. Keep up the good work!
> John
Thanks again and best regards, Chris

 

    On Thursday, October 13, 2016 4:36 PM, John McFarlane <john_at_[hidden]> wrote:
 

 Hi Christopher. I'm actually the main culprit behind P0037. :)

Date: Wed, 12 Oct 2016 18:32:26 +0000 (UTC)
> From: Christopher Kormanyos <e_float_at_[hidden]>
> To: "boost_at_[hidden]" <boost_at_[hidden]>
> Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015
>Â  Â  Â  Â  and more
> Message-ID: <1026507022.4306136.1476297146580_at_[hidden]>
> Content-Type: text/plain; charset=UTF-8
>
> > I'm a bit surprised I didn't see this work before.
> > Are you aware that SG14, the gamedev, real-time simulations, embedded
> > software and financing study group for the standard
> > is working on fixed point real proposal too?
> > Here is a version of the proposal:>http://johnmcfarlane
> .github.io/fixed_point/papers/p0037r2.html and>http://johnmcfarlane.githu
> b.io/fixed_point/papers/p0381r0.html
> > I will notify SG14 in case they missed your work too.
> Thanks for the information.
> We became aware of your work unfortunately very late inthe project. Much
> of our fixed_point work stems from myearly prototyping dating from 2011 -
> 2013.
> I see a lot of similarities in the two bodies of work.Maybe we could
> identify the strengths of each work.I don't know if it makes sense to
> combine them,but maybe share some concepts or interface ideaswould make
> sense.
>

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.

>
> In your work I've been experiencing some trouble withthe 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 also had some problems compilingon 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.

> In your work you are using wrapped versions of elementarytranscendental
> functions designed for built-in float.You might appreciate our hand-crafted
> functionsdesigned to be highly efficient in several digit ranges.
>

Yes! I would be very interested in seeing if I could adapt those function.

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.

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.

> I have also benched our fixed_point on bare-metalembedded systems both
> 8-bit and 32-bit with verysatisfying efficiency results. This is a key
> featurefor our embedded users that might also be interestingfor 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.

>
> Thank you and best regards, Chris
>
> And thank you. Keep up the good work!
John

>
>Â  Â  On Tuesday, October 11, 2016 11:37 PM, Klaim - Jo?l Lamotte <
> mjklaim_at_[hidden]> wrote:
>
>
>Â  On 6 October 2016 at 12:07, Paul A. Bristow <pbristow_at_[hidden]>
> wrote:
>
> > > -----Original Message-----
> > > From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of
> > Christopher Kormanyos
> > > Sent: 05 October 2016 23:07
> > > To: boost_at_[hidden]
> > > Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015
> and
> > more
> > >
> > > >> A partial implementation of fixed-point in a Boost-like
> > > >> style based on proposal N3352 is now available.
> > >
> > > > ... But your links don't work,
> >
> > Indeed :-( (
> >
> > The correct link to the docs for some years used to be
> >
> > https://dl.dropboxusercontent.com/u/43940943/modular-boost/
> > libs/fixed_point/doc/html/index.html
> >
> > but sadly this no longer works for reasons that so far escape me (but I
> > suspect some change at Dropbox?).
> >
> > Meanwhile here is a PDF version to whet your appetite until I get a html
> > version publicly available.
> >
> > https://dl.dropboxusercontent.com/u/43940943/modular-boost/
> > libs/fixed_point/doc/fixed_point.pdf
> >
> > Boost.Fixed_point ?
> > ===============
> >
> > A partial implementation of fixed-point in a Boost-like style based on
> > proposal N3352 is now available.
> >
> > This work is the result of developments from 2013-2016, including efforts
> > from GSoC 2015.
> >
> > The source code is available at: https://github.com/
> > BoostGSoC15/fixed_point
> >
> > (The master branch will be stable for a while but the develop branch may
> > be updated in the light of your feedback).
> >
> > Preliminary docs are available at:
> >
> > https://dl.dropboxusercontent.com/u/43940943/modular-boost/
> > libs/fixed_point/index.html
> >
> > We are potentially interested in submitting this work for inclusion in
> > Boost.
> >
> > We are now requesting comments and suggestions for improvements,
> > corrections and any
> > further test results if these become available.
> >
> > Some key library features include:
> >
> > * proper C++ header-only implementation
> > * full numeric_limits and <cmath> functions
> > * flexible template choice of split between resolution and range
> > * automatic selection of underlying integral representation
> > * portability and high efficiency for bare metal microcontrollers
> > * interoperation with Boost.Math
> > * seamless extension to high-precision using Boost.Multiprecision
> > * extensive test suite
> >
> > Thank you for your consideration.
> > Best regards,
> >
> > Christopher Kormanyos
> >
> > And apologies from Paul.
> >
>
>
> Hi,
>
> I'm a bit surprised I didn't see this work before.
> Are you aware that SG14, the gamedev, real-time simulations, embedded
> software and financing study group for the standard
> is working on fixed point real proposal too?
> Here is a version of the proposal:
> http://johnmcfarlane.github.io/fixed_point/papers/p0037r2.html and
> http://johnmcfarlane.github.io/fixed_point/papers/p0381r0.html
> I will notify SG14 in case they missed your work too.
>
> Jo?l Lamotte
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman
> /listinfo.cgi/boost
>
>
>
>

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