From patchwork Sun Jul 13 02:00:57 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ulrich Drepper X-Patchwork-Id: 369377 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 951AF1400B5 for ; Sun, 13 Jul 2014 12:01:26 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=sjOxxhrRz6p9yKaLIHMCUHNPBS3XYkVlU6mAzPyunHCj+/ewj6/Tr 2tGGlhVK5uDD7T2O+wBd3yeLRwJ+bEKGjLxK+btm6nZ7tiYKzn3QTOHK7KmYxiWi oCSuLy0DUvY4pOB85TzTFj4GMq0kVUHRfBZp5BCa9XTHMh2jTH43sM= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=1ZYjd9nElQj1socewkoMC0qljEs=; b=TnwFyM10RVpUNjStjGTc bhH3RAe/eSpHx76v/zqXh6PesnhAXoitAfNtn1mypYAme1Ve8OncsTTao/6M8yAZ nuT4MpnFqvEzIQdMI0ipMtirGJf1E8fvdt90e0Hqxpab9Y04XKjMs1yElLLH7bHF h9iR3dhrT3G2UK6xeh22dew= Received: (qmail 27929 invoked by alias); 13 Jul 2014 02:01:14 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 25395 invoked by uid 89); 13 Jul 2014 02:01:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=3.4 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS, URIBL_BLACK autolearn=no version=3.3.2 X-HELO: mail-qc0-f174.google.com Received: from mail-qc0-f174.google.com (HELO mail-qc0-f174.google.com) (209.85.216.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Sun, 13 Jul 2014 02:01:01 +0000 Received: by mail-qc0-f174.google.com with SMTP id x13so2328546qcv.33 for ; Sat, 12 Jul 2014 19:00:59 -0700 (PDT) X-Received: by 10.224.42.196 with SMTP id t4mr9628060qae.48.1405216858967; Sat, 12 Jul 2014 19:00:58 -0700 (PDT) Received: from x240.local (cpe-68-173-15-30.nyc.res.rr.com. [68.173.15.30]) by mx.google.com with ESMTPSA id 61sm6942632qgf.15.2014.07.12.19.00.58 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 12 Jul 2014 19:00:58 -0700 (PDT) From: Ulrich Drepper X-Google-Original-From: Ulrich Drepper Received: from x240.local (localhost.localdomain [127.0.0.1]) by x240.local (8.14.8/8.14.8) with ESMTP id s6D20vM0025377 for ; Sat, 12 Jul 2014 22:00:57 -0400 Received: (from drepper@localhost) by x240.local (8.14.8/8.14.8/Submit) id s6D20vUv025376; Sat, 12 Jul 2014 22:00:57 -0400 To: gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: add uniform on sphere distribution Date: Sat, 12 Jul 2014 22:00:57 -0400 Message-ID: <87a98eow4m.fsf@x240.local.i-did-not-set--mail-host-address--so-tickle-me> MIME-Version: 1.0 Ed's submission of the logistic regression distribution caused problems for me because, like Ed, I have changes to the 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 * 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 +#include #include #include #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 + 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 + result_type + operator()(_UniformRandomNumberGenerator& __urng) + { return this->operator()(__urng, _M_param); } + + template + result_type + operator()(_UniformRandomNumberGenerator& __urng, + const param_type& __p); + + template + void + __generate(_ForwardIterator __f, _ForwardIterator __t, + _UniformRandomNumberGenerator& __urng) + { this->__generate(__f, __t, __urng, this->param()); } + + template + void + __generate(_ForwardIterator __f, _ForwardIterator __t, + _UniformRandomNumberGenerator& __urng, + const param_type& __p) + { this->__generate_impl(__f, __t, __urng, __p); } + + template + 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 + 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 + friend std::basic_istream<_CharT, _Traits>& + operator>>(std::basic_istream<_CharT, _Traits>& __is, + __gnu_cxx::uniform_on_sphere_distribution<_Dimen1, + _RealType1>& __x); + + private: + template + 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 + 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 + template + 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 + template + 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::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::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 +// +// 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 +// . + +// 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 +#include + +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 +// +// 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 +// . + +// 26.5.8.4.5 Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere] + +#include +#include + +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 +// +// 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 +// . + +// 26.5.8.4.5 Class template uniform_on_sphere_distribution [rand.dist.ext.uniform_on_sphere] + +#include +#include + +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 +// +// 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 +// . + +// 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 +#include +#include + +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 +// +// 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 +// . + +// 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 +#include +#include + +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; +}