Re: [boost] [integer][math]Heads up on revised gcd/lcm code

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 
> versions.
> 
> 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 
implementation.