Boost logo

Boost :

Subject: [boost] [integer][math]Heads up on revised gcd/lcm code
From: John Maddock (jz.maddock_at_[hidden])
Date: 2017-04-24 17:37:47

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.

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.

This email has been checked for viruses by AVG.

Boost list run by bdawes at, gregod at, cpdaniel at, john at