libstdc++
uniform_int_dist.h
Go to the documentation of this file.
1 // Class template uniform_int_distribution -*- C++ -*-
2 
3 // Copyright (C) 2009-2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /**
26  * @file bits/uniform_int_dist.h
27  * This is an internal header file, included by other library headers.
28  * Do not attempt to use it directly. @headername{random}
29  */
30 
31 #ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H
32 #define _GLIBCXX_BITS_UNIFORM_INT_DIST_H
33 
34 #include <type_traits>
35 #include <ext/numeric_traits.h>
36 #if __cplusplus > 201703L
37 # include <concepts>
38 #endif
39 
40 namespace std _GLIBCXX_VISIBILITY(default)
41 {
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43 
44 #ifdef __cpp_lib_concepts
45  /// Requirements for a uniform random bit generator.
46  template<typename _Gen>
47  concept uniform_random_bit_generator
48  = invocable<_Gen&> && unsigned_integral<invoke_result_t<_Gen&>>
49  && requires
50  {
51  { _Gen::min() } -> same_as<invoke_result_t<_Gen&>>;
52  { _Gen::max() } -> same_as<invoke_result_t<_Gen&>>;
53  requires bool_constant<(_Gen::min() < _Gen::max())>::value;
54  };
55 #endif
56 
57  namespace __detail
58  {
59  // Determine whether number is a power of two.
60  // This is true for zero, which is OK because we want _Power_of_2(n+1)
61  // to be true if n==numeric_limits<_Tp>::max() and so n+1 wraps around.
62  template<typename _Tp>
63  constexpr bool
64  _Power_of_2(_Tp __x)
65  {
66  return ((__x - 1) & __x) == 0;
67  }
68  }
69 
70  /**
71  * @brief Uniform discrete distribution for random numbers.
72  * A discrete random distribution on the range @f$[min, max]@f$ with equal
73  * probability throughout the range.
74  */
75  template<typename _IntType = int>
77  {
79  "template argument must be an integral type");
80 
81  public:
82  /** The type of the range of the distribution. */
83  typedef _IntType result_type;
84  /** Parameter type. */
85  struct param_type
86  {
88 
89  param_type() : param_type(0) { }
90 
91  explicit
92  param_type(_IntType __a,
94  : _M_a(__a), _M_b(__b)
95  {
96  __glibcxx_assert(_M_a <= _M_b);
97  }
98 
100  a() const
101  { return _M_a; }
102 
104  b() const
105  { return _M_b; }
106 
107  friend bool
108  operator==(const param_type& __p1, const param_type& __p2)
109  { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
110 
111  friend bool
112  operator!=(const param_type& __p1, const param_type& __p2)
113  { return !(__p1 == __p2); }
114 
115  private:
116  _IntType _M_a;
117  _IntType _M_b;
118  };
119 
120  public:
121  /**
122  * @brief Constructs a uniform distribution object.
123  */
125 
126  /**
127  * @brief Constructs a uniform distribution object.
128  */
129  explicit
131  _IntType __b
133  : _M_param(__a, __b)
134  { }
135 
136  explicit
137  uniform_int_distribution(const param_type& __p)
138  : _M_param(__p)
139  { }
140 
141  /**
142  * @brief Resets the distribution state.
143  *
144  * Does nothing for the uniform integer distribution.
145  */
146  void
147  reset() { }
148 
150  a() const
151  { return _M_param.a(); }
152 
154  b() const
155  { return _M_param.b(); }
156 
157  /**
158  * @brief Returns the parameter set of the distribution.
159  */
160  param_type
161  param() const
162  { return _M_param; }
163 
164  /**
165  * @brief Sets the parameter set of the distribution.
166  * @param __param The new parameter set of the distribution.
167  */
168  void
169  param(const param_type& __param)
170  { _M_param = __param; }
171 
172  /**
173  * @brief Returns the inclusive lower bound of the distribution range.
174  */
176  min() const
177  { return this->a(); }
178 
179  /**
180  * @brief Returns the inclusive upper bound of the distribution range.
181  */
183  max() const
184  { return this->b(); }
185 
186  /**
187  * @brief Generating functions.
188  */
189  template<typename _UniformRandomBitGenerator>
191  operator()(_UniformRandomBitGenerator& __urng)
192  { return this->operator()(__urng, _M_param); }
193 
194  template<typename _UniformRandomBitGenerator>
196  operator()(_UniformRandomBitGenerator& __urng,
197  const param_type& __p);
198 
199  template<typename _ForwardIterator,
200  typename _UniformRandomBitGenerator>
201  void
202  __generate(_ForwardIterator __f, _ForwardIterator __t,
203  _UniformRandomBitGenerator& __urng)
204  { this->__generate(__f, __t, __urng, _M_param); }
205 
206  template<typename _ForwardIterator,
207  typename _UniformRandomBitGenerator>
208  void
209  __generate(_ForwardIterator __f, _ForwardIterator __t,
210  _UniformRandomBitGenerator& __urng,
211  const param_type& __p)
212  { this->__generate_impl(__f, __t, __urng, __p); }
213 
214  template<typename _UniformRandomBitGenerator>
215  void
216  __generate(result_type* __f, result_type* __t,
217  _UniformRandomBitGenerator& __urng,
218  const param_type& __p)
219  { this->__generate_impl(__f, __t, __urng, __p); }
220 
221  /**
222  * @brief Return true if two uniform integer distributions have
223  * the same parameters.
224  */
225  friend bool
227  const uniform_int_distribution& __d2)
228  { return __d1._M_param == __d2._M_param; }
229 
230  private:
231  template<typename _ForwardIterator,
232  typename _UniformRandomBitGenerator>
233  void
234  __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
235  _UniformRandomBitGenerator& __urng,
236  const param_type& __p);
237 
238  param_type _M_param;
239 
240  // Lemire's nearly divisionless algorithm.
241  // Returns an unbiased random number from __g downscaled to [0,__range)
242  // using an unsigned type _Wp twice as wide as unsigned type _Up.
243  template<typename _Wp, typename _Urbg, typename _Up>
244  static _Up
245  _S_nd(_Urbg& __g, _Up __range)
246  {
247  using _Up_traits = __gnu_cxx::__int_traits<_Up>;
248  using _Wp_traits = __gnu_cxx::__int_traits<_Wp>;
249  static_assert(!_Up_traits::__is_signed, "U must be unsigned");
250  static_assert(!_Wp_traits::__is_signed, "W must be unsigned");
251  static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits),
252  "W must be twice as wide as U");
253 
254  // reference: Fast Random Integer Generation in an Interval
255  // ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
256  // https://arxiv.org/abs/1805.10941
257  _Wp __product = _Wp(__g()) * _Wp(__range);
258  _Up __low = _Up(__product);
259  if (__low < __range)
260  {
261  _Up __threshold = -__range % __range;
262  while (__low < __threshold)
263  {
264  __product = _Wp(__g()) * _Wp(__range);
265  __low = _Up(__product);
266  }
267  }
268  return __product >> _Up_traits::__digits;
269  }
270  };
271 
272  template<typename _IntType>
273  template<typename _UniformRandomBitGenerator>
276  operator()(_UniformRandomBitGenerator& __urng,
277  const param_type& __param)
278  {
279  typedef typename _UniformRandomBitGenerator::result_type _Gresult_type;
280  typedef typename make_unsigned<result_type>::type __utype;
281  typedef typename common_type<_Gresult_type, __utype>::type __uctype;
282 
283  constexpr __uctype __urngmin = _UniformRandomBitGenerator::min();
284  constexpr __uctype __urngmax = _UniformRandomBitGenerator::max();
285  static_assert( __urngmin < __urngmax,
286  "Uniform random bit generator must define min() < max()");
287  constexpr __uctype __urngrange = __urngmax - __urngmin;
288 
289  const __uctype __urange
290  = __uctype(__param.b()) - __uctype(__param.a());
291 
292  __uctype __ret;
293  if (__urngrange > __urange)
294  {
295  // downscaling
296 
297  const __uctype __uerange = __urange + 1; // __urange can be zero
298 
299 #if defined __UINT64_TYPE__ && defined __UINT32_TYPE__
300 #if __SIZEOF_INT128__
301  if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT64_MAX__)
302  {
303  // __urng produces values that use exactly 64-bits,
304  // so use 128-bit integers to downscale to desired range.
305  __UINT64_TYPE__ __u64erange = __uerange;
306  __ret = _S_nd<unsigned __int128>(__urng, __u64erange);
307  }
308  else
309 #endif
310  if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT32_MAX__)
311  {
312  // __urng produces values that use exactly 32-bits,
313  // so use 64-bit integers to downscale to desired range.
314  __UINT32_TYPE__ __u32erange = __uerange;
315  __ret = _S_nd<__UINT64_TYPE__>(__urng, __u32erange);
316  }
317  else
318 #endif
319  {
320  // fallback case (2 divisions)
321  const __uctype __scaling = __urngrange / __uerange;
322  const __uctype __past = __uerange * __scaling;
323  do
324  __ret = __uctype(__urng()) - __urngmin;
325  while (__ret >= __past);
326  __ret /= __scaling;
327  }
328  }
329  else if (__urngrange < __urange)
330  {
331  // upscaling
332  /*
333  Note that every value in [0, urange]
334  can be written uniquely as
335 
336  (urngrange + 1) * high + low
337 
338  where
339 
340  high in [0, urange / (urngrange + 1)]
341 
342  and
343 
344  low in [0, urngrange].
345  */
346  __uctype __tmp; // wraparound control
347  do
348  {
349  const __uctype __uerngrange = __urngrange + 1;
350  __tmp = (__uerngrange * operator()
351  (__urng, param_type(0, __urange / __uerngrange)));
352  __ret = __tmp + (__uctype(__urng()) - __urngmin);
353  }
354  while (__ret > __urange || __ret < __tmp);
355  }
356  else
357  __ret = __uctype(__urng()) - __urngmin;
358 
359  return __ret + __param.a();
360  }
361 
362 
363  template<typename _IntType>
364  template<typename _ForwardIterator,
365  typename _UniformRandomBitGenerator>
366  void
367  uniform_int_distribution<_IntType>::
368  __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
369  _UniformRandomBitGenerator& __urng,
370  const param_type& __param)
371  {
372  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
373  typedef typename _UniformRandomBitGenerator::result_type _Gresult_type;
374  typedef typename make_unsigned<result_type>::type __utype;
375  typedef typename common_type<_Gresult_type, __utype>::type __uctype;
376 
377  static_assert( __urng.min() < __urng.max(),
378  "Uniform random bit generator must define min() < max()");
379 
380  constexpr __uctype __urngmin = __urng.min();
381  constexpr __uctype __urngmax = __urng.max();
382  constexpr __uctype __urngrange = __urngmax - __urngmin;
383  const __uctype __urange
384  = __uctype(__param.b()) - __uctype(__param.a());
385 
386  __uctype __ret;
387 
388  if (__urngrange > __urange)
389  {
390  if (__detail::_Power_of_2(__urngrange + 1)
391  && __detail::_Power_of_2(__urange + 1))
392  {
393  while (__f != __t)
394  {
395  __ret = __uctype(__urng()) - __urngmin;
396  *__f++ = (__ret & __urange) + __param.a();
397  }
398  }
399  else
400  {
401  // downscaling
402  const __uctype __uerange = __urange + 1; // __urange can be zero
403  const __uctype __scaling = __urngrange / __uerange;
404  const __uctype __past = __uerange * __scaling;
405  while (__f != __t)
406  {
407  do
408  __ret = __uctype(__urng()) - __urngmin;
409  while (__ret >= __past);
410  *__f++ = __ret / __scaling + __param.a();
411  }
412  }
413  }
414  else if (__urngrange < __urange)
415  {
416  // upscaling
417  /*
418  Note that every value in [0, urange]
419  can be written uniquely as
420 
421  (urngrange + 1) * high + low
422 
423  where
424 
425  high in [0, urange / (urngrange + 1)]
426 
427  and
428 
429  low in [0, urngrange].
430  */
431  __uctype __tmp; // wraparound control
432  while (__f != __t)
433  {
434  do
435  {
436  constexpr __uctype __uerngrange = __urngrange + 1;
437  __tmp = (__uerngrange * operator()
438  (__urng, param_type(0, __urange / __uerngrange)));
439  __ret = __tmp + (__uctype(__urng()) - __urngmin);
440  }
441  while (__ret > __urange || __ret < __tmp);
442  *__f++ = __ret;
443  }
444  }
445  else
446  while (__f != __t)
447  *__f++ = __uctype(__urng()) - __urngmin + __param.a();
448  }
449 
450  // operator!= and operator<< and operator>> are defined in <bits/random.h>
451 
452 _GLIBCXX_END_NAMESPACE_VERSION
453 } // namespace std
454 
455 #endif
std::uniform_int_distribution::param
void param(const param_type &__param)
Sets the parameter set of the distribution.
Definition: uniform_int_dist.h:169
std::uniform_int_distribution::uniform_int_distribution
uniform_int_distribution()
Constructs a uniform distribution object.
Definition: uniform_int_dist.h:124
std
ISO C++ entities toplevel namespace is std.
std::uniform_int_distribution::result_type
_IntType result_type
Definition: uniform_int_dist.h:79
std::uniform_int_distribution::operator==
friend bool operator==(const uniform_int_distribution &__d1, const uniform_int_distribution &__d2)
Return true if two uniform integer distributions have the same parameters.
Definition: uniform_int_dist.h:226
std::uniform_int_distribution::uniform_int_distribution
uniform_int_distribution(_IntType __a, _IntType __b=__gnu_cxx::__int_traits< _IntType >::__max)
Constructs a uniform distribution object.
Definition: uniform_int_dist.h:130
std::uniform_int_distribution::min
result_type min() const
Returns the inclusive lower bound of the distribution range.
Definition: uniform_int_dist.h:176
std::max
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:254
std::uniform_int_distribution
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
Definition: uniform_int_dist.h:77
std::uniform_int_distribution::param
param_type param() const
Returns the parameter set of the distribution.
Definition: uniform_int_dist.h:161
std::uniform_int_distribution::reset
void reset()
Resets the distribution state.
Definition: uniform_int_dist.h:147
std::uniform_int_distribution::max
result_type max() const
Returns the inclusive upper bound of the distribution range.
Definition: uniform_int_dist.h:183
numeric_traits.h
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
std::uniform_int_distribution::param_type
Definition: uniform_int_dist.h:86
std::uniform_int_distribution::operator()
result_type operator()(_UniformRandomBitGenerator &__urng)
Generating functions.
Definition: uniform_int_dist.h:191
__gnu_cxx::__int_traits
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
Definition: numeric_traits.h:136
concepts
std::is_integral
is_integral
Definition: type_traits:370
type_traits