[patch] std::experimental::gcd and std::experimental::lcd

[patch] std::experimental::gcd and std::experimental::lcd

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 449 bytes --]

These where simple to implement (almost too simple ... I probably
got something wrong!)

Tested powerpc64le-linux, committed to trunk.


(Apart from using common_type_t, which is easy to change, these
functions meet the simpler rules for C++11 constexpr, so moving them
out of <experimental/numeric> would probably allow <ratio> to be
greatly simplified. I don't plan on doing that myself any time soon,
but it would make sense to do it some day.)


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 7605 bytes --]

commit 75a262dbda438434ec7f7ba6144e7e3ca05f5dbc
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Sat May 2 16:02:29 2015 +0100

    	* include/experimental/numeric: New. Define gcd and lcm.
    	* include/Makefile.am: Add new header.
    	* include/Makefile.in: Regenerate.
    	* testsuite/experimental/numeric/gcd.cc: New.
    	* testsuite/experimental/numeric/lcm.cc: New.
    	* doc/xml/manual/status_cxx2017.xml: Update status.
    	* doc/html/manual/status.html: Regenerate.

diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
index 80dd050..c30bf09 100644
--- a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
+++ b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
@@ -209,14 +209,13 @@ not in any particular release.
     </row>
 
     <row>
-      <?dbhtml bgcolor="#C8B0B0" ?>
       <entry>
 	<link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4061.pdf">
 	  N4061
 	</link>
       </entry>
       <entry>Greatest Common Divisor and Least Common Multiple</entry>
-      <entry>N</entry>
+      <entry>Y</entry>
       <entry>Library Fundamentals 2 TS</entry>
     </row>
 
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 6ba702c..92b386a 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -654,6 +654,7 @@ experimental_headers = \
 	${experimental_srcdir}/list \
 	${experimental_srcdir}/map \
 	${experimental_srcdir}/memory \
+	${experimental_srcdir}/numeric \
 	${experimental_srcdir}/optional \
 	${experimental_srcdir}/ratio \
 	${experimental_srcdir}/set \
diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric
new file mode 100644
index 0000000..a11516b
--- /dev/null
+++ b/libstdc++-v3/include/experimental/numeric
@@ -0,0 +1,88 @@
+// <experimental/numeric> -*- C++ -*-
+
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file experimental/numeric
+ *  This is a TS C++ Library header.
+ */
+
+//
+// N4336 Working Draft, C++ Extensions for Library Fundamentals, Version 2
+//
+
+#ifndef _GLIBCXX_EXPERIMENTAL_NUMERIC
+#define _GLIBCXX_EXPERIMENTAL_NUMERIC 1
+
+#pragma GCC system_header
+
+#if __cplusplus <= 201103L
+# include <bits/c++14_warning.h>
+#else
+
+#include <experimental/type_traits>
+#include <cmath>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace experimental
+{
+inline namespace fundamentals_v2
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+#define __cpp_lib_experimental_gcd_lcm 201411
+
+  // Greatest common divisor
+  template<typename _Mn, typename _Nn>
+    constexpr common_type_t<_Mn, _Nn>
+    gcd(_Mn __m, _Nn __n)
+    {
+      static_assert(is_integral<_Mn>::value, "arguments to gcd are integers");
+      static_assert(is_integral<_Nn>::value, "arguments to gcd are integers");
+
+      return __m == 0 ? std::abs(__n)
+	: __n == 0 ? std::abs(__m)
+	: fundamentals_v2::gcd(__n, __m % __n);
+    }
+
+  // Least common multiple
+  template<typename _Mn, typename _Nn>
+    constexpr common_type_t<_Mn, _Nn>
+    lcm(_Mn __m, _Nn __n)
+    {
+      static_assert(is_integral<_Mn>::value, "arguments to lcm are integers");
+      static_assert(is_integral<_Nn>::value, "arguments to lcm are integers");
+
+      return (__m != 0 && __n != 0)
+	? (std::abs(__m) / fundamentals_v2::gcd(__m, __n)) * std::abs(__n)
+	: 0;
+    }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace fundamentals_v2
+} // namespace experimental
+} // namespace std
+
+#endif // __cplusplus <= 201103L
+
+#endif // _GLIBCXX_EXPERIMENTAL_NUMERIC
diff --git a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
new file mode 100644
index 0000000..efbe273
--- /dev/null
+++ b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
@@ -0,0 +1,28 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+// { dg-do compile }
+
+#include <experimental/numeric>
+
+using std::experimental::fundamentals_v2::lcm;
+
+static_assert(lcm(21, 6) == 42, "");
+static_assert(lcm(41, 0) == 0, "LCD with zero is zero");
+static_assert(lcm(0, 7) == 0, "LCD with zero is zero");
+static_assert(lcm(0, 0) == 0, "no division by zero");
diff --git a/libstdc++-v3/testsuite/experimental/numeric/lcm.cc b/libstdc++-v3/testsuite/experimental/numeric/lcm.cc
new file mode 100644
index 0000000..359fa09
--- /dev/null
+++ b/libstdc++-v3/testsuite/experimental/numeric/lcm.cc
@@ -0,0 +1,32 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+// { dg-do compile }
+
+#include <experimental/numeric>
+
+using std::experimental::fundamentals_v2::gcd;
+
+static_assert( gcd(1071, 462) == 21, "" );
+static_assert( gcd(2000, 20) == 20, "" );
+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, "" );
+

Re: [patch] std::experimental::gcd and std::experimental::lcd

[Marc Glisse]

On Sat, 2 May 2015, Jonathan Wakely wrote:

> These where simple to implement (almost too simple ... I probably
> got something wrong!)

I didn't remember that std::abs works for unsigned. It will need more work 
for performance, but that can certainly be done later (I didn't look at 
the code beyond checking what you meant by "simple").

> (Apart from using common_type_t, which is easy to change, these
> functions meet the simpler rules for C++11 constexpr, so moving them
> out of <experimental/numeric> would probably allow <ratio> to be
> greatly simplified. I don't plan on doing that myself any time soon,
> but it would make sense to do it some day.)

gcd is not really the hard part in ratio. But constexpr should help, it 
made sense not to have it in tr1, but I don't remember why we didn't use 
it in the more recent changes (2011, the compiler probably already 
supported constexpr). Maybe the interesting functions were too hard to 
write as one-liners...

-- 
Marc Glisse

Re: [patch] std::experimental::gcd and std::experimental::lcd

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1504 bytes --]

On 02/05/15 18:27 +0200, Marc Glisse wrote:
>On Sat, 2 May 2015, Jonathan Wakely wrote:
>
>>These where simple to implement (almost too simple ... I probably
>>got something wrong!)
>
>I didn't remember that std::abs works for unsigned. It will need more 
>work for performance, but that can certainly be done later (I didn't 
>look at the code beyond checking what you meant by "simple").

std::abs seems to work fine for unsigned, the overload in <cmath> for
integral types just uses __builtin_fabs. Maybe it would be better for
gcd() to just use that directly instead of including <cmath> (as
attached, which also removes the qualification on the call to gcd
because the functions only work for integral types which have no
associated namespaces anyway).

>>(Apart from using common_type_t, which is easy to change, these
>>functions meet the simpler rules for C++11 constexpr, so moving them
>>out of <experimental/numeric> would probably allow <ratio> to be
>>greatly simplified. I don't plan on doing that myself any time soon,
>>but it would make sense to do it some day.)
>
>gcd is not really the hard part in ratio. But constexpr should help, 
>it made sense not to have it in tr1, but I don't remember why we 
>didn't use it in the more recent changes (2011, the compiler probably 
>already supported constexpr). Maybe the interesting functions were too 
>hard to write as one-liners...

<ratio> was added to libstdc++ in 2008 so I think the constexpr
support was not good enough at the time.


[-- Attachment #2: abs.txt --]
[-- Type: text/plain, Size: 1542 bytes --]

diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric
index a11516b..b284110 100644
--- a/libstdc++-v3/include/experimental/numeric
+++ b/libstdc++-v3/include/experimental/numeric
@@ -40,7 +40,6 @@
 #else
 
 #include <experimental/type_traits>
-#include <cmath>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -52,7 +51,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 #define __cpp_lib_experimental_gcd_lcm 201411
 
-  // Greatest common divisor
+  /// Greatest common divisor
   template<typename _Mn, typename _Nn>
     constexpr common_type_t<_Mn, _Nn>
     gcd(_Mn __m, _Nn __n)
@@ -60,12 +59,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static_assert(is_integral<_Mn>::value, "arguments to gcd are integers");
       static_assert(is_integral<_Nn>::value, "arguments to gcd are integers");
 
-      return __m == 0 ? std::abs(__n)
-	: __n == 0 ? std::abs(__m)
-	: fundamentals_v2::gcd(__n, __m % __n);
+      return __m == 0 ? __builtin_abs(__n)
+	: __n == 0 ? __builtin_abs(__m)
+	: gcd(__n, __m % __n);
     }
 
-  // Least common multiple
+  /// Least common multiple
   template<typename _Mn, typename _Nn>
     constexpr common_type_t<_Mn, _Nn>
     lcm(_Mn __m, _Nn __n)
@@ -74,7 +73,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static_assert(is_integral<_Nn>::value, "arguments to lcm are integers");
 
       return (__m != 0 && __n != 0)
-	? (std::abs(__m) / fundamentals_v2::gcd(__m, __n)) * std::abs(__n)
+	? (__builtin_abs(__m) / gcd(__m, __n)) * __builtin_abs(__n)
 	: 0;
     }
 

Re: [patch] std::experimental::gcd and std::experimental::lcd

[Marc Glisse]

On Sat, 2 May 2015, Jonathan Wakely wrote:

> On 02/05/15 18:27 +0200, Marc Glisse wrote:
>> On Sat, 2 May 2015, Jonathan Wakely wrote:
>> 
>>> These where simple to implement (almost too simple ... I probably
>>> got something wrong!)
>> 
>> I didn't remember that std::abs works for unsigned. It will need more work 
>> for performance, but that can certainly be done later (I didn't look at the 
>> code beyond checking what you meant by "simple").
>
> std::abs seems to work fine for unsigned, the overload in <cmath> for
> integral types just uses __builtin_fabs.

That's bad! You don't want to go through floating point, that cannot even 
represent int64_t accurately.

> Maybe it would be better for
> gcd() to just use that directly instead of including <cmath> (as
> attached, which also removes the qualification on the call to gcd
> because the functions only work for integral types which have no
> associated namespaces anyway).

Actually you use __builtin_abs (no 'f') in the patch, which apparently 
casts to int, that's even worse...

> <ratio> was added to libstdc++ in 2008 so I think the constexpr
> support was not good enough at the time.

Yes, but we modified a few pieces with Paolo in 2011, and those could have 
used constexpr I guess.

-- 
Marc Glisse

Re: [patch] std::experimental::gcd and std::experimental::lcd

[Marc Glisse]

On Sat, 2 May 2015, Jonathan Wakely wrote:

> std::abs seems to work fine for unsigned, the overload in <cmath> for
> integral types just uses __builtin_fabs.

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2192
That overload should die.

-- 
Marc Glisse

Re: [patch] std::experimental::gcd and std::experimental::lcd

[Jonathan Wakely]

On 02/05/15 19:07 +0200, Marc Glisse wrote:
>On Sat, 2 May 2015, Jonathan Wakely wrote:
>
>>On 02/05/15 18:27 +0200, Marc Glisse wrote:
>>>On Sat, 2 May 2015, Jonathan Wakely wrote:
>>>
>>>>These where simple to implement (almost too simple ... I probably
>>>>got something wrong!)
>>>
>>>I didn't remember that std::abs works for unsigned. It will need 
>>>more work for performance, but that can certainly be done later (I 
>>>didn't look at the code beyond checking what you meant by 
>>>"simple").
>>
>>std::abs seems to work fine for unsigned, the overload in <cmath> for
>>integral types just uses __builtin_fabs.
>
>That's bad! You don't want to go through floating point, that cannot 
>even represent int64_t accurately.

Good point - we should fix <cmath> then!

>>Maybe it would be better for
>>gcd() to just use that directly instead of including <cmath> (as
>>attached, which also removes the qualification on the call to gcd
>>because the functions only work for integral types which have no
>>associated namespaces anyway).
>
>Actually you use __builtin_abs (no 'f') in the patch, which apparently 
>casts to int, that's even worse...

Oops, that's a typo (I didn't even test that change).

>><ratio> was added to libstdc++ in 2008 so I think the constexpr
>>support was not good enough at the time.
>
>Yes, but we modified a few pieces with Paolo in 2011, and those could 
>have used constexpr I guess.

Ah I see. What we have now works, so it's not a priority to try and
replace bits of it with constexpr functions.