March 2011 - Boost - lists.boost.org

GSoC 2011
by mahbubul hasan 21 Apr '11

21 Apr '11

Hi, I am Mahbub. I am a CSE graduate. I just saw you had a proposal regarding queue and heap in GSoC 2010. In my undergraduate I did thesis on heaps. In that time I learned soft heap, it might be interesting to you. Here is the short description of soft heap<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&t…>.( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&t…) Soft heap is a heap like data structure but with some uncertainty. This data structure supports insert, delete, merge, findmin. It does every work in amortized constant time except insert operation which takes O( log 1/e ) where 0<e=<.5. Here e is error rate. The data structure will never contain more than en corrupted elements. There are two versions of soft heap. 1. By Binomial Tree 2. By forest of binary tree There is one more thing that might interesting to you. That is, in my undergraduate I improved the running time of heap sort by significant amount by applying pairing technique. The paper is submitted to International Journal of Computer Mathematics and it is under review now. It mainly improves Carlsson's variant of heapsort. It also improves the deletion method proposed by Gonnet and Munro (Heaps on Heaps). [The heap is inplace, that means no additional space is required] It also improves the Weak Heapsort. WeakHeapsort is a sorting method which requires O(n) additional bit to sort. However applying the pairing technique it can be reduced to O(n/2) additional bit. It is known that weakheap is the theoretically best known algorithm. [Best considering number of comparisons] So I am just curious if you are interested in these types of algorithms. I saw no possible proposal category where these fits in, but I thought you might be interested. Please let me know what do you think about this. Mahbub

2 6

doxygen limitations
by Vicente BOTET 17 Apr '11

17 Apr '11

Hi, I would like to comment some limitations I have found while trying to generate the reference manual from the code comments using doxygen. 1. C++0x explicit operators are not documented as explicit with a warning explicit operator underlying_type const&() const ^^^^ gives operator underlying_type const &() const; 2. ::type misplaced when inheriting from a metafunction template < typename Final, typename UT, typename MetaMixinSeq=boost::mpl::vector0<>, typename Base=base_opaque_type > class new_class : public linear_hierarchy::type { gives template, typename Base = base_opaque_type> class new_class : public linear_hierarchy::type< MetaMixinSeq, Final, Base > { // ^^^^ 3. The base type is missing if the class is not documented elsewhere. This applies to other classes defined in other libraries in Boost or the Stl, but also when we use parameterized inheritance. template struct inherited_from_underlying { template struct type : Base { // Parameterized inheritance }; }; gives template struct inherited_from_underlying { // member classes/structs/unions template struct type { }; }; 4. When the brief comment takes only one line the comment is included on the Synopsis and nothing on the description section //! the underlying type typedef UT underlying_type; generates typedef UT underlying_type; // the underlying type 5. The classes are sometimes implicitly prefixed with his namespace template < typename UT, typename Tag=void, typename Bool=bool, typename MetaMixinSeq=boost::mpl::vector0<>, typename Base=base_private_opaque_type > class private_opaque_type : public private_opaque_class< private_opaque_type, UT, Bool, MetaMixinSeq, Base> gives template, typename Base = base_private_opaque_type> class private_opaque_type : public boost::opaque::private_opaque_class< private_opaque_type< UT, Tag, Bool, MetaMixinSeq, Base >, UT, Bool, MetaMixinSeq, Base > Do you have a workaround to some of these issues? What about creating a specific doxygen limitations and workarounds wiki page? Is there a possibility that the generated html goes to a single reference html file? Best, Vicente P.S. You can see directly some real examples on the documentation of Boost.Opaque https://svn.boost.org/svn/boost/sandbox/opaque/libs/opaque/doc/html/index.h….

3 5

[GSOC]SIMD Library
by Faiçal Tchirou 12 Apr '11

12 Apr '11

Hi everyone, I recently ask documentation about the SIMD Library project here and I receive some guides and references links from Joel Falcou. Now I have some questions about the library itself. Is the goal of the project to build a library similar to libSIMDx86 but more focusing on the AltiVec instruction set ? Joel also advises me to take a look at Proto. I read that Proto is used to build DSEL. Will Proto be used to map high level classes and methods of the library to native SIMD instructions ? What about the library itself ? Which modules have to be developped ? Thanks.

8 37

Proposed Library Boost.Algorithm
by Marshall Clow 09 Apr '11

09 Apr '11

(Finally) I have uploaded to the vault <http://www.boostpro.com/vault/index.php?action=downloadfile&filename=Boost.…> a proposal for the Boost.Algorithm library. This has been a matter of interest and discussion for a long, long time. Some of this code was written during the "Library in a week" session at BoostCon 2008. More was written last summer after this year's BoostCon. There is no way that I can write and submit all the algorithms that people want/need/are interested in, so I am proposing to set up a system by which people can submit algorithms to be included in the library, and have them reviewed, much like how new libraries are reviewed for acceptance into boost. The difference will be that a new algorithm is generally a much smaller piece of code than a new library, so hopefully we can lower the barrier to getting small pieces of code into Boost. So, what's in this proposal? 1) Three search algorithms: Boyer-Moore, Boyer-Moore-Horspool and Knuth-Morris-Pratt. (search.hpp) 2) A set of predicates for determining if a sequence is ordered (by some criteria) (ordered.hpp) Originally written by Grant Erickson during the "Library in a week" session at Boostcon 2008, and reworked somewhat by myself. 3) A set of predicates for determining other properties of a sequence, based on some suggestions for C++0x. (all.hpp) 4) An algorithm for restricting a value between two endpoints (clamp.hpp) And, of course, test cases and documentation. -- Marshall

6 13

[GSoC] NLP Idea for GSoC 2011 project
by Sarma Tangirala 08 Apr '11

08 Apr '11

Hello list, I have worked with Boost on my projects but haven't really thought of using C++ as a language for NLP. The NLP that I have done is on Python and Java, for their built-in string methods. I don't know if this is inexperience or ignorance, but does C++ work well for NLP? I was thinking of having a GSoC project that is devoted to provide support for NLP. I mean like the kind that looks real easy on python. Also, I was looking at some C++ code using Boost/tokenizer.hpp that tokenized some text and it looked a bit scary. Any suggestions or advice? -- Regards, Sarma Tangirala, Junior - Class of 2012, Department of Information Science and Technology, College of Engineering Guindy - Anna University

4 9

[chrono] Interoperability with ICL and common concepts
by Joachim Faulhaber 06 Apr '11

06 Apr '11

Hi Vicente and Boost Chronoists, thank you for implementing Boost.Chrono! It's a very fine piece of software :) Currently I'm checking out the usage of chrono types with icl::intervals and interval containers. Obviously, using intervals of chrono::time_points or chrono::durations can be an important use case. Also ICL already works well with other date and time data types from boost data_time, so chrono's interoperability should be at least as easy. A problem here is, that Icl, while working instantly with built in data types (e.g. int, short, double or even int*), for other numeric types (e.g. boost::rational) or types "based on integral types" (e.g. data_time::ptime) I needed to provide adapter code. I think it'd be ideal, if boost libraries interoperated with each other just out of the box, of course. To achive this, we have to find a common understanding of those concepts, that make a seamless interoperability work. I think, this is important work to be done, because it widens the view from one's own library perspective to a broader horizon of generic interplay. The problem: There is a minimal set of requirements that Icl expects for the domain types of intervals and interval containers (1) A zero element, more precisely an identity element w.r.t. the type's composition operation, which usually is +. An assumption that works well for all built in types and many STL-types is, that we get this element by the default constructor T(). (2) A strict weak ordering < (3) For all discrete types and for continuous numeric types: Operators ++, -- (Only pre-variants needed e.g. ++x) (3.1) For discrete types ++/-- increments/decrements by a *least step* (3.2) For continuous numeric types ++/-- increments/decrements by a *unit step*. Most of the functionality of Icl works if requirements (1) through (3) are met. In addition, there are some functions that require a distance type, but only for more specific types, namely for numeric types that use varying interpretations of the origin (zero), like epoch based date and time and pointer-addresses. BTW, do we already have a name for this type of concept? origin_based_equidistant_scalar origin_based_equidifferential_scalar because they are based to an arbitrary origin, but have comparable differences or distances. Or shorter equidistant_scalar equidifferential_scalar because if we emphasize, that by "comparable differences or distances", it is implied that the origin is choosable. May favorite is "equidistant_scalar". This concept reminds me of "Levels of measurement" http://en.wikipedia.org/wiki/Level_of_measurement (4) For such equidistant scalar types D the ICL assumes, that the type of the difference values of D is D::difference_type. To summarize, for a domain type Dom, Icl expects Dom(), <, ++, -- and if dom is a equidistant scalar type we expect an associated type Dom::difference_type to be defined. Now boost::chrono::duration (D1*) Has a default ctor that leaves the type undefined. (D2) Has <, Ok. (D3) Has ++, --, Ok. boost::chrono::time_point (T1) Has a default ctor that implements the semantics assumed by the ICL, Ok. (T2) Has <, Ok. (T3*) Does not have ++, --. (T4*) Does not have difference_type So I end up with 3 of my requirements not met (D1, T3, T4) D1: Default ctor for chrono::duration leaves objects undefined. I assume this is due to efficiency considerations, nevertheless unfavorable from the view point of my library. For all built in types and most of the STL there has been something like an intuitive maybe unconscious may be conscious agreement to assign the identity element w.r.t. the fundamental composing operation of the constructed object's type as the semantics of the default ctor. From an algebraic, generic and interoprability point of view (and IMHO) this is the best choice. This choice has not been taken for chrono::durations, which is a little inconsistent also, because interestingly for its chrono::time_point type the semantic is just the desired one. The possibility of default ctor customization is no remedy, because ICL should ideally be completely "chrono agnostic" and still interoperable. For the same reason duration::zero() is not an option. T3: chrono::time_point does not implement ++ and --. I assume this is because of the specific maths that is designed for chrono::time_points (P) and durations (D) where - : P x P -> D + : P x D -> P + : D x P -> P but + : P x P -> P //verboten But this should not be an argument against ++ and -- because the "least steppable unit" for integral rep types as well as the "unit" for floating point rep types, that is processed by ++ and -- is the same for time_points and durations. T4: Finally, difference_type as the associated type for time_point is not defined. IMO, it should be, because from a concept point of view, chrono::time_point falls in the same equidistant scalar concept that other types are in (e.g. T*, random_access_iterator<T>) and those associate a difference_type. These are the main problems of Icl/Chrono interoperability. There are a few minor ones as well. Let's discuss these first. I hope we can arrive at a solution, where Icl can be chrono agnostic and vica versa and still everything works well together. Based on that, we could fix similar issues for other libs like data_time. Cheers, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de

5 38

Why Boost.Build?
by Gregory Crosswhite 05 Apr '11

05 Apr '11

Hey everyone, Is there a reason why Boost uses Boost.Jam/Boost.Build for reasons other than tradition? Does it have advantages over other build systems, in particular CMake (which I consider to be its main competitor)? Are there many people/projects who use Boost.Jam/Boost.Build outside of Boost? These questions are asked purely out of curiosity due to my ignorance of Boost.Jam/Boost.Build, not because I have an axe to grind. Cheers, Greg

23 43

Re: [boost] GSoC Proposal Preparation For Encoding Awared String
by Artyom 05 Apr '11

05 Apr '11

> From: Soares Chen <crf(a)hypershell.org> > > Hi all, > > [snip] > > I think there are several options that I can choose for my project: > 1. To use Chad Nelson's code as base, try to incorporate other ideas > proposed in the mailing list, integrate with Boost.Locale, and make it > Boost quality to submit for review. If this option is chosen, I wish > that Chad Nelson can be my mentor. > 2. To start a new code base, gather and compile ideas suggested in > mailing list, final design decisions made by me and my mentor but not > the community (to keep the project going on fast), make it Boost > quality and submit for review. > 3. To start the boost::string project, where another better string is > reinvented and fix all the weaknesses of std::string. > 4. Adopt different proposal, and improve on existing project such as > Boost.Unicode [2] or Boost.Locale [3] such that it really solves the > encoding awareness problem. > 5. Any other suggestion? Hello, I want you to address several points: It would be very hard to get the consensus about the way to solve the problem. Probably the best and the most wishful thinking solution is to assume that all strings are UTF-8 based, however it is not the reality. The problem is actually not the string but rather the way you code. Even if you create a perfect UTF-8 string and then call fopen(your_perfect_string.c_str(),"r") Under windows... And it would not work <sigh... damn Windows> As you can see from multiple discussions, there are many contradicting requirements about how should string look like and what should it bring with. If you want to provide better Unicode awareness to Boost you don't need new cool utf-XYZ string, you need a policy. I think boost::filesystem v3 is a big step forward, it allows you to use UTF-8 strings on Windows which I think is a really good beginning. This is my opinion. Boost.Locale and several other my projects (CppCMS, CppDB) live happily with std::string. The problem is that in vast majority of cases you don't need encoding aware string, as so many operations you usually do on strings are encoding agnostic. But this is other story. Bottom line, if you want to improve Unicode awareness of Boost I think you need to adopt Boost.Filesystem v3 like policy all over the code base of Boost. 1. Use Wide API as native one in Boost everywhere under Windows 2. Use char * API as native one in Boost everywhere under non-Windows platforms 3. Use std::codecvt to handle this (after many tricks... ) The Unicode String/Encoding Aware String is the last thing to do not the first thing. Why? 1. Because you will never get the consensus about what is the "right-thing" to do (wide, narrow, utf-8, utf-16) etc. Project that are handled and directed by a single source or management like Qt, GTK(mm), Java, C#, Python or others may decide what is the right thing. This will never happen in Boost as it is too pluralistic even in cases where it does not always make sense, just because the way libraries are developed, reviewed and got in - based on public reviews that eventually encourages diversity. 2. Because you would not likely to be able to enforce users to actually use your string. As boost is more about collaboration then enforcement of specific style. 3. Even heavy discussions there hadn't got to any conclusion. So what would happen and final review of your library? My $0.02 Artyom

7 11

[release][1.47] Release branch open + schedule
by Daniel James 05 Apr '11

05 Apr '11

Hello everyone, It's been over a week since the release, so it's time to open the release branch. Since we're running late, and we haven't discussed the changes to the schedule, and I think it helps people to pace their development, we should probably decide on a schedule for this release pretty quickly, and then discuss the schedule for future releases later. We discussed having longer betas, 4 weeks was suggested. If we do that this time, it'll leave a very small window for merging to release, so I think 3 weeks might be better. Something like: 4th April: Release branch closed for beta (bug fixes only). 11th April: Beta target date. 2nd May: Release target date. Note: That's just a proposal, not the actual schedule. It isn't up to me. That's still a tight schedule, maybe a shorter beta or a delayed release would be better. Any thoughts? Daniel

4 7

[lexical cast] Performance improvements
by Antony Polukhin 05 Apr '11

05 Apr '11

Working with Boost Lexical Cast library found that some casts are working really slow. For example, cast from short to int is done via cast from short to char[], and cast from char[] to int. Cast from char* to string is done via string() constructor call and string`s append function call (instead of string constructor call with char array as a parameter). So I wrote patch to Boost Lexical Cast library, that returns Target directly constructed from Source in cases, when: 1) Source and Target are arithmetics (and not char or wchar_t), and all values of Source are in range of Target 2) Source and Target are both char or both wchar_t 3) Source is array of CharT and Target is std::basic_string<CharT, ...> 4) Source and Target are std::basic_string with same template parameters It gives performance boost more than 10 times in case 1) , about 7 times in case 2), and about 1.5 times in cases 3) and 4). Existing tests for Boost Lexical Cast library cover considered cases. Patch was successfully tested on Intel 11.1.072, g++-4.4.5, VC++9 compilers. P.S.: I`m a newbie here, so where shall I send this patch? Shall I test it on other compilers?

5 5

Re: [boost] [lexical-cast] version of lexical_cast in 1.46.1 is quite older than in trunk
by Antony Polukhin 04 Apr '11

04 Apr '11

> "SergV"<serge-voropaev(a)yandex.ru> wrote in message > news:loom.20110329T052451-354@post.gmane.org... > We discovered lexical_cast from 1.43 and 1.46.1 versions do not work in > our > program. But version of lexical_cast from trunk work very well. Version > information: > 1.46.1 - rev. 56161 13.09.2009 > trunk - rev.65279 5.09.2010 > > 1) Is there any reason that release does not include last version > lexical_cast > from trunk? > 2) May be there are a lot of such forgotten files in trunk? There is also some mess with tickets for lexical_cast : some tickets are in bug database for months (and even years). > On Wed, 2011-03-30 at 18:16 +0300, Matthew Chambers wrote: >> Does that mean lexical_cast is orphaned? I'd like to see lexical_cast have optimized conversions for >> string->number and number->string (template specializations using strtol/strtod; or optionally using >> the spirit-based construe_cast). Being able to pass ios flags to control the format (i.e. boolalpha) >> would be nice too [...] >> Which reminds me - lexical_cast error messages are not very >> informative[...] > >Agreed. This should be added as well[...] > >-Matt I can take care about some of this issues, but if lexical_cast is orphaned and not maintained any more it`ll be just wasting time. - Antony

4 3

Data / String Ref library
by Olaf van der Spek 02 Apr '11

02 Apr '11

Hi, A lot of functions take a const void*, size_t pair as two parameters. This is then cast to a const unsigned char* for further processing. Two parameters means you can't easily pass the result of an expression or function call. One parameter would be handier. const std::string& is also used frequently. However, this forces the caller to use (or construct) std::string, which is undesirable and unnecessary. A solution seems simple: data_ref and string_ref, which represent a pointer pair (void/unsigned char and char respectively). string_ref can replace const std::string&, data_ref can replace const void*, size_t. I think this would be a nice addition to Boost. Is there any interest in a library that solves this problem? -- Olaf

4 11

[gsoc] Interest in BGL v2?
by Michael Lopez 01 Apr '11

01 Apr '11

Hello all, My name is Michael and, if there is enough interest from the mailing list, I will be submitting an application for GSoC 2011 to work on the BGL v2. I have been working on a project called Origin ( http://code.google.com/p/origin/) when time permits, that houses the code that I intend to integrate into boost. The project was started by Andrew Sutton and I have taken an active role in its creation. The new library focuses on ease of use, replacement of property maps for labels, data structures with more concise and clear semantics, a new graph concept hierarchy, implementing graph algorithms to align with STL abstractions, and, finally, integrate C++0x into the BGL. I have already worked on the existing BGL back in 2009 for GSoC. While working on the BGL, I started seeing opportunities to bring the BGL more in-line with modern techniques and practices. I found that the library, though robust and quite mature, was lacking in some areas. The most unavoidable being C++0x support. The other design concern was that some of the data structures felt more like meta-programs. This is no good since a meta-program generates types that may model one of many concepts. Another feature that has been on BGL's want list is the implementation of algorithm objects. Some of the algorithm objects are already present in Origin. I realize that this is not a 3 month project. I fully understand that. However, I plan to continue maintaining this library in Origin, as I have been, until it is mature enough for a release and integration into other libraries. Hopefully there is enough interest to get this off of the ground. Please respond with your interests, questions and/or doubts. Michael Lopez

7 29

[lexical-cast] version of lexical_cast in 1.46.1 is quite older than in trunk
by SergV 01 Apr '11

01 Apr '11

We discovered lexical_cast from 1.43 and 1.46.1 versions do not work in our program. But version of lexical_cast from trunk work very well. Version information: 1.46.1 - rev. 56161 13.09.2009 trunk - rev.65279 5.09.2010 1) Is there any reason that release does not include last version lexical_cast from trunk? 2) May be there are a lot of such forgotten files in trunk? Sergey Voropaev

6 7

Re: [boost] [submission] STL-compliant containers with copy-on-write
by Alexandr Sterligov 01 Apr '11

01 Apr '11

I'm working with embedded software and we have to use COW containers pretty often. I haven't found any COW container implementation which may replace STL containers and had to implemented it. It is not possible to make STL containers with COW keeping all semantics of the STL containers. For example, almost any member-function may throw, because copy ctor may throw. It is not always safe to replace std::vector with mine cow_vector, but in most cases it is safe. For example, it is not safe if you have saved constant pointer or constant reference from constant cow_vector. But with std::vector saving addresses is not a good idea as well, because resize, push_back and others may cause address change. In my implementation iterators are safe, for example: cow_vector<int> a; a.push_back( 1 ); cow_vector<int> b; b.push_back( 2 ); cow_vector<int>::const_iterator itA = a.begin(); assert( *itA == 1 ); cow_vector<int>::const_iterator itB = b.begin(); assert( *itB == 2 ); b = a; assert( itA == a.begin() ); assert( itB == b.begin() ); assert( *itA == 1 ); assert( *itB == 1 ); a[0] = 3; // or *a.begin() = 3 assert( itA == a.begin() ); assert( itB == b.begin() ); assert( *itA == 3 ); assert( *itB == 1 ); You example: int* p = &v[1]; // copying is done here v[0] = 1; assert( p == &v[1] ); // still valid as copying was done before. But in following case it won't work now: void test( const cow_vector<int>& a ) { const int *a = &v[1]; v[0] = 1; assert( p != &v[1] ); // sorry, another pointer if internal buffer was shared. } Please note, that it's possible to do copying if any reference or pointer is taken from iterator or container itself, but my current implementation doesn't do it. That's easy to change. > IMO it isn't possible to really make that work anyway since STL > containers expose references to their elements *and* make guarantees > about iterator stability and element layout. For example, if v is a > vector and I do > > v[0] = 1; > > it's not allowed to change the address of v[1] > -- > Dave Abrahams > BoostPro Computing > http://www.boostpro.com ---- Best regards, Alexander Sterligov

6 11

GSOC2011 (Introduction)
by Harinderpal Singh 01 Apr '11

01 Apr '11

Hi My name is Harinderpal Singh. I am from Lovely Professional University, Punjab, India. I am a fourth year B.Tech student. I have worked on c++. I also have basic knowledge of Mysql. I have competed in various inter college level competitions. I work on linux(ubuntu) and also have knowledge of windows. I don't have any experience with open source previously.I am interested in Checks & Hashes module Regards Harinderpal Singh Website; http://www.iyouth.in Blog: http://codelinguist.wordpress.com/ <http://codelinguist.wordpress.com/> +91-9888573505

2 1

boost interprocess (>1.45) robust mutexes
by Rusk . 31 Mar '11

31 Mar '11

Hi, I have noticed that in version 1.45 Ion Gaztanaga has added detail/robust_emulation.hpp which contains code that seems to emulate pthread_mutexattr_setrobust_np(). I understand this may be needed for platforms that don't support robust mutexes. My version of linux does seem to support robust mutexes, however I could not find a way to compile or in any other way to use this flag on posix mutexes in boost 1.46.1. Article here ( http://stackoverflow.com/questions/1179685/how-do-i-take-ownership-of-an-ab…) indicates the way to do this. But now emulation for robust mutexes has been added I wonder if I am missing something. Thanks, ddrum

3 7

GSoC idea
by Brestin Seby 31 Mar '11

31 Mar '11

Hello, my name is Sebastian Brestin. I am a student from Romania and I am really looking forward to working for C++ Boost library. I have noticed that in the past years Boost has proposed many times on building a library for operations on Big Integers, yet I do not find any implementation in boost_1_46_1 . Also I have noticed that many students choose Java over C++ in algorithm contests, because Java has a built-in library that permits operations on Big Numbers. As I have seen that so far neither STL, nor Boost have implemented operations over Big Numbers, I suggest to implement those operations over Big Numbers: - addition, subtraction, multiplication, division, modulo, comparison, factorial, radical etc. - conversion from one base representation to another( for example from decimal to hexadecimal, or from decimal to binary, or even in other bases) - operations in modulo classes. - those operations will not be limited only to integer numbers but also extended to floating point numbers in simple precision and double precision as well( except modulo classes). I think that this library could help not just students, but it can be also used in finding large prime numbers for security keys, why not ( using the "sieve of eratostene" on those large numbers). Thank you for your time and I hope I will get some feed back over this idea.

2 1

Algebraic abstractions related to (big) integers in C++
by Thomas Klimpel 31 Mar '11

31 Mar '11

Dear (big) integer enthusiasts, The goal of this message is to reflect on the two's complement representation of negative integers, from a relatively abstract algebraic perspective. Some of the questions that arise in this context are whether the two's complement representation would be well suited for (i) a fixed width integer data type (ii) a fixed point number data type (iii) a variable width integer data type (iv) a floating point number data type Circumstantial evidence suggests that it's well suited for (i) and (ii), but not well suited for (iv). The following quote from Bill Gosper (1972) "By this strategy, consider the universe, or, more precisely, algebra [...] therefore algebra is run on a machine (the universe) which is twos-complement." (<http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154>) could be seen as evidence in favor of using two's complement representation for (iii). However, XInt and other bigint libraries took the opposite decision, so there is strong circumstantial evidence against using two's complement representation for (iii). Let me start with a disclaimer that I'm not an expert in algebra. The following thoughts emerged when I tried to understand the semi-direct product. I wanted to see how it works for a concrete "small" group. So I tried to write the Quaternion group (the one with the 8 elements 1, -1, i, -i, j, -j, k, -k) as a semi-direct product. This didn't work, because the Quaternion group is not a semi-direct product. But after some time I managed to "decompose" the Quaternion group into abelian groups in a different way. I subsequently learned that this sort of problem is called the group extension problem <http://en.wikipedia.org/wiki/Group_extension>. It's a solved problem, but I would have to learn some homological algebra to understand its solution. Let's look at the "ring of integers" (denoted by "Z") and the "ring of integers modulo m" (denoted by "Z_m"). We want to "approximate" the "ring of integers" by the "ring of integers modulo m". One of the advantages of this approach is that it's relatively easy to represent the "ring of integers modulo m" in a computer, especially for "m = 2^n" (more concretely "m = 2^32" for int32_t and "m = 2^64" for int64_t). There exists exactly one non-trivial ring homomorphism "p : Z -> Z_m" from the "ring of integers" into the "ring of integers modulo m". (The integer "1" is mapped to the corresponding "1", and the additive group of the "ring of integers modulo m" is generated by "1".) A good way to describe how we "approximate" "Z" by "Z_m" is to define a map "q : Z_m -> Z" such that "p(q(i)) = i for all i". Because the map "q" is not uniquely determined by the condition "p(q(i))=i", let's add the additional constraint "-m/2 <= q(i) < m/2". It's easily checked that this uniquely determines the map "q". This map "q" is not a ring homomorphism, but that's OK as there does not exists any non-trivial ring homomorphism from "Z_m" into "Z". Still we should try to measure the deviation of "q" from a ring homomorphism by taking a look at "S(a, b) := q(a) + q(b) - q(a + b)" and "P(a, b) := q(a) q(b) - q(a b)". It's easily checked that "p(S(a, b)) = 0" and "p(P(a, b)) = 0". This shows that "S(a, b)" and "P(a, b)" are multiples of "m". A quick estimation shows "-1 <= S(a, b)/m <= 1" and "-(m+1)/4 < P(a, b)/m <= (m+2)/4". This doesn't look too bad, but still bad enough to question whether the constraint "-m/2 <= q(i) < m/2" is really the way to go. Instead of the constraint "-m/2 <= q(i) < m/2", we could have also used the constraint "0 <= q(i) < m" or the constraint "-m/2 < q(i) <= m/2". One reason to prefer the constraint "-m/2 <= q(i) < m/2" over the constraint "-m/2 < q(i) <= m/2" is that we exactly get the two's complement representation of signed integers for "m = 2^n", which was the very reason that we investigated these algebraic relations in the first place. It's also more consistent with the "a <= x < b" representation of ranges so typical for C/C++. I want to give a third reason why the constraint "-m/2 <= q(i) < m/2" should be preferred over the constraint "-m/2 < q(i) <= m/2". Let's define a "round to nearest" division and the corresponding modulo operation for the "ring of integers" by "rdiv(a, b) := floor(1/2 + a/b)" and "rmod(a, b) := a - b rdiv(a, b)". It's easily checked that "-m/2 <= rmod(i, m) < m/2". It could be objected that implementing "round to nearest" by "i = floor(0.5 + x);" is only correct for non-negative values of "x". The correct implementation of "round to nearest" seems to be "i = x >= 0 ? floor(x + 0.5) : ceil(x - 0.5);". But I don't think that the more complicated definition of "round to nearest" is always "more" correct than the simpler one. At least when manipulating polygons, there can be situations where the simpler definition turns out to be the "more" correct one. But let's investigate to constraint "0 <= q(i) < m" now. A quick estimation shows "0 <= S(a, b)/m <= 1" and "0 <= P(a, b)/m < m-1". So "S(a, b)/m" could be stored in a single "carry bit" and "P(a, b)/m" can be stored as a value of "Z_m". It is therefore not uncommon to have access to "S(a, b)/m" in machine language via a "carry bit" and to "P(a, b)/m" by using a machine instruction that computes "a b" and "P(a, b)/m" at the same time and stores "a b" and "P(a, b)" in different registers. (My experiences with machine language are from the time before 1996, so pardon me if these statement should not be fully correct.) The statement about the carry bit is not fully correct, because the carry bit is normally not just a result of an addition in machine language, but is also taken into account during the addition. So if "c" is the carry bit before the addition, the addition will return the value "p(c) + a + b" in "Z_m" and the new carry bit "(c + q(a) + q(b) - q(p(c) + a + b))/m". It's probably even possible to write this "add_with_carry" operation as a function in C or as a template in C++. But I don't really believe that many compilers will notice the equivalence between a template like the following and the "add_with_carry" machine instruction. template <Uint> typename boost::enable_if<boost::is_unsigned<Uint>, bool>::type add_with_carry(Uint& a, const Uint& b, bool c) { a += (c != 0); a += b; return (c != 0) ? (a <= b) : (a < b); } And I'm pretty certain that there doesn't exist any compiler will notice the equivalence between a template like the following and the mentioned machine instruction for a multiplication returning the complete result. I'm not even certain myself that they are equivalent (but I could write a test to verify it for me, if I really wanted to be certain). template <Uint> typename boost::enable_if<boost::is_unsigned<Uint>, Uint>::type multiply_full_result(Uint& a, const Uint& b) { Uint upper_a = (a >> (sizeof(Unit)/2)); Uint upper_b = (b >> (sizeof(Unit)/2)); Uint lower_a = a & (Uint(-1) >> (sizeof(Unit)/2)); Uint lower_b = b & (Uint(-1) >> (sizeof(Unit)/2)); Uint upper = upper_a * upper_b; upper += ((upper_a*lower_b) >> (sizeof(Unit)/2)); upper += ((lower_a*upper_b) >> (sizeof(Unit)/2)); a *= b; return upper; } I'm starting to get problems with the length of this message now, because it is quite reasonable to expect that the number of people that will even try to read the message gets lower and lower as the message gets longer and longer. And this is already my third start from scratch trying to come up with something reasonable in size and readability. My first attempt directly started with p-adic numbers and p-adic integers, then tried to explain how the two's complement representation is related to 2-adic integers. It noted that it is indeed an approximation in the 2-adic metric, but this normally doesn't buy us anything, because the 2-adic metric is almost never the relevant metric for our problem domain at hand. This is also one of the reasons why the two's complement representation should be avoided for floating point numbers, because the relevant metric in this case is the normal metric of the real numbers. My second attempt tried to take the opposite approach, and started with the C++ statement "std::size_t n = std::max(1, c.size());", noting that it will provoke a compile error. After some discussion and additional examples like the expressions "c.size()/-2" and "-c.size()/2", it claimed that Haskell was able to solve these problems by not assigning any concrete type to "2" at all, but just the abstract "Num" typeclass. One part of the problems that are meant here is described in the following statement: "What I consider especially strange from an algebraic point of view, is to automatically promote a signed integer type to its corresponding unsigned integer type, when an arithmetic expression contains both signed and unsigned integer types. Shouldn't it be the other way round? Or wouldn't it be even better, if there would be no automatic conversion at all? At least from an algebraic point of view, any natural number is also an integer, not vice versa like in C." So let's try to come to some sort of conclusion now, even so not all semantical issues I wanted to discuss have been raised, and nearly no solutions for the raised issues have been presented. It looks to me now like it can be advantageous to implement operations for signed (variable or fixed width) integer data types in terms of operations for unsigned integer data types. This can be done independent of whether the two's complement representation is used or not. However, we should still be careful to provide the correct semantic for signed integer types, even if we implement them in terms of unsigned integer types. It is a questionable design when the TTMath bignum library lets it signed integer type derive public from its unsigned integer type ("template<uint value_size> class Int : public UInt<value_size> { ... };"), because the relationship between signed and unsigned integer types is not a "is a" relationship as required for public inheritance. (Think about it, a signed integer is really not an unsigned integer, even if the unsigned integer type would model the "ring of integers modulo m" instead of the "natural numbers".) Is is also questionable when a relatively new language like the D programming language cripples its "Usual Arithmetic Conversions" by stating "The signed type is converted to the unsigned type." as rule 4.4. Even so it is true that an integer can be converted to an "integer modulo m" (remember the ring homomorphism "p : Z -> Z_m"), are there really good reasons to apply such a conversion automatically? For the C/C++ language, the answer is definitively yes: "backward compatibility". But I don't think that this reason would have applied to D. And please pardon me if I imply press the send button now. Regards, Thomas

4 12

[context review] Review is finished
by Vicente BOTET 31 Mar '11

31 Mar '11

Hi all, As there were no request to extend the review, the review of Oliver Kowalke Context library is finished. I think that even if there were not too much review and discussions, there were enough material to make Boost.Context a library having the Boost level. I hope I could be able to give the review result soon. I would like to thank Oliver and of course all the reviewers for their participation I'm afraid there was some problems with User ML. If you think that you could made a review next weekend, please don't hesitate to send it to the Dev ML. Vicente, Review manager

1 0

gsoc project(checks)
by Александр 31 Mar '11

31 Mar '11

Hello, Paul. Here i send you test message. Also i send you two different messages, one with .zip file and one with .rar. Actually, here i want to say few things i thought about after i finished coding. I made my class working with uint8_t type - byte arrays. But then i thought it should be working the same way with any int type actually.. And even with any data if we think of it as a simple sequence of bytes. But here i came to the problem: 1. i can replace uint8_t by template class and then use cast in process() method to get data in byte representation: byte *bytes = reinterpet_cast<byte*>(&in_data) and then just deal with byte sequence. 2. or remove vector from member and treat any structure as sequence of bytes. But the thing is - we need checksum for data stored in structure of checksum for structure itself? Because if we take complex structure(something like map<pair<set<int>,pair<int,string> > >) what checksum are we calculating actually? Thank you! -- Alexandr mailto:daywalker@mail333.com

2 1

gsoc project(checks) plain
by Александр 31 Mar '11

31 Mar '11

In case there is a problem with sending zipped files i just list my code here(with no tests or docs,just hpp): #ifndef BOOST_CHECKSUM_HPP #define BOOST_CHECKSUM_HPP #include <boost/cstdint.hpp> #include <vector> namespace boost { typedef boost::uint8_t byte; class checksum { public: checksum(); checksum(const checksum&); checksum(const std::vector<byte>&); void process(); void put_data(const std::vector<byte>&); byte get_sum() const; bool proceeded() const; private: byte sum; std::vector<byte> in_data; bool done; };//boost::checksum inline checksum::checksum() : sum(0), done(false) { } inline checksum::checksum(const boost::checksum &cs) { sum=cs.sum; done=cs.done; in_data=cs.in_data; } inline checksum::checksum(const std::vector<byte> &_in_data) : sum(0), done(false), in_data(_in_data) { } inline void checksum::process() { if (!done) { uint8_t temp_sum=0; for (std::vector<byte>::const_iterator it=in_data.begin();it<in_data.end();it++) temp_sum+=*it; sum=temp_sum; done=true; } } inline void checksum::put_data(const std::vector<byte> &_in_data) { if (in_data!=_in_data) { in_data=_in_data; done=false; } } inline byte checksum::get_sum() const { return sum; } inline bool checksum::proceeded() const { return done; } } //namespace boost #endif // BOOST_CHECKSUM_HPP -- Alexandr mailto:daywalker@mail333.com

1 0

gsoc project
by Александр 31 Mar '11

31 Mar '11

Hello! I am a student from Moscow Institute of Physics and Technology and i wish to participate in Google Summer Of Code project. Boost C++ Libraries development seems really interesting for me, so that's why i decided to ask some questions about details. In the list of ideas there is "Checks & Hashes" project - i had experience in this area, writing a small lib for my university project, but it was mostly like a simple wrapper for RFC implementations of hashing algorithms like MD5 or SHA-1. As i understood this library is got to be something like a collection of different algorithms and it is got to be scalable, right? What are the requirements for me to be able to work on this project? Do i need to write some code for a start? -- Best wishes, Alexandr mailto:daywalker@mail333.com

5 9

[math] Warnings in version 1.46.1
by Richard Hadsell 31 Mar '11

31 Mar '11

I am trying to build the Boost 1.46.1 libraries on a Fedora 7 Linux system with the default g++ 4.1.2. The warnings from the math library produce zillions of lines of output. Each warning has a long description of the instantiation and then concludes with a couple of lines like this: ./boost/math/special_functions/binomial.hpp:65: instantiated from here ./boost/mpl/assert.hpp:79: warning: lowering visibility of 'int mpl_::assertion_failed(typename mpl_::assert<C>::type) [with bool C = false]' to match its type Is this problem known? I hope it doesn't continue in future releases. -- Dick Hadsell 203-992-6320 Fax: 203-992-6001 Reply-to: hadsell(a)blueskystudios.com Blue Sky Studios http://www.blueskystudios.com 1 American Lane, Greenwich, CT 06831-2560

3 13

[submission] STL-compliant containers with copy-on-write
by Alexandr Sterligov 31 Mar '11

31 Mar '11

Is there any interest in a library of STL-compliant containers (vector, deque, map, set, list) with copy-on-write? -- Best regards, Alexander Sterligov

3 2