This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] libstdc++: add uniform on sphere distribution


Ed's submission of the logistic regression distribution caused problems
for me because, like Ed, I have changes to the <ext/random> header in my
tree for a long time.  Time to submit them.

This first one is a new distribution.  It generates coordinates for
random points on a unit sphere in arbitrarily many dimensions.  This
distribution by itself is useful but if I get some other code fully
implemented it will also form the basis for yet another, more
sophisticated distribution.

The patch is tested against the current tree without causing additional
problems.

OK?


2014-07-12  Ulrich Drepper  <drepper@gmail.com>

	* include/ext/random: Add uniform_on_sphere_distribution definition.
	* include/ext/random.tcc: Add out-of-band member function definitions
	for uniform_on_sphere_distribution.
	* libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/
	cons/default.cc: New file.
        *
	* libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/
        operators/equal.cc: New file.
        *
	* libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/
        operators/inequal.cc: New file.
        *
	* libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/
        operators/serialize.cc: New file.
        *
	* libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/
        operators/values.cc: New file.


diff --git a/libstdc++-v3/include/ext/random b/libstdc++-v3/include/ext/random
--- a/libstdc++-v3/include/ext/random
+++ b/libstdc++-v3/include/ext/random
@@ -36,6 +36,7 @@
 #else
 
 #include <random>
+#include <algorithm>
 #include <array>
 #include <ext/cmath>
 #ifdef __SSE2__
@@ -3293,6 +3294,196 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       const logistic_distribution<_RealType1>& __d2)
     { return !(__d1 == __d2); }
 
+
+  /**
+   * @brief A distribution for random coordinates on a unit sphere.
+   *
+   * The method used in the generation function is attributed by Donald Knuth
+   * to G. W. Brown, Modern Mathematics for the Engineer (1956).
+   */
+  template<std::size_t _Dimen, typename _RealType = double>
+    class uniform_on_sphere_distribution
+    {
+      static_assert(std::is_floating_point<_RealType>::value,
+		    "template argument not a floating point type");
+      static_assert(_Dimen != 0, "dimension is zero");
+
+    public:
+      /** The type of the range of the distribution. */
+      typedef std::array<_RealType, _Dimen> result_type;
+      /** Parameter type. */
+      struct param_type
+      {
+	explicit
+	param_type()
+	{ }
+
+	friend bool
+	operator==(const param_type& __p1, const param_type& __p2)
+	{ return true; }
+      };
+
+      /**
+       * @brief Constructs a uniform on sphere distribution.
+       */
+      explicit
+      uniform_on_sphere_distribution()
+      : _M_param(), _M_n(_RealType(0), _RealType(1))
+      { }
+
+      explicit
+      uniform_on_sphere_distribution(const param_type& __p)
+      : _M_param(__p), _M_n(_RealType(0), _RealType(1))
+      { }
+
+      /**
+       * @brief Resets the distribution state.
+       */
+      void
+      reset()
+      { }
+
+      /**
+       * @brief Returns the parameter set of the distribution.
+       */
+      param_type
+      param() const
+      { return _M_param; }
+
+      /**
+       * @brief Sets the parameter set of the distribution.
+       * @param __param The new parameter set of the distribution.
+       */
+      void
+      param(const param_type& __param)
+      { _M_param = __param; }
+
+      /**
+       * @brief Returns the greatest lower bound value of the distribution.
+       * This function makes no sense for this distribution.
+       */
+      result_type
+      min() const
+      {
+	result_type __res;
+	__res.fill(0);
+	return __res;
+      }
+
+      /**
+       * @brief Returns the least upper bound value of the distribution.
+       * This function makes no sense for this distribution.
+       */
+      result_type
+      max() const
+      {
+	result_type __res;
+	__res.fill(0);
+	return __res;
+      }
+
+      /**
+       * @brief Generating functions.
+       */
+      template<typename _UniformRandomNumberGenerator>
+	result_type
+	operator()(_UniformRandomNumberGenerator& __urng)
+	{ return this->operator()(__urng, _M_param); }
+
+      template<typename _UniformRandomNumberGenerator>
+	result_type
+	operator()(_UniformRandomNumberGenerator& __urng,
+		   const param_type& __p);
+
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate(_ForwardIterator __f, _ForwardIterator __t,
+		   _UniformRandomNumberGenerator& __urng)
+	{ this->__generate(__f, __t, __urng, this->param()); }
+
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate(_ForwardIterator __f, _ForwardIterator __t,
+		   _UniformRandomNumberGenerator& __urng,
+		   const param_type& __p)
+	{ this->__generate_impl(__f, __t, __urng, __p); }
+
+      template<typename _UniformRandomNumberGenerator>
+	void
+	__generate(result_type* __f, result_type* __t,
+		   _UniformRandomNumberGenerator& __urng,
+		   const param_type& __p)
+	{ this->__generate_impl(__f, __t, __urng, __p); }
+
+      /**
+       * @brief Return true if two uniform on sphere distributions have
+       *        the same parameters and the sequences that would be
+       *        generated are equal.
+       */
+      friend bool
+      operator==(const uniform_on_sphere_distribution& __d1,
+		 const uniform_on_sphere_distribution& __d2)
+      { return true; }
+
+      /**
+       * @brief Inserts a %uniform_on_sphere_distribution random number distribution
+       * @p __x into the output stream @p __os.
+       *
+       * @param __os An output stream.
+       * @param __x  A %uniform_on_sphere_distribution random number distribution.
+       *
+       * @returns The output stream with the state of @p __x inserted or in
+       * an error state.
+       */
+      template<size_t _Dimen1, typename _RealType1, typename _CharT,
+	       typename _Traits>
+	friend std::basic_ostream<_CharT, _Traits>&
+	operator<<(std::basic_ostream<_CharT, _Traits>& __os,
+		   const __gnu_cxx::uniform_on_sphere_distribution<_Dimen1,
+								   _RealType1>&
+		   __x);
+
+      /**
+       * @brief Extracts a %uniform_on_sphere_distribution random number distribution
+       * @p __x from the input stream @p __is.
+       *
+       * @param __is An input stream.
+       * @param __x  A %uniform_on_sphere_distribution random number generator engine.
+       *
+       * @returns The input stream with @p __x extracted or in an error state.
+       */
+      template<std::size_t _Dimen1, typename _RealType1, typename _CharT,
+	       typename _Traits>
+	friend std::basic_istream<_CharT, _Traits>&
+	operator>>(std::basic_istream<_CharT, _Traits>& __is,
+		   __gnu_cxx::uniform_on_sphere_distribution<_Dimen1,
+							     _RealType1>& __x);
+
+    private:
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate_impl(_ForwardIterator __f, _ForwardIterator __t,
+			_UniformRandomNumberGenerator& __urng,
+			const param_type& __p);
+
+      param_type _M_param;
+      std::normal_distribution<_RealType> _M_n;
+    };
+
+  /**
+   * @brief Return true if two uniform on sphere distributions are different.
+   */
+  template<std::size_t _Dimen, typename _RealType>
+    inline bool
+    operator!=(const __gnu_cxx::uniform_on_sphere_distribution<_Dimen,
+	       _RealType>& __d1,
+	       const __gnu_cxx::uniform_on_sphere_distribution<_Dimen,
+	       _RealType>& __d2)
+   { return false; }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace __gnu_cxx
 
diff --git a/libstdc++-v3/include/ext/random.tcc b/libstdc++-v3/include/ext/random.tcc
--- a/libstdc++-v3/include/ext/random.tcc
+++ b/libstdc++-v3/include/ext/random.tcc
@@ -1539,6 +1539,63 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __is;
     }
 
+
+  template<std::size_t _Dimen, typename _RealType>
+    template<typename _UniformRandomNumberGenerator>
+      typename uniform_on_sphere_distribution<_Dimen, _RealType>::result_type
+      uniform_on_sphere_distribution<_Dimen, _RealType>::
+      operator()(_UniformRandomNumberGenerator& __urng,
+		 const param_type& __p)
+      {
+	result_type __ret;
+	_RealType __sum = _RealType(0);
+
+	std::generate(__ret.begin(), __ret.end(),
+		      [&__urng, &__sum, this](){ _RealType __t = _M_n(__urng);
+						 __sum += __t * __t;
+						 return __t; });
+	auto __norm = std::sqrt(__sum);
+	std::transform(__ret.begin(), __ret.end(), __ret.begin(),
+		       [__norm](_RealType __val){ return __val / __norm; });
+
+	return __ret;
+      }
+
+  template<std::size_t _Dimen, typename _RealType>
+    template<typename _OutputIterator,
+	     typename _UniformRandomNumberGenerator>
+      void
+      uniform_on_sphere_distribution<_Dimen, _RealType>::
+      __generate_impl(_OutputIterator __f, _OutputIterator __t,
+		      _UniformRandomNumberGenerator& __urng,
+		      const param_type& __param)
+      {
+	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator>)
+
+	while (__f != __t)
+	  *__f++ = this->operator()(__urng, __param);
+      }
+
+  template<std::size_t _Dimen, typename _RealType, typename _CharT,
+	   typename _Traits>
+    std::basic_ostream<_CharT, _Traits>&
+    operator<<(std::basic_ostream<_CharT, _Traits>& __os,
+	       const __gnu_cxx::uniform_on_sphere_distribution<_Dimen,
+							       _RealType>& __x)
+    {
+      return __os;
+    }
+
+  template<std::size_t _Dimen, typename _RealType, typename _CharT,
+	   typename _Traits>
+    std::basic_istream<_CharT, _Traits>&
+    operator>>(std::basic_istream<_CharT, _Traits>& __is,
+	       __gnu_cxx::uniform_on_sphere_distribution<_Dimen,
+							 _RealType>& __x)
+    {
+      return __is;
+    }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
diff -durpN a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/cons/default.cc b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/cons/default.cc
--- a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/cons/default.cc	1969-12-31 19:00:00.000000000 -0500
+++ b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/cons/default.cc	2014-04-15 22:49:24.971799863 -0400
@@ -0,0 +1,45 @@
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+//
+// 2014-04-15  Ulrich Drepper  <drepper@gmail.com>
+//
+// Copyright (C) 2014 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/>.
+
+// 26.4.8.3.* Class template uniform_in_sphere [rand.dist.ext.uniform_on_sphere]
+// 26.4.2.4 Concept RandomNumberDistribution [rand.concept.dist]
+
+#include <ext/random>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test [[gnu::unused]] = true;
+
+  __gnu_cxx::uniform_on_sphere_distribution<2> u2;
+  __gnu_cxx::uniform_on_sphere_distribution<3> u3;
+  __gnu_cxx::uniform_on_sphere_distribution<4, double> u4;
+  __gnu_cxx::uniform_on_sphere_distribution<5, float> u5;
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff -durpN a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/equal.cc b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/equal.cc
--- a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/equal.cc	1969-12-31 19:00:00.000000000 -0500
+++ b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/equal.cc	2014-04-15 22:58:59.474117608 -0400
@@ -0,0 +1,43 @@
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+//
+// 2014-04-15  Ulrich Drepper  <drepper@gmail.com>
+//
+// Copyright (C) 2014 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/>.
+
+// 26.5.8.4.5 Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere]
+
+#include <ext/random>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test [[gnu::unused]] = true;
+
+  __gnu_cxx::uniform_on_sphere_distribution<3> u, v;
+
+  VERIFY( u == v );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff -durpN a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/inequal.cc b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/inequal.cc
--- a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/inequal.cc	1969-12-31 19:00:00.000000000 -0500
+++ b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/inequal.cc	2014-04-15 23:00:48.489580407 -0400
@@ -0,0 +1,43 @@
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+//
+// 2014-04-15  Ulrich Drepper  <drepper@gmail.com>
+//
+// Copyright (C) 2014 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/>.
+
+// 26.5.8.4.5 Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere]
+
+#include <ext/random>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test [[gnu::unused]] = true;
+
+  __gnu_cxx::uniform_on_sphere_distribution<3> u, v;
+
+  VERIFY( !(u != v) );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff -durpN a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/serialize.cc b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/serialize.cc
--- a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/serialize.cc	1969-12-31 19:00:00.000000000 -0500
+++ b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/serialize.cc	2014-04-15 23:11:10.041160516 -0400
@@ -0,0 +1,50 @@
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+//
+// 2014-04-15  Ulrich Drepper  <drepper@gmail.com>
+//
+// Copyright (C) 2014 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/>.
+
+// 26.4.8.3.* Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere]
+// 26.4.2.4 Concept RandomNumberDistribution [rand.concept.dist]
+
+#include <ext/random>
+#include <sstream>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test [[gnu::unused]] = true;
+
+  std::stringstream str;
+  __gnu_cxx::uniform_on_sphere_distribution<3> u, v;
+  std::minstd_rand0 rng;
+
+  u(rng); // advance
+  str << u;
+
+  str >> v;
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff -durpN a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/values.cc b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/values.cc
--- a/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/values.cc	1969-12-31 19:00:00.000000000 -0500
+++ b/libstdc++-v3/testsuite/ext/random/uniform_on_sphere_distribution/operators/values.cc	2014-04-15 23:13:17.911686481 -0400
@@ -0,0 +1,59 @@
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+// { dg-require-cmath "" }
+//
+// 2014-04-15  Ulrich Drepper  <drepper@gmail.com>
+//
+// Copyright (C) 2014 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/>.
+
+// 26.4.8.3.* Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere]
+// 26.4.2.4 Concept RandomNumberDistribution [rand.concept.dist]
+
+#include <ext/random>
+#include <functional>
+#include <testsuite_random.h>
+
+void
+test01()
+{
+  using namespace __gnu_test;
+
+  std::mt19937 eng;
+
+  __gnu_cxx::hypergeometric_distribution<> hd1{15, 3, 2};
+  auto bhd1 = std::bind(hd1, eng);
+  testDiscreteDist(bhd1, [](int k)
+		   { return hypergeometric_pdf(k, 15, 3, 2); });
+
+  __gnu_cxx::hypergeometric_distribution<> hd2{500, 50, 30};
+  auto bhd2 = std::bind(hd2, eng);
+  testDiscreteDist(bhd2, [](int k)
+		   { return hypergeometric_pdf(k, 500, 50, 30); });
+
+  __gnu_cxx::hypergeometric_distribution<> hd3{100, 20, 5};
+  auto bhd3 = std::bind(hd3, eng);
+  testDiscreteDist(bhd3, [](int k)
+		   { return hypergeometric_pdf(k, 100, 20, 5); });
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]