libstdc++: Optimise GCD algorithms

The current std::gcd and std::chrono::duration::_S_gcd algorithms are
both recursive. This is potentially expensive to evaluate in constant
expressions, because each level of recursion makes a new copy of the
function to evaluate. The maximum number of steps is bounded
(proportional to the number of decimal digits in the smaller value) and
so unlikely to exceed the limit for constexpr nesting, but the memory
usage is still suboptimal. By using an iterative algorithm we avoid
that compile-time cost. Because looping in constexpr functions is not
allowed until C++14, we need to keep the recursive implementation in
duration::_S_gcd for C++11 mode.

For std::gcd we can also optimise runtime performance by using the
binary GCD algorithm.

libstdc++-v3/ChangeLog:

	* include/std/chrono (duration::_S_gcd): Use iterative algorithm
	for C++14 and later.
	* include/std/numeric (__detail::__gcd): Replace recursive
	Euclidean algorithm with iterative version of binary GCD algorithm.
	* testsuite/26_numerics/gcd/1.cc: Test additional inputs.
	* testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
	* testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
	* testsuite/experimental/numeric/gcd.cc: Test additional inputs.
	* testsuite/26_numerics/gcd/2.cc: New test.

1 files changed, 135 insertions, 1 deletions

diff --git a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
index 33568cb..8555421 100644
--- a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
+++ b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
@@ -18,8 +18,16 @@
 // { dg-do compile { target c++14 } }
 
 #include <experimental/numeric>
+#include <experimental/type_traits>
+
+#ifndef __cpp_lib_experimental_gcd_lcm
+# error "Feature-test macro for gcd missing"
+#elif __cpp_lib_experimental_gcd_lcm != 201411
+# error "Feature-test macro for gcd has wrong value"
+#endif
 
 using std::experimental::fundamentals_v2::gcd;
+using std::experimental::is_same_v;
 
 static_assert( gcd(1071, 462) == 21, "" );
 static_assert( gcd(2000, 20) == 20, "" );
@@ -27,8 +35,134 @@ static_assert( gcd(2011, 17) == 1, "GCD of two primes is 1" );
 static_assert( gcd(200, 200) == 200, "GCD of equal numbers is that number" );
 static_assert( gcd(0, 13) == 13, "GCD of any number and 0 is that number" );
 static_assert( gcd(29, 0) == 29, "GCD of any number and 0 is that number" );
-static_assert( gcd(0, 0) == 0, "" );
+static_assert( gcd(0, 0) == 0, "Zarro Boogs found" );
 
 static_assert(gcd(1u, 2) == 1, "unsigned and signed");
+static_assert(gcd(9, 6u) == 3, "unsigned and signed");
 static_assert(gcd(3, 4u) == 1, "signed and unsigned");
+static_assert(gcd(32u, 24) == 8, "signed and unsigned");
+static_assert(gcd(1u, -2) == 1, "unsigned and negative");
+static_assert(gcd(-21, 28u) == 7, "unsigned and negative");
+static_assert(gcd(-3, 4u) == 1, "negative and unsigned");
+static_assert(gcd(33u, -44) == 11, "negative and unsigned");
 static_assert(gcd(5u, 6u) == 1, "unsigned and unsigned");
+static_assert(gcd(54u, 36u) == 18, "unsigned and unsigned");
+static_assert(gcd(-5, -6) == 1, "negative and negative");
+static_assert(gcd(-50, -60) == 10, "negative and negative");
+
+static_assert( is_same_v<decltype(gcd(1l, 1)), long>, "" );
+static_assert( is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long>, "" );
+
+#include <climits>
+#include <testsuite_hooks.h>
+
+constexpr struct testcase { unsigned long long p, q, r; } testcases[] = {
+  { 5, 8, 1 },
+  { 6, 35, 1 },
+  { 30, 42, 6 },
+  { 24, 60, 12 },
+  { 55, 144, 1 },
+  { 105, 252, 21 },
+  { 253, 22121, 11 },
+  { 1386, 3213, 63 },
+  { 2028, 2049, 3 },
+  { 46391, 62527, 2017 },
+  { 63245986, 39088169, 1 },
+  { 77160074263, 47687519812, 1 },
+  { 77160074264, 47687519812, 4 },
+};
+
+template<typename P, typename Q>
+constexpr bool
+check(P p, Q q, unsigned long long r)
+{
+  using R = std::common_type_t<P, Q>;
+  static_assert( is_same_v<decltype(gcd(p, q)), R>, "" );
+  static_assert( is_same_v<decltype(gcd(q, p)), R>, "" );
+  R r1 = gcd(p, q);
+  // Check non-negative, so conversion to unsigned long doesn't alter value.
+  VERIFY( r1 >= 0 );
+  // Check for expected result
+  VERIFY( (unsigned long long)r1 == r );
+  // Check reversing arguments doesn't change result
+  VERIFY( gcd(q, p) == r1 );
+
+  P pabs = p < 0 ? -p : p;
+  VERIFY( gcd(p, p) == pabs );
+  VERIFY( gcd(0, p) == pabs );
+  VERIFY( gcd(p, 0) == pabs );
+  VERIFY( gcd(1, p) == 1 );
+  VERIFY( gcd(p, 1) == 1 );
+  Q qabs = q < 0 ? -q : q;
+  VERIFY( gcd(q, q) == qabs );
+  VERIFY( gcd(0, q) == qabs );
+  VERIFY( gcd(q, 0) == qabs );
+  VERIFY( gcd(1, q) == 1 );
+  VERIFY( gcd(q, 1) == 1 );
+  VERIFY( gcd(r, r) == r );
+  VERIFY( gcd(0, r) == r );
+  VERIFY( gcd(r, 0) == r );
+  VERIFY( gcd(1, r) == 1 );
+  VERIFY( gcd(r, 1) == 1 );
+
+  return true;
+}
+
+constexpr bool
+test01()
+{
+  for (auto t : testcases)
+  {
+    check(t.p, t.q, t.r);
+
+    if (t.p <= LONG_MAX && t.q <= LONG_MAX)
+    {
+      check( (long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p, -(long)t.p, t.p);
+
+      check( (long)t.p, t.q, t.r);
+      check(-(long)t.p, t.q, t.r);
+
+      check(t.p,  (long)t.q, t.r);
+      check(t.p, -(long)t.q, t.r);
+
+      check( (long)t.p,  (long)t.q, t.r);
+      check( (long)t.p, -(long)t.q, t.r);
+      check(-(long)t.p,  (long)t.q, t.r);
+      check(-(long)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= INT_MAX && t.q <= INT_MAX)
+    {
+      check((long)t.p,  (int)t.q, t.r);
+      check(-(int)t.p, (long)t.q, t.r);
+
+      check( (int)t.p, (unsigned)t.q, t.r);
+      check(-(int)t.p, (unsigned)t.q, t.r);
+
+      check(-(int)t.p,  -(int)t.q, t.r);
+      check(-(int)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= SHRT_MAX && t.q <= SHRT_MAX)
+    {
+      check(  (long)t.p, (short)t.q, t.r);
+      check(-(short)t.p,  (long)t.q, t.r);
+
+      check( (short)t.p, (unsigned short)t.q, t.r);
+      check(-(short)t.p, (unsigned short)t.q, t.r);
+
+      check(-(short)t.p, -(short)t.q, t.r);
+      check(-(short)t.p,  -(long)t.q, t.r);
+    }
+  }
+  return true;
+}
+
+
+int main()
+{
+  static_assert( test01() );  // constexpr
+  VERIFY( test01() );	      // non-constexpr
+}