April 2013 - Boost - lists.boost.org

[Boost][GSOC] proposal for Trie
by Hardy Huang 28 Apr '13

28 Apr '13

Hi, this is my proposal for GSOC 2013, please read it and give me some useful information on it, thanks == Personal Details == * Name: Zhe(Hardy) Huang * College/University: Peking University * Course/Major: Computer Science * Degree Program: M.Sc. * Email: hzithlony(a)gmail.com * Homepage: not yet * Availability: * How much time do you plan to spend on your GSoC? I will spend the most part time of the semester(till late June), and then the whole summer on my GSoC project. * What are your intended start and end dates? I basically will obey the rules of GSoC, and I will also listen to mentor’s advice on it. * What other factors affect your availability (exams, courses, moving, work, etc.)? I am having my courses now, and I will have my final exams in June. Since I am not having many courses, I have enough time to do something for the project before exams. And in summer I could almost work full time on it. == Background Information == Please summarize your educational background (degrees earned, courses taken, etc.). I majored in Computer Science in Zhongshan University from 2008 to 2012, by which I earned my bachelor’s degree. During the four years, I learned many basic courses on Computer Science, like algebra, logic, data structure, algorithms, operating system, Compilers, databases, networks. >From 2012 till now, I am studying Computer Science in Peking University pursuing my master’s degree. My research field is information retrieval. Please summarize your programming background (OSS projects, internships, jobs, etc.). GSoC is the first time that I get involved with a real and large OSS project. Besides, I’ve developed many things in C and C++. I developed a simplified B-tree data structure in C during my intership for a small company. Later a system in C to extract and evaluate the content of webpages for my research, and I am still on it. An implementation of a search system in C++. A webpage template system in C for my lab to generating webpages in order to do some research on them. Please tell us a little about your programming interests. I like to write codes for the basic and general use. I am pursuing well-framework of design and code, and high reusability when I think of develop the project. Please tell us why you are interested in contributing to the Boost C++ Libraries. Boost is widely used by programmers and famous for its powerful and efficient. It is an honor to contribute to such a lib, and have my codes used and reviewed by so many programmers. I like the reusability of well-designed lib, so it also will be a good chance for me to improve my skill of design and programming. And a good chance to communicate with good guys as well. I want to be a good programmer with many good programmers as my friends. What is your interest in the project you are proposing? Because I have participated in many competitions of algorithm, I have a good knowledge of algorithms and data structures. I have also implement many, but for the sake of winning, the codes usually can not be well-reused. Meanwhile the STL in C++, which I’ve used many times during the competitions, such as set, map, priority_queue, sort are good examples of well-reused algorithms and data structures. So I’ve been expecting to develop some general libraries of algorithms and data structures. Boost is a well-formed organization, and Boost lib is a widely-used lib, so I also want to learn some skills to develop a good lib from developing the project with mentors in Boost. Have you done any previous work in this area before or on similar projects? I am good at data structure and algorithm, and I wrote codes of various algorithms and data structures for many times. I am very familiar with the Trie data structure, and as I list above, I've develop a simplified general B-tree data structure in C, which is a good experience when I develop Trie for Boost. What are your plans beyond this Summer of Code time frame for your proposed work?. I will dedicate my summer to my work. And taking the experience as a good beginning, I will be feeling happy to contribute more to Boost, and other OSS projects. Please rate, from 0 to 5 (0 being no experience, 5 being expert), your knowledge of the following languages, technologies, or tools: - C++ 3 - C++ Standard Library 3 - Boost C++ Libraries 2 - Subversion 3 What software development environments are you most familiar with (Visual Studio, Eclipse, KDevelop, etc.)? I use Visual Studio in my lab, and vim + gcc for myself. What software documentation tool are you most familiar with (Doxygen, !DocBook, Quickbook, etc.)? I’ve used Doxygen before, it is simple and efficient. == Project Proposal == Please provide a description of your proposed work. Trie(Radix Tree) is an efficient in memory data structure to deal with string storing and searching. It can be used in many applications, and in comparison to hashtables, it has better expandability and stability. It will be an data structure of great importance and wide usage. == Proposed Milestones and Schedule == Please provide estimated milestones and schedule for completing the proposed work. Before May 27: To familiarize with the Boost lib, with reading the codes and discussing about it in mailing list. To have a better knowledge of lib, with reading some books of STL and Boost, and comparing Boost with STL. To setup us a proper environment for development. Study deep into Trie, reading some others’ good implementations. May 27 – June 17: Keep in touch with the Boost organization and have good communications with my mentor. Get involved with the development of boost. Try some toys about Boost, and discuss them with mentor, in order to know better about mentor and how the development goes on. June 17 – July 15(Coding period begins): Discuss the detail of the design with mento, develop an alpha version of Trie, and have it tested in small scale. July 15 – July 29(To mid-term evaluation): Refine my alpha codes, analyze the performance, and try to improve it. Write an initial report of the project and document of Trie. July 29 – September 23: Refine my codes, and have some thorough tests on it, make it robust. Reorganize codes and improve documents.

5 27

[result_of] Allow result_of to work with C++11 lambdas
by Nathan Crookston 28 Apr '13

28 Apr '13

Hi all, Using C++11 lambda functions with several boost components. For example, the following code snippet will not work with VC10, nor with g++ up to 4.8: #include <boost/assign.hpp> #include <boost/range/adaptors.hpp> #include <boost/range/algorithm.hpp> #include <iostream> int main() { std::vector<int> v; for(int i = 0; i < 10; ++i) v.push_back(i); boost::for_each(v | boost::adaptors::transformed([](int i) { return i * 2; }), [](int i) { std::cout << i << std::endl; }); } g++4.5 gives around 34k of error messages, while VC10 has a mere 22k. The root of these problems is that lambda functions don't conform to the tr1::result_of protocol -- there is no nested result_type member, nor nested result struct. The standard doesn't mandate this case since decltype may be used to deduce the return type on C++11-conforming compilers. boost::result_of disables the use of decltype on many compilers in favor of tr1-style deduction due to weaknesses in the implementation of decltype. While it is important to use tr1-protocol result_of to allow code involving incomplete types to compile, it would be very convenient to fall back to a decltype approach when it's detected that the tr1 protocol is not being followed. Jeff Hellrung suggested[1] a fallback to decltype *only* for compilers which had nonconforming decltype operators. Thus the only behavioral change would be that some code which before would produce an error would now compile and run correctly. A ticket[1] with a patch (including tests and docs) was created. Daniel Walker suggested further discussion on the list, which this attempts to provoke. I think this would be a nice improvement for a set of often-used compilers -- the list of boost-users questions whose problems could be addressed by this patch is extensive (and can be provided, if desired). Thanks, Nate [1] http://boost.2283326.n4.nabble.com/Range-amp-c-0x-Lambdas-Can-this-be-done-…<http://boost.2283326.n4.nabble.com/Range-amp-c-0x-Lambdas-Can-this-be-done-…> [2] https://svn.boost.org/trac/boost/ticket/7753

7 36

[type_erasure] Using any with iterator Concept.
by Adam Wulkiewicz 28 Apr '13

28 Apr '13

Hi, I'm trying to use type-erased iterator in STL algorithms, e.g. copy but get errors like this one: error C2039: 'iterator_category' : is not a member of 'boost::type_erasure::any<Concept>' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility 373 of course any doesn't define iterator_category. I'm using MSVC2010 and doing something like this: typedef boost::type_erasure::any< boost::type_erasure::iterator< boost::single_pass_traversal_tag > > iterator; // ... iterator first = return_some_iterator(...); iterator last = return_some_iterator(...); // BAM! std::copy(first, last, std::back_inserter(result)); // BAM! typedef iterator::iterator_category C; I simply tried to add it to the iterator<> Concept defined in iterator.hpp but this didn't help: template<...> struct iterator< ::boost::single_pass_traversal_tag, ...> : iterator< ::boost::incrementable_traversal_tag, ...> { typedef ValueType value_type; typedef typename iterator_reference< Reference, ValueType >::type reference; typedef DifferenceType difference_type; typedef std::input_iterator_tag iterator_category; }; Am I doing something wrong or is it an error in Boost.TypeErasure? Regards, Adam Wulkiewicz

2 2

Bernoulli Numbers Implementation With More Precision and Boost.Test
by Gaurav Deshmukh 27 Apr '13

27 Apr '13

I have further improved the implementation of 'bernoulli' function for Math.Bernoulli project idea of GSoC-2013. In my previous update, I made the return type generic. But, there was lack of precision as I had mentioned. For achieving greater accuracy, I implemented the Akiyama-Tanigawa algorithm using 'cpp_rational' data type. As there is no approximation in intermediate steps, it gives best accuracy. It can be casted to the data types of 'cpp_dec_float'. But, I think this implementation may be slower than the previous implementations. So, there is trade-off between running time and precision. We may implement 'bernoulli' function in two ways. If priority is running time than the accuracy of precision, then we can use previous implementation. If priority is the precision, then we can use this implementation. I have attached the 3 files. 1) bernoulli.hpp : It contains the function fr calculating bernoulli number. 2) example.cpp : It contains the program to test bernoulli.hpp 3) test.cpp : This is the Boost.Test comparing the values calculated by benoulli.hpp with some of the published values.

2 1

[gsoc 2013] Approximate string matching proposal
by Jan Strnad 27 Apr '13

27 Apr '13

Hi, I've already posted this but it probably got buried. My proposal for GSOC 2013 is also available at http://webdev.fit.cvut.cz/~strnaj11/gsoc/. Regards, Jan Strnad GSOC 2013 Proposal - Approximate string pattern matching ======================================================== Abstract -------- My name is Jan Strnad and this is my proposal for GSOC 2013. I would like to implement a set of approximate string matching algorithms. There are two categories of these algorithms. A representative of the first category takes two strings and computes so-called distance between those two strings. A member of the second category takes some text and a pattern and finds all approximate matches of the pattern in the text according to some given distance. I'm planning to support various distances, such as Hamming, Levenstein, Damerau–Levenshtein, Jaro, Delta, Gamma ... I'm proposing to implement a general solution that supports multiple string containers, not only std::string. There are many possible applications such as spell checking. Personal Details ---------------- Name: Jan Strnad University: Czech Technical University in Prague, Faculty of Information Technology, The Czech Republic Major: Theoretical Informatics / System Programming - studying both in parallel Degree program: MSc. Email/XMPP: hanny.strnad(a)gmail.com ICQ: 335127474 homepage: none Mailing address: Okružní 508, 788 13 Vikýřovice, Czech Republic Availability: * Start: at worse by 17th June but probably earlier * End: 21st September * I have no other duties during this period but I may take a one week vacation. * I'm planning to spend 40-45 hours per week. Background ---------- Please summarize your educational background I'm first year master's student at CTU in Prague with major in Theoretical Informatics and System Programming. At this university I also gained my BSc. degree (Software Engineering, with honors) in June 2012. Here's an incomplete list of courses I have taken so far: Data structures and algorithms, Graph theory, Complexity theory, Automata and grammar theory, Compiler design course, Software engineering courses (including practical ones), various programming languages (C, C++, Java, Scala, Common Lisp, Haskell, Erlang, SML), various programming paradigms (imperative, object-oriented, functional, logical), math & statistics courses, Data compression, String pattern matching course, Computer architecture related courses, Parallel algorithms course and many others. I also spent 4 months as an exchange student in Uppsala University, Sweden where I took Constraint programming and Software verification courses. Please summarize your programming background I'm able to code in many languages, but I'm most experienced in C++ (5 years) and Scala languages (1.5 years). My C++ experience is gained mostly from school's projects an my small own projects (usually some kind of small tweaks of third party programs). I have an experience with C++ templates, multi-threading using both POSIX threads and openMP, STL and with some of the Boost libraries (Program Options, Smart Ptr). I definitely not know everything that would be needed for my GSOC project, but I'm quick learner. Please tell us a little about your programming interests. Please tell us why you are interested in contributing to the Boost C++ Libraries. What is your interest in the project you are proposing? As you may have guested, my professional interests are programming languages (especially their paradigms), concurrent & parallel programming and finally everything related to theoretical informatics. That includes things such as data compression or pattern matching. This is also one of the reasons why I want to contribute to Boost. I want to share my knowledge of pattern matching algorithms and I believe that the Boost project is the right place. I'm seeking for an off the school programming experience. Another reason is that since I'm a long time user of various open source software, I believe that it is time to start to contribute to community as well. From this program I mostly expecting gaining some real world experience. My C++ and especially Boost knowledge should improve significantly. Have you done any previous work in this area before or on similar projects? I think I have everything that is needed to successfully complete this project. I have a theoretical foundations of approximate string matching algorithms from my university courses as well as I'm able to implement them using C++ without any major issues. What are your plans beyond this Summer of Code time frame for your proposed work?. I know that it may take a long time for a project to become a part of Boost library. So, if selected, my intentions after the summer is over are: 1. Release my project as an open-source, not necessary as a standard part of Boost library. 2. Do everything necessary to include my work as a part of standard part of Boost library eventually. 3. Further development: adding support of more distances, implementing another string algorithms such as repetitions searching. This heavily depends on users' interest. I know that my work won't end by the end of summer. I'm willing to spend a couple of hours per week (say 2 or 3) to keep my project updated and most importantly alive. Languages, technologies, tools My regular C++ development environment is consisted of Linux, git, CMake, Sublime text, gdb and valgrind. I have also used Eclipse and svn before. For documentation purposes I'm most familiar with Doxygen. Here is a self-evaluation of desired skills: C++ 3 STL 4 Boost libraries 1 Subversion 3 Proposal -------- Approximate string matching is used in many areas. To name some of them, there are spell checking and DNA processing. I can also imagine many applications in human-to-computer interaction. I'm proposing an extension of Boost String algorithms library. I would like to implement algorithms of two categories: 1. Compute distance of two strings. Imagine a function that takes two strings a returns a number describing their distance (various distances are described below). 2. Find all approximate matches of a pattern in some text using given distance. Example of this can be found in API interface usage example. Distance is defined as a number (or a tuple of numbers) describing similarity of two strings. Here is a list of all distances I'm planning to implement: 1. Hamming - a number of replace (single character only) operations needed so that the strings match exactly. 2. Levenstein - a number of insert, delete and replace operations. 3. Generalized Levenstein (Weighted Levenstein) - same as before but each operation may have different cost. 4. Damerau-Levenstein - a number of insert, delete, replace and transpose (of two adjacent characters) operations. 5. Weigted Damerau-Levenstein - same as before but each operation may have different cost. 6. Jaro - please see [1] 7. Jaro-Winkler - also see [1] (following assumes we can compute distance of two characters, eg. c - a = 2) 8. Delta - the maximum number of distance between two characters, eg. Delta(aaa,bbb) = Delta(aaa,aab) = 1. 9. Gamma - a cumulative distance between two characters, Gamma(aaa,bbb) = 3. 10. (Delta, Gamma) - a combination of two preceding distances. Distance 10 is not exactly needed, but I included it because it is quite common to compute both Delta and Gamma distances at the same time, so I provided efficient algorithm for this. As noted, when using distances 8-10 we must be able to compute distance between two characters. This behavior should be customizable as well. Simple API definition follows. It's very immature and it will change but it should give you general idea: ~~~~ {.cpp} namespace boost{ template <typename TRange> std::size_t hamming_dist(TRange first, TRange second); template <typename TRange> std::size_t levenstein_dist(TRange first, TRange second); template <typename TRange, typename Type> Type weighted_levenstein_dist(TRange first, TRange second, Type replace_cost, Type insert_cost, Type delete_cost); template <typename TRange> std::size_t damerau_levenstein_dist(TRange first, TRange second); template <typename TRange, typename Type> Type weighted_damerau_levenstein_dist(TRange first, TRange second, Type replace_cost, Type insert_cost, Type delete_cost, Type transpose_cost); template <typename TRange> std::size_t delta_dist(TRange first, TRange second); template <typename TRange> std::size_t gamma_dist(TRange first, TRange second); template <typename TRange> float jaro_dist(TRange first, TRange second); template <typename TRange> float jaro_winkler_dist(TRange first, TRange second, float weight); template <typename TRange> std::pair<std::size_t, std::size_t> deltagamma_dist(TRange first, TRange second); template <typename Type> class approximate_distance { // ... }; class hamming_distance : public approximate_distance<std::size_t>{}; template <typename Type, typename TRange> class approx_pattern { public: approx_pattern(approximate_distance<Type>& distance, Type max_allowed, TRange pattern); }; template <typename Type, typename TRange> class sapprox_match_iterator { public: sapprox_match_iterator(TRange text, approx_pattern<Type, TRange>); // overloaded ++ and * operators }; template <typename Type, typename TRange> class sapprox_match_result { public: Type distance() const; std::size_t startIndex() const; std::size_t endIndex() const; TRange str() const; }; } ~~~~ Here is an example of usage: ~~~~ {.cpp} string a = "aaabc"; string b = "aaacb"; cout << boost::hamming_dist(a, b) << endl; // prints 2 cout << boost::damerau_levenstein_dist(a, b) << endl; // prints 1 string pattern = "acbdef"; string text = "aacdefbcdefabccef"; boost::approx_pattern ap(boost::hamming_distance, 1, pattern ); boost::sapprox_match_iterator begin( text, ap ); boost::sapprox_match_iterator end; std::for_each( begin, end, []( const boost::sapprox_match_result& what ) { cout << what.str() << " starting at " << what.startIndex() << endl; } ); // aacdef at 0 , fbcdef at 5, abccef at 11 ~~~~ As you can see, I would like my implementation to be general so that other string containers can be used instead of std::string. A will also take care of proper design in a way that further distances can be easily added later. There are multiple implementation approaches that can be used: NFA simulation, Shift-or algorithm and dynamic programming approach. I will probably choose the dynamic programming - it has low time and space complexity as well as it does not require any kind of preprocessing. Thus searching all occurrences of pattern in a text has O(m*n) complexity, m is length of pattern, n is length of text. Related work There is currently only one C++ library I know of: Flamingo [2]. From my point of view, its usage is a kind of complicated. You can also find implementations of single functions on-line, but they lack of multiple distances support as well as they are not general (eg. designed for C-like strings only). Another related project is stringmetrics [3]. This project is written in Scala so it is not related to C++ programmers. Schedule -------- This is an approximate schedule I would like to keep on. Since I will probably hit many unexpected issues I have reserved some time for it. 17th June : start 17th June - 27th June : prototyping and designing API interface as well as auxiliary functions / classes 28th June - 30th June : setting up testing environment, writing basic unit tests 1st July - 14th July : implementation of general dynamic programming model that will be used by most distances 15th July - 28th July : implementation of distances 1 - 5 29th July - 4th August : implementation of distances 8 - 10 5th August - 11th August : implementation of distances 6,7 12th August - 1st September : implementation of approximate pattern search in a text for all distances 2nd September - 15th September : wrapping up, end user documentation 16th September - 21st September : reserved During all implementation phases I'll be also performing testing and source code documentation. References ---------- [1] http://en.wikipedia.org/wiki/Jaro-Winkler_distance [2] http://flamingo.ics.uci.edu/releases/4.1/ [3] http://rockymadden.com/stringmetric/

1 0

[gsoc 2013] chrono::date
by Anurag Kalia 27 Apr '13

27 Apr '13

After going through related docs and general information, I have some questions regarding the chrono::date library. What is the origin of the name 'chrono'? I have assumed till now, it has something to do with chronology, but I am not sure.Why is date a part of 'chrono' at all? As I understand, chrono::date library is supposed to be based on the counts of sunrises. I am in favour of it because it elegantly circumvents the complications of leap seconds which are unnecessary with date-related arithmetic. But if we want it to be compatible with the rest of chrono library, complications arise:If we use a definition in line with principles of chrono (i.e. not using sunrises for a moment), a date really becomes a time-interval defined by the 00:00:00 of that date + a duration of 1 day, if we follow the rules of chrono library. But the length of a day can be changed today due to insertion/deletion of leap seconds to the conventional 24-hour day, if needed. Moreover, this change is arbitrary, since leap seconds are used to keep the time in sync with earth's rotations, which changes without a fixed pattern.The length of month and year similarly are complicated, not only by the length of days in it (see above) but also by the variable number of days. For example January has 31 days, April has 30 days and February has 28 or 29 days depending upon common year or leap year respectively. Due to the latter, length of year also varies between 365 and 366 days.In essence, there is no fixed duration of day, month or year; unlike the rest of chrono library which fundamentally is based on 'duration' class.Now if we revert to our original definition, our library basically becomes a count of sunrises since epoch. Aren't we forming an independent library from chrono then?What does one mean when one says the chrono::date library interoperates with rest of chrono library? This question is an offshoot of previous question. I am confused as to how far can both parts interoperate given the above-mentioned complications. Subtraction of dates yields us theoretically a duration of a number of days. But since actual time duration of a day is ill-defined (see above), we have to return the answer in resolution of seconds, if we use 'duration' at all. I am unable to think of more possibilities of cross-pollination between the two parts. Am I correct in my reasoning? I am genuinely stuck at this clubbing up of unrelated (to me) classes. Even more so because Boost already supplies such a vast number of header files with least number of interdependencies. A smaller self-contained date library seems (to me) more in line with its principles. Thanks,Anurag Kalia.

5 10

Re: [boost] [gsoc-2013] Boost.Thread/ThreadPool project
by Niall Douglas 27 Apr '13

27 Apr '13

> > [1] http://danlincan.3owl.com/gsoc/Proposal.pdf > > > I have some questions: > > * Why the submit function of all the thread pools doesn't returns the same? > * What is the advantage of returning future from submit call? > .... My personal big issue with a Boost.Thread threadpool is why adding one is necessary when forty lines of C++11 code using Boost.ASIO implements you one: /*! \class thread_pool \brief A very simple thread pool based on Boost.ASIO and std::thread */ class thread_pool { class worker { thread_pool *pool; public: explicit worker(thread_pool *p) : pool(p) { } void operator()() { pool->service.run(); } }; friend class worker; std::vector< std::unique_ptr<thread> > workers; boost::asio::io_service service; boost::asio::io_service::work working; public: //! Constructs a thread pool of \em no workers explicit thread_pool(size_t no) : working(service) { workers.reserve(no); for(size_t n=0; n<no; n++) workers.push_back(std::unique_ptr<thread>(new thread(worker(this)))); } ~thread_pool() { service.stop(); for(auto &i : workers) i->join(); } //! Returns the underlying io_service boost::asio::io_service &io_service() { return service; } //! Sends some callable entity to the thread pool for execution template<class F> future<typename std::result_of<F()>::type> enqueue(F f) { typedef typename std::result_of<F()>::type R; // Somewhat annoyingly, io_service.post() needs its parameter to be copy constructible, // and packaged_task is only move constructible, so ... auto task=std::make_shared<boost::packaged_task<R>>(std::move(f)); // NOTE to self later: this ought to go to std::packaged_task<R()> service.post(std::bind([](std::shared_ptr<boost::packaged_task<R>> t) { (*t)(); }, task)); return task->get_future(); } }; ... and you're done. Moreover, this thread pool integrates seamlessly with Boost.ASIO ioservice callback dispatch which is a huge plus. I took that example from some page on the internet, so I don't claim I wrote most of the above. Do bear in mind before you respond that parts of Boost.ASIO are scheduled to enter the standard in TR2, therefore no you won't need Boost.ASIO as a dependency soon. I'm not ruling out the merit of a Boost.Thread threadpool. For me personally though, the hurdle is very significantly raised: you need to strongly prove to me why your proposed thread pool is much superior to a Boost.ASIO based threadpool. Otherwise I will zero score the GSoC proposal, because in the end we need other proposed projects more. By the way, I actually don't object at all if your proposed Boost.Thread threadpool is a thin wrapper of Boost.ASIO. That, actually, is just fine with me, though I'd doubt Google would feel it substantial enough for GSoC funding seeing as it would be finished within a week. Niall

3 3

[operators] v2 test code
by Andrew Ho 26 Apr '13

26 Apr '13

I took a some time re-working the operators header based on previous feedback provided. Hopefully this will allow us to get a rough base worked out and we can work through some of the details. Most of the general idea is the same as v1, but there are a few changes and in general is not backwards-compatible. As far as I know this should be usable and support at least all of the features provided by v1 or something equivalent (see notes). codepad link: http://codepad.org/F2LrIUD2 notes: 1. Rather than using op1/op2, this version uses template specialization to make the distinction between the two. 2. All math operators have commutative and non-commutative versions, as well as left versions. Distinction is made by struct name, i.e. op is non- commutative, op_commutative is commutative, and op_left is the left variation. Note that there isn't any hard checks to prevent op_left<T, T> (which obviously makes no sense, may even result in a compiler error regardless), but the internal composite operators all use template partial specialization which don't have op_left if U = T. 3. I opted for the return-by-value only method to safely handle move semantics (see other discussion Daniel started for why). Changing this to the unsafe version is as simple as replacing the basic operator definition macro (I have that code, too. Let me know if I should post this, too). 4. Pretty much all code which alluded to a specific compiler bug/support has been removed. This includes NRVO code. I'm still not sure what level of backwards-compatibility or specific compiler code we wanted so I just code to C++03/C++11. 5. I haven't added noexcept yet (mainly because I haven't had the time to learn more about noexcept yet). My testing has nearly all so far been done in VS2012 which has an "illustrious reputation" with standards compliance. I also have access to VS2010 and MinGW (GCC 4.7.2) so I'll try testing these later, but I don't have a setup for testing compilers in Linux/Unix/Mac or any other compilers we may want to support (Clang, Intel, Embarcadero/Borland, etc.). A few questions I have: 1. In v1 operators were always considered commutative/non-commutative. The composite operators take advantage of this fact, and I have the composite operators implemented with the same assumptions. Are there any composite operators we want to provide which make different assumptions (for example, a matrix has commutative add/subtract, but non-commutative multiply)? 2. I'm a little unsure if the <boost/iterator.hpp> include is still required. It compiled fine without it, but I haven't tried out all the features to see if it is indeed required. Anyone know why we should keep this include in v2? Feedback would be appreciated, thanks.

2 4

GSoC : Boost.Math Bernoulli Numbers
by Gaurav Deshmukh 26 Apr '13

26 Apr '13

Hi, I am Gaurav Deshmukh, CSE second year student. I am interested in the idea of adding support to Bernoulli's number to special functions in Boost.Math for GSoC-2013. I have the experience of using Boost libraries and generics in C++. I have experience to use git. I have also learned to use Boost Test upto some extent. I have tried to implement naive Akiyama–Tanigawa algorithm for second Bernoulli numbers using multi-precision boost class *'number' (cpp_dec_float_50**)*. I have attached two files. The header file *bernoulli.hpp* contains the function to calculate second bernoulli number for n<3000. *exampe.cpp *is made to test the bernoulli.hpp .

2 2

[gsoc-2013]Approximate string matching
by Yu Jiang 26 Apr '13

26 Apr '13

Hello, I'm Yu Jiang, currently a master student from Tsinghua University in China. I'm attracted by the idea of "approximate string matching" since it's highly related about my research and also my interest. I have seen in a previous discussion, another student proposed to implement some basic matching functions such as "edit distance" for boost. He said by using dynamic programming, the time complexity is O(m*n). However, if we give a threshold T and only report the exact edit distance if it's no larger than T, the complexity can be O(T * min(m,n)). I think sometimes we just need to decide whether the edit distance is small enough. Furthermore, I'm also interested in approximate string search. That is, given a query string word Q and a candidate word set S, find all the strings in S who have the edit distance no larger than a threshold T with the query string. This is very useful in many area such as data integration, and I have strong knowledge in fast algorithms to solve this. So, is it compatible for gsoc 2013 and for boost? Looking forward to your opinions. Thanks, Yu

3 4