distributions.h (18526B)
1 // Copyright 2017 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // ----------------------------------------------------------------------------- 16 // File: distributions.h 17 // ----------------------------------------------------------------------------- 18 // 19 // This header defines functions representing distributions, which you use in 20 // combination with an Abseil random bit generator to produce random values 21 // according to the rules of that distribution. 22 // 23 // The Abseil random library defines the following distributions within this 24 // file: 25 // 26 // * `absl::Uniform` for uniform (constant) distributions having constant 27 // probability 28 // * `absl::Bernoulli` for discrete distributions having exactly two outcomes 29 // * `absl::Beta` for continuous distributions parameterized through two 30 // free parameters 31 // * `absl::Exponential` for discrete distributions of events occurring 32 // continuously and independently at a constant average rate 33 // * `absl::Gaussian` (also known as "normal distributions") for continuous 34 // distributions using an associated quadratic function 35 // * `absl::LogUniform` for discrete distributions where the log to the given 36 // base of all values is uniform 37 // * `absl::Poisson` for discrete probability distributions that express the 38 // probability of a given number of events occurring within a fixed interval 39 // * `absl::Zipf` for discrete probability distributions commonly used for 40 // modelling of rare events 41 // 42 // Prefer use of these distribution function classes over manual construction of 43 // your own distribution classes, as it allows library maintainers greater 44 // flexibility to change the underlying implementation in the future. 45 46 #ifndef ABSL_RANDOM_DISTRIBUTIONS_H_ 47 #define ABSL_RANDOM_DISTRIBUTIONS_H_ 48 49 #include <limits> 50 #include <type_traits> 51 52 #include "absl/base/config.h" 53 #include "absl/meta/type_traits.h" 54 #include "absl/random/bernoulli_distribution.h" 55 #include "absl/random/beta_distribution.h" 56 #include "absl/random/exponential_distribution.h" 57 #include "absl/random/gaussian_distribution.h" 58 #include "absl/random/internal/distribution_caller.h" // IWYU pragma: export 59 #include "absl/random/internal/traits.h" 60 #include "absl/random/internal/uniform_helper.h" // IWYU pragma: export 61 #include "absl/random/log_uniform_int_distribution.h" 62 #include "absl/random/poisson_distribution.h" 63 #include "absl/random/uniform_int_distribution.h" // IWYU pragma: export 64 #include "absl/random/uniform_real_distribution.h" // IWYU pragma: export 65 #include "absl/random/zipf_distribution.h" 66 67 namespace absl { 68 ABSL_NAMESPACE_BEGIN 69 70 inline constexpr IntervalClosedClosedTag IntervalClosedClosed = {}; 71 inline constexpr IntervalClosedClosedTag IntervalClosed = {}; 72 inline constexpr IntervalClosedOpenTag IntervalClosedOpen = {}; 73 inline constexpr IntervalOpenOpenTag IntervalOpenOpen = {}; 74 inline constexpr IntervalOpenOpenTag IntervalOpen = {}; 75 inline constexpr IntervalOpenClosedTag IntervalOpenClosed = {}; 76 77 // ----------------------------------------------------------------------------- 78 // absl::Uniform<T>(tag, bitgen, lo, hi) 79 // ----------------------------------------------------------------------------- 80 // 81 // `absl::Uniform()` produces random values of type `T` uniformly distributed in 82 // a defined interval {lo, hi}. The interval `tag` defines the type of interval 83 // which should be one of the following possible values: 84 // 85 // * `absl::IntervalOpenOpen` 86 // * `absl::IntervalOpenClosed` 87 // * `absl::IntervalClosedOpen` 88 // * `absl::IntervalClosedClosed` 89 // 90 // where "open" refers to an exclusive value (excluded) from the output, while 91 // "closed" refers to an inclusive value (included) from the output. 92 // 93 // In the absence of an explicit return type `T`, `absl::Uniform()` will deduce 94 // the return type based on the provided endpoint arguments {A lo, B hi}. 95 // Given these endpoints, one of {A, B} will be chosen as the return type, if 96 // a type can be implicitly converted into the other in a lossless way. The 97 // lack of any such implicit conversion between {A, B} will produce a 98 // compile-time error 99 // 100 // See https://en.wikipedia.org/wiki/Uniform_distribution_(continuous) 101 // 102 // Example: 103 // 104 // absl::BitGen bitgen; 105 // 106 // // Produce a random float value between 0.0 and 1.0, inclusive 107 // auto x = absl::Uniform(absl::IntervalClosedClosed, bitgen, 0.0f, 1.0f); 108 // 109 // // The most common interval of `absl::IntervalClosedOpen` is available by 110 // // default: 111 // 112 // auto x = absl::Uniform(bitgen, 0.0f, 1.0f); 113 // 114 // // Return-types are typically inferred from the arguments, however callers 115 // // can optionally provide an explicit return-type to the template. 116 // 117 // auto x = absl::Uniform<float>(bitgen, 0, 1); 118 // 119 template <typename R = void, typename TagType, typename URBG> 120 typename absl::enable_if_t<!std::is_same<R, void>::value, R> // 121 Uniform(TagType tag, 122 URBG&& urbg, // NOLINT(runtime/references) 123 R lo, R hi) { 124 using gen_t = absl::decay_t<URBG>; 125 using distribution_t = random_internal::UniformDistributionWrapper<R>; 126 127 auto a = random_internal::uniform_lower_bound(tag, lo, hi); 128 auto b = random_internal::uniform_upper_bound(tag, lo, hi); 129 if (!random_internal::is_uniform_range_valid(a, b)) return lo; 130 131 return random_internal::DistributionCaller<gen_t>::template Call< 132 distribution_t>(&urbg, tag, lo, hi); 133 } 134 135 // absl::Uniform<T>(bitgen, lo, hi) 136 // 137 // Overload of `Uniform()` using the default closed-open interval of [lo, hi), 138 // and returning values of type `T` 139 template <typename R = void, typename URBG> 140 typename absl::enable_if_t<!std::is_same<R, void>::value, R> // 141 Uniform(URBG&& urbg, // NOLINT(runtime/references) 142 R lo, R hi) { 143 using gen_t = absl::decay_t<URBG>; 144 using distribution_t = random_internal::UniformDistributionWrapper<R>; 145 constexpr auto tag = absl::IntervalClosedOpen; 146 147 auto a = random_internal::uniform_lower_bound(tag, lo, hi); 148 auto b = random_internal::uniform_upper_bound(tag, lo, hi); 149 if (!random_internal::is_uniform_range_valid(a, b)) return lo; 150 151 return random_internal::DistributionCaller<gen_t>::template Call< 152 distribution_t>(&urbg, lo, hi); 153 } 154 155 // absl::Uniform(tag, bitgen, lo, hi) 156 // 157 // Overload of `Uniform()` using different (but compatible) lo, hi types. Note 158 // that a compile-error will result if the return type cannot be deduced 159 // correctly from the passed types. 160 template <typename R = void, typename TagType, typename URBG, typename A, 161 typename B> 162 typename absl::enable_if_t<std::is_same<R, void>::value, 163 random_internal::uniform_inferred_return_t<A, B>> 164 Uniform(TagType tag, 165 URBG&& urbg, // NOLINT(runtime/references) 166 A lo, B hi) { 167 using gen_t = absl::decay_t<URBG>; 168 using return_t = typename random_internal::uniform_inferred_return_t<A, B>; 169 using distribution_t = random_internal::UniformDistributionWrapper<return_t>; 170 171 auto a = random_internal::uniform_lower_bound<return_t>(tag, lo, hi); 172 auto b = random_internal::uniform_upper_bound<return_t>(tag, lo, hi); 173 if (!random_internal::is_uniform_range_valid(a, b)) return lo; 174 175 return random_internal::DistributionCaller<gen_t>::template Call< 176 distribution_t>(&urbg, tag, static_cast<return_t>(lo), 177 static_cast<return_t>(hi)); 178 } 179 180 // absl::Uniform(bitgen, lo, hi) 181 // 182 // Overload of `Uniform()` using different (but compatible) lo, hi types and the 183 // default closed-open interval of [lo, hi). Note that a compile-error will 184 // result if the return type cannot be deduced correctly from the passed types. 185 template <typename R = void, typename URBG, typename A, typename B> 186 typename absl::enable_if_t<std::is_same<R, void>::value, 187 random_internal::uniform_inferred_return_t<A, B>> 188 Uniform(URBG&& urbg, // NOLINT(runtime/references) 189 A lo, B hi) { 190 using gen_t = absl::decay_t<URBG>; 191 using return_t = typename random_internal::uniform_inferred_return_t<A, B>; 192 using distribution_t = random_internal::UniformDistributionWrapper<return_t>; 193 194 constexpr auto tag = absl::IntervalClosedOpen; 195 auto a = random_internal::uniform_lower_bound<return_t>(tag, lo, hi); 196 auto b = random_internal::uniform_upper_bound<return_t>(tag, lo, hi); 197 if (!random_internal::is_uniform_range_valid(a, b)) return lo; 198 199 return random_internal::DistributionCaller<gen_t>::template Call< 200 distribution_t>(&urbg, static_cast<return_t>(lo), 201 static_cast<return_t>(hi)); 202 } 203 204 // absl::Uniform<unsigned T>(bitgen) 205 // 206 // Overload of Uniform() using the minimum and maximum values of a given type 207 // `T` (which must be unsigned), returning a value of type `unsigned T` 208 template <typename R, typename URBG> 209 typename absl::enable_if_t<!std::numeric_limits<R>::is_signed, R> // 210 Uniform(URBG&& urbg) { // NOLINT(runtime/references) 211 using gen_t = absl::decay_t<URBG>; 212 using distribution_t = random_internal::UniformDistributionWrapper<R>; 213 214 return random_internal::DistributionCaller<gen_t>::template Call< 215 distribution_t>(&urbg); 216 } 217 218 // ----------------------------------------------------------------------------- 219 // absl::Bernoulli(bitgen, p) 220 // ----------------------------------------------------------------------------- 221 // 222 // `absl::Bernoulli` produces a random boolean value, with probability `p` 223 // (where 0.0 <= p <= 1.0) equaling `true`. 224 // 225 // Prefer `absl::Bernoulli` to produce boolean values over other alternatives 226 // such as comparing an `absl::Uniform()` value to a specific output. 227 // 228 // See https://en.wikipedia.org/wiki/Bernoulli_distribution 229 // 230 // Example: 231 // 232 // absl::BitGen bitgen; 233 // ... 234 // if (absl::Bernoulli(bitgen, 1.0/3721.0)) { 235 // std::cout << "Asteroid field navigation successful."; 236 // } 237 // 238 template <typename URBG> 239 bool Bernoulli(URBG&& urbg, // NOLINT(runtime/references) 240 double p) { 241 using gen_t = absl::decay_t<URBG>; 242 using distribution_t = absl::bernoulli_distribution; 243 244 return random_internal::DistributionCaller<gen_t>::template Call< 245 distribution_t>(&urbg, p); 246 } 247 248 // ----------------------------------------------------------------------------- 249 // absl::Beta<T>(bitgen, alpha, beta) 250 // ----------------------------------------------------------------------------- 251 // 252 // `absl::Beta` produces a floating point number distributed in the closed 253 // interval [0,1] and parameterized by two values `alpha` and `beta` as per a 254 // Beta distribution. `T` must be a floating point type, but may be inferred 255 // from the types of `alpha` and `beta`. 256 // 257 // See https://en.wikipedia.org/wiki/Beta_distribution. 258 // 259 // Example: 260 // 261 // absl::BitGen bitgen; 262 // ... 263 // double sample = absl::Beta(bitgen, 3.0, 2.0); 264 // 265 template <typename RealType, typename URBG> 266 RealType Beta(URBG&& urbg, // NOLINT(runtime/references) 267 RealType alpha, RealType beta) { 268 static_assert( 269 std::is_floating_point<RealType>::value, 270 "Template-argument 'RealType' must be a floating-point type, in " 271 "absl::Beta<RealType, URBG>(...)"); 272 273 using gen_t = absl::decay_t<URBG>; 274 using distribution_t = typename absl::beta_distribution<RealType>; 275 276 return random_internal::DistributionCaller<gen_t>::template Call< 277 distribution_t>(&urbg, alpha, beta); 278 } 279 280 // ----------------------------------------------------------------------------- 281 // absl::Exponential<T>(bitgen, lambda = 1) 282 // ----------------------------------------------------------------------------- 283 // 284 // `absl::Exponential` produces a floating point number representing the 285 // distance (time) between two consecutive events in a point process of events 286 // occurring continuously and independently at a constant average rate. `T` must 287 // be a floating point type, but may be inferred from the type of `lambda`. 288 // 289 // See https://en.wikipedia.org/wiki/Exponential_distribution. 290 // 291 // Example: 292 // 293 // absl::BitGen bitgen; 294 // ... 295 // double call_length = absl::Exponential(bitgen, 7.0); 296 // 297 template <typename RealType, typename URBG> 298 RealType Exponential(URBG&& urbg, // NOLINT(runtime/references) 299 RealType lambda = 1) { 300 static_assert( 301 std::is_floating_point<RealType>::value, 302 "Template-argument 'RealType' must be a floating-point type, in " 303 "absl::Exponential<RealType, URBG>(...)"); 304 305 using gen_t = absl::decay_t<URBG>; 306 using distribution_t = typename absl::exponential_distribution<RealType>; 307 308 return random_internal::DistributionCaller<gen_t>::template Call< 309 distribution_t>(&urbg, lambda); 310 } 311 312 // ----------------------------------------------------------------------------- 313 // absl::Gaussian<T>(bitgen, mean = 0, stddev = 1) 314 // ----------------------------------------------------------------------------- 315 // 316 // `absl::Gaussian` produces a floating point number selected from the Gaussian 317 // (ie. "Normal") distribution. `T` must be a floating point type, but may be 318 // inferred from the types of `mean` and `stddev`. 319 // 320 // See https://en.wikipedia.org/wiki/Normal_distribution 321 // 322 // Example: 323 // 324 // absl::BitGen bitgen; 325 // ... 326 // double giraffe_height = absl::Gaussian(bitgen, 16.3, 3.3); 327 // 328 template <typename RealType, typename URBG> 329 RealType Gaussian(URBG&& urbg, // NOLINT(runtime/references) 330 RealType mean = 0, RealType stddev = 1) { 331 static_assert( 332 std::is_floating_point<RealType>::value, 333 "Template-argument 'RealType' must be a floating-point type, in " 334 "absl::Gaussian<RealType, URBG>(...)"); 335 336 using gen_t = absl::decay_t<URBG>; 337 using distribution_t = typename absl::gaussian_distribution<RealType>; 338 339 return random_internal::DistributionCaller<gen_t>::template Call< 340 distribution_t>(&urbg, mean, stddev); 341 } 342 343 // ----------------------------------------------------------------------------- 344 // absl::LogUniform<T>(bitgen, lo, hi, base = 2) 345 // ----------------------------------------------------------------------------- 346 // 347 // `absl::LogUniform` produces random values distributed where the log to a 348 // given base of all values is uniform in a closed interval [lo, hi]. `T` must 349 // be an integral type, but may be inferred from the types of `lo` and `hi`. 350 // 351 // I.e., `LogUniform(0, n, b)` is uniformly distributed across buckets 352 // [0], [1, b-1], [b, b^2-1] .. [b^(k-1), (b^k)-1] .. [b^floor(log(n, b)), n] 353 // and is uniformly distributed within each bucket. 354 // 355 // The resulting probability density is inversely related to bucket size, though 356 // values in the final bucket may be more likely than previous values. (In the 357 // extreme case where n = b^i the final value will be tied with zero as the most 358 // probable result. 359 // 360 // If `lo` is nonzero then this distribution is shifted to the desired interval, 361 // so LogUniform(lo, hi, b) is equivalent to LogUniform(0, hi-lo, b)+lo. 362 // 363 // See https://en.wikipedia.org/wiki/Reciprocal_distribution 364 // 365 // Example: 366 // 367 // absl::BitGen bitgen; 368 // ... 369 // int v = absl::LogUniform(bitgen, 0, 1000); 370 // 371 template <typename IntType, typename URBG> 372 IntType LogUniform(URBG&& urbg, // NOLINT(runtime/references) 373 IntType lo, IntType hi, IntType base = 2) { 374 static_assert(random_internal::IsIntegral<IntType>::value, 375 "Template-argument 'IntType' must be an integral type, in " 376 "absl::LogUniform<IntType, URBG>(...)"); 377 378 using gen_t = absl::decay_t<URBG>; 379 using distribution_t = typename absl::log_uniform_int_distribution<IntType>; 380 381 return random_internal::DistributionCaller<gen_t>::template Call< 382 distribution_t>(&urbg, lo, hi, base); 383 } 384 385 // ----------------------------------------------------------------------------- 386 // absl::Poisson<T>(bitgen, mean = 1) 387 // ----------------------------------------------------------------------------- 388 // 389 // `absl::Poisson` produces discrete probabilities for a given number of events 390 // occurring within a fixed interval within the closed interval [0, max]. `T` 391 // must be an integral type. 392 // 393 // See https://en.wikipedia.org/wiki/Poisson_distribution 394 // 395 // Example: 396 // 397 // absl::BitGen bitgen; 398 // ... 399 // int requests_per_minute = absl::Poisson<int>(bitgen, 3.2); 400 // 401 template <typename IntType, typename URBG> 402 IntType Poisson(URBG&& urbg, // NOLINT(runtime/references) 403 double mean = 1.0) { 404 static_assert(random_internal::IsIntegral<IntType>::value, 405 "Template-argument 'IntType' must be an integral type, in " 406 "absl::Poisson<IntType, URBG>(...)"); 407 408 using gen_t = absl::decay_t<URBG>; 409 using distribution_t = typename absl::poisson_distribution<IntType>; 410 411 return random_internal::DistributionCaller<gen_t>::template Call< 412 distribution_t>(&urbg, mean); 413 } 414 415 // ----------------------------------------------------------------------------- 416 // absl::Zipf<T>(bitgen, hi = max, q = 2, v = 1) 417 // ----------------------------------------------------------------------------- 418 // 419 // `absl::Zipf` produces discrete probabilities commonly used for modelling of 420 // rare events over the closed interval [0, hi]. The parameters `v` and `q` 421 // determine the skew of the distribution. `T` must be an integral type, but 422 // may be inferred from the type of `hi`. 423 // 424 // See http://mathworld.wolfram.com/ZipfDistribution.html 425 // 426 // Example: 427 // 428 // absl::BitGen bitgen; 429 // ... 430 // int term_rank = absl::Zipf<int>(bitgen); 431 // 432 template <typename IntType, typename URBG> 433 IntType Zipf(URBG&& urbg, // NOLINT(runtime/references) 434 IntType hi = (std::numeric_limits<IntType>::max)(), double q = 2.0, 435 double v = 1.0) { 436 static_assert(random_internal::IsIntegral<IntType>::value, 437 "Template-argument 'IntType' must be an integral type, in " 438 "absl::Zipf<IntType, URBG>(...)"); 439 440 using gen_t = absl::decay_t<URBG>; 441 using distribution_t = typename absl::zipf_distribution<IntType>; 442 443 return random_internal::DistributionCaller<gen_t>::template Call< 444 distribution_t>(&urbg, hi, q, v); 445 } 446 447 ABSL_NAMESPACE_END 448 } // namespace absl 449 450 #endif // ABSL_RANDOM_DISTRIBUTIONS_H_