Subject: Re: [boost] [integer][math]Heads up on revised gcd/lcm code
From: Edward Diener (eldiener_at_[hidden])
Date: 2017-04-24 19:03:00
On 4/24/2017 1:37 PM, John Maddock via Boost wrote:
> First some history....
> Some time ago, the old gcd/lcm code was moved from Boost.Math to
> Boost.Integer as a means of reducing inter-library dependencies.
> Unfortunately a number of tasks were never completed: the docs weren't
> added to Boost.Integer, and the Boost.Math code never got updated to
> redirect to the moved headers. Fast forward a couple of years and when
> Jeremy Murphy contributed a new version of the gcd/lcm code as part of
> supporting polynomial gcd, and since I'd completely forgotten about the
> move, this got integrated into Boost.Math leaving us with two divergent
> As part of sorting this mess out, I've now pushed to Boost.Integer a
> "best of both" version of this code, so far as I can tell, all dependent
> libraries are unaffected by the change, though I do need to do some more
> work on supporting obsolete compilers I no longer have access to.
To which obsolete compilers are you referring ?
> The main enhancements are:
> * New mixed binary/Euclid algorithm added, this seems to be the best
> performing algorithm in most cases, and is now the default for most
> integer types (performance is deeply dependent on the input though, so
> your mileage may vary).
> * In addition to integer and rational support, polynomial gcd is now
> supported via boost::math::polynomial.
> * There are new range based gcd-lcm algorithms for calculating the
> gcd/lcm of all the values in an iterator range, this is primarily for
> polynomial gcd support.
> * There are new variadic overloads of gcd/lcm for calculating gcd/lcm
> over more than 2 values.
> * The gcd/lcm functions are now constexpr in C++14 land, this means that
> the old compile time calculation traits classes are rendered obsolete
> for current compilers.
> * The gcd/lcm functions are now noexcept where appropriate.
> * Compiler intrinsics are now used speed up binary-gcd steps where
> possible, sadly this is incompatible with constexpr support since the
> intrinsics aren't yet constexpr :(
> Please do let me know if you find any snags, best, John.
I will test rational, which is part of CMT, and uses Integer's gcd/lcm
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk