- Boost - lists.boost.org

Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
by John McFarlane 19 Oct '16

19 Oct '16

> > Date: Thu, 13 Oct 2016 20:41:27 +0000 (UTC) > From: Christopher Kormanyos <e_float(a)yahoo.com> > > > 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-b… > > >> 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/91c3f2e272f9fd5e33ffb4dc2… It's on display in this test: https://github.com/johnmcfarlane/fixed_point/blob/1cc7ceaaff5422667ae962995… 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

4 7

[serialization]
by alainm 19 Oct '16

19 Oct '16

Hi, I have a few blocking compilation/link problems on the develop branch for which to fixes are pending (46 (3 lines) & 45(1 line)). 45 is a bug in the code I thin, 46 probably works just fine on most platform, but not on mine (recent Intel compiler on CentOS 6.5, which mean advanced features, but old headers). Boths are breaking are breaking some tests on Boost.MPI. Could someone have a look at it ? Regards Alain

1 0

[Serialization] check failed ???
by alainm 17 Oct '16

17 Oct '16

Hi, If I got on: https://github.com/boostorg/serialization/pull/46 I see a message "All checks have failed". If I follow the link "details" I see stuff regarding rake (?) and unfound "rakefiles", What is this all about ? Regards -- Alain Miniussi Pole Génie Logiciel Scientifique Observatoire de la Côte d'Azur Blv de l'Observatoire, Nice

1 0

Read only attributes in C++ (class proposal)
by Daniel Illescas Romero 17 Oct '16

17 Oct '16

Hello, I wanted to make some read only attributes on C++ so I made a class, named ReadOnly. This class will contain an internal private value, only “friend” classes could change this internally. Description: · A read only object will contains an internal value that can’t be changed outside the class. For example: ReadOnly<string> name = “Daniel”; To access its value: object.name, if you try: object.name = “other”, it won’t change it’s value because it’s a read only variable; you can change it’s value only inside the class the object is declared, you could change it like: name.value = “whatever”; · To set a value (outside the class) to a read only attribute you MUST specify a setter function (which can be static and contained inside the class), like: ReadOnly<int> age {ReadOnly::setAge, 1}; (optionally you can also set a default value to the attribute). Example of setter function: static bool setAge(const int& value) { return (value > 0 && value <= 150); } So if you you have an object and you want to change its value like this: object.age = 100; it will change its internal value only if the setter function (which is called internally) returns true. · The idea of doing all of this instead private variables and getters & setters is because this approach is closer to OOP than what is normally used; I mean if you have an object and you want to get an attribute value, what you need to do in most cases is something like: object.getAttribute(), you are calling a function to just take a look at an attribute, that shouldn’t make sense in OOP, that’s why I made all of this. It’s also similar to how you manage getters and setters in Swift, because they are embedded in the attribute and you don’t need to make other functions. :) I uploaded the project to github so everyone can take a look: https://github.com/illescasDaniel/ReadOnly <https://github.com/illescasDaniel/ReadOnly> — I wanted to know your opinion about the idea of the class and also about the implementation, I’d love to upload it to boost libraries but I want to know people opinion and make the class better. Thank you!

2 1

How can I detect if a template static member function exists?
by Vinnie Falco 16 Oct '16

16 Oct '16

I'd like to write a trait: template<class T> struct has_content_length : std::integral_constant<bool, ...>{}; which detects whether or not a template static member function is present in T. Here's a typical T: struct X { template<bool isRequest, class Body, class Headers> static std::uint64_t content_length( message<isRequest, Body, Headers> const& m); }; How can I detect if X::content_length(m) is callable for any m of type message template?

2 1

Re: [boost] [config] Changes to reflect Visual C++ "15" preview 5
by Tom Kent 15 Oct '16

15 Oct '16

I've now added a runner to the test suite with msvc-15.0 (preview 5 installed), it should show up in a couple hours as "teeks99-09o-win2012R2-64on64" (the far right column). The run only took a few minutes instead of an hour or two, so I'm expecting it to look pretty broken. Just glancing at the logs it looks like the compiler isn't even being found. Does this require b2 updates? Tom

2 1

[algorithm] New search algorithms
by Зайцев Александр 14 Oct '16

14 Oct '16

Hello. Now in Boost. Algorithm there are 3 algorithms for searching: Knuth-Morris-Prata, Boyer-Moore, Boyer-Moore-Horspool. They are good algorithms, but there are other efficient algorithms like Turbo-Boyer-Moore, Quick Search, etc. You can find some more here: http://www-igm.univ-mlv.fr/~lecroq/string/index.html Now i am working on new search algorithms for Boost.Algorithm. Maybe are there anybody,who familiar with string search algorithms? -- Best regards, Alexander Zaitsev

1 0

[program_options] -d directory is falling into positional input-files 1_62_0
by Roger Martin 14 Oct '16

14 Oct '16

Hi, Pulled this from a larger application to isolate to the problem: -d ./tmp or -d "./tmp" doesn't go to directory string but is with the positionals: #include <stdlib.h> #include <iostream> #include <exception> #include <string> #include <cstring> #include <memory> #include <fstream> #include "boost/program_options.hpp" int main(int argc, char** argv) { try { boost::program_options::positional_options_description p; p.add("input-file", -1); std::string directory = "./"; boost::program_options::options_description visible("Allowed options"); visible.add_options() ("input-file", boost::program_options::value<std::vector<std::string>>(), "input files can be *.xml, *.pdb, *.mol2, *.mtz, *.cif, *.csv, and *.sdf. Csv and sdf formats are for NMR calculations. csv lists the atoms for which the shifts will be computed. 1st line containts the Header: \"Chain\",\"Residue ID\",\"Sequence\",\"Atom Name\",\"Unbound ppm\",\"Bound ppm\". Then atoms may be listed i.e \"A\",\"MET\",231,\"CE\",10.30,10.50. sdf file contains the ligands for a CSP calculation. ") ("directory,d", boost::program_options::value<std::string>(&directory)->implicit_value("./"), "Directory for publishing output.") ; boost::program_options::options_description all("Allowed options"); all.add(visible);//.add(hidden); boost::program_options::variables_map vm; boost::program_options::store(boost::program_options::command_line_parser(argc, argv).options(all).positional(p).run(), vm); boost::program_options::notify(vm); std::vector<std::string> fileList = vm["input-file"].as < std::vector < std::string >> (); for (unsigned int fileListIndex = 0; fileListIndex < fileList.size(); fileListIndex++) { std::cout<<" "<<fileList[fileListIndex]<<" "<<std::endl; } } catch (std::exception& e) { std::cout << e.what() << std::endl; } return 0; } Built with g++ 4.9.0 on Linux frodo.quantumbioinc.com 2.6.32-573.7.1.el6.centos.plus.x86_64 #1 SMP Wed Sep 23 03:02:55 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux g++ -fPIE -std=c++11 -I${BOOST_HOME}/include -Wl,--allow-multiple-definition -MT main.o -MMD -MP -O3 -c -o main.o main.cpp g++ -pie -Wl,--allow-multiple-definition -o main main.o -L${BOOST_HOME}/lib -lboost_program_options -lc -lm -lpthread -lz -lstdc++ -ldl -lrt And run as ./main 2-aminoethanol.pdb -d ./tmp which results in 2-aminoethanol.pdb ./tmp This code had been working with 1_57_0. Some change in the API I need to adjust for?

1 0

[algorithm] Longest palindromic substring in Boost.Algorithm
by Зайцев Александр 14 Oct '16

14 Oct '16

Hello I want to add to Boost.Algorithm algorithm for finding all palindromes in a sequence in O(N). https://en.wikipedia.org/wiki/Longest_palindromic_substring Is it useful algorithm for Boost? Have you any suggestions? -- Best regards, Alexander Zaitsev

3 2

Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
by John McFarlane 13 Oct '16

13 Oct '16

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(a)yahoo.com> > To: "boost(a)lists.boost.org" <boost(a)lists.boost.org> > Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015 > and more > Message-ID: <1026507022.4306136.1476297146580(a)mail.yahoo.com> > 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(a)gmail.com> wrote: > > > On 6 October 2016 at 12:07, Paul A. Bristow <pbristow(a)hetp.u-net.com> > wrote: > > > > -----Original Message----- > > > From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of > > Christopher Kormanyos > > > Sent: 05 October 2016 23:07 > > > To: boost(a)lists.boost.org > > > 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 > > > >

2 1