RandomLib
1.10
|
The partial uniform integer distribution. More...
#include <RandomLib/UniformInteger.hpp>
Public Member Functions | |
template<class Random > | |
UniformInteger (Random &r, IntType m, bool flip=false) | |
IntType | Min () const |
IntType | Max () const |
IntType | Entropy () const |
template<class Random > | |
IntType | operator() (Random &r) |
void | Negate () |
void | Add (IntType c) |
template<class Random > | |
bool | LessThan (Random &r, IntType p, IntType q) |
template<class Random > | |
bool | LessThanEqual (Random &r, IntType p, IntType q) |
template<class Random > | |
bool | GreaterThan (Random &r, IntType p, IntType q) |
template<class Random > | |
bool | GreaterThanEqual (Random &r, IntType p, IntType q) |
Static Public Member Functions | |
static bool | Check (IntType mmax, IntType qmax) |
Related Functions | |
(Note that these are not member functions.) | |
template<typename IntType , int bits> | |
std::ostream & | operator<< (std::ostream &os, const UniformInteger< IntType, bits > &u) |
The partial uniform integer distribution.
A class to sample in [0, m). For background, see:
Lumbroso's algorithm is a realization of the Knuth-Yao method for the case of uniform probabilities. This class generalizes the method to accept random digits in a base, b = 2bits. An important additional feature is that only sufficient random digits are drawn to narrow the allowed range to a power of b. Thus after UniformInteger<int,1> u(r,5)
, u represents
range prob [0,4) 8/15 [0,2) 2/15 [2,4) 2/15 4 1/5
u.Min()
and u.Max()
give the extent of the closed range. The number of additional random digits needed to fix the value is given by u.Entropy()
. The comparison operations may require additional digits to be drawn and so the range might be narrowed down. If you need a definite value then use u(r)
.
The DiscreteNormalAlt class uses UniformInteger to achieve an asymptotically ideal scaling wherein the number of random bits required per sample is constant + log2σ. If Lumbroso's algorithm for sampling in [0,m) were used the log2σ term would be multiplied by about 1.4.
It is instructive to look at the Knuth-Yao discrete distribution generating (DDG) tree for the case m = 5 (the binary expansion of 1/5 is 0.00110011...); Lumbroso's algorithm implements this tree.
UniformInteger collapses all of the full subtrees above to their parent nodes to yield this tree where now some of the outcomes are ranges.
Averaging over many samples, the maximum number of digits required to construct a UniformInteger, i.e., invoking UniformInteger(r,m)
, is (2b − 1)/(b − 1). (Note that this does not increase as m increases.) The maximum number of digits required to sample specific integers, i.e., invoking UniformInteger(r,m)(r)
, is b/(b − 1) + logbm. The worst cases are when m is slightly more than a power of b.
The number of random bits required for sampling is shown as a function of the fractional part of log2m below. The red line shows what Lumbroso calls the "toll", the number of bits in excess of the entropy that are required for sampling.
IntType | the type of the integer (must be signed). |
bits | the number of bits in each digit used for sampling; the base for sampling is b = 2bits. |
Definition at line 80 of file UniformInteger.hpp.
RandomLib::UniformInteger< IntType, bits >::UniformInteger | ( | Random & | r, |
IntType | m, | ||
bool | flip = false |
||
) |
Constructor creating a partially sampled integer in [0, m)
[in] | r | random object. |
[in] | m | constructed object represents an integer in [0, m). |
[in] | flip | if true, rearrange the ranges so that the widest ones are at near the upper end of [0, m) (default false). |
The samples enough random digits to obtain a uniform range whose size is a power of the base. The range can subsequently be narrowed by sampling additional digits.
Definition at line 205 of file UniformInteger.hpp.
References STATIC_ASSERT.
|
inline |
Definition at line 99 of file UniformInteger.hpp.
Referenced by coverage32(), coverage64(), RandomLib::UniformInteger< IntType, bits >::LessThan(), and RandomLib::UniformInteger< IntType, bits >::operator<<().
|
inline |
Definition at line 103 of file UniformInteger.hpp.
Referenced by coverage32(), coverage64(), RandomLib::UniformInteger< IntType, bits >::LessThan(), RandomLib::UniformInteger< IntType, bits >::Negate(), and RandomLib::UniformInteger< IntType, bits >::operator<<().
|
inline |
Max() + 1 - Min() = 2Entropy() * bits.
Definition at line 109 of file UniformInteger.hpp.
Referenced by coverage32(), coverage64(), main(), and RandomLib::UniformInteger< IntType, bits >::operator<<().
|
inline |
Sample until the entropy vanishes, i.e., Min() = Max().
Definition at line 115 of file UniformInteger.hpp.
|
inline |
Negate the range, [Min(), Max()] → [−Max(), −Min()].
Definition at line 120 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::Max().
Referenced by coverage32(), coverage64(), and RandomLib::DiscreteNormalAlt< IntType, bits >::operator()().
|
inline |
Add a constant to the range
[in] | c | the constant to be added. |
[Min(), Max()] → [Min() + c, Max() + c].
Definition at line 128 of file UniformInteger.hpp.
Referenced by coverage32(), coverage64(), and RandomLib::DiscreteNormalAlt< IntType, bits >::operator()().
|
inline |
Compare with a fraction, *this < p/q
Random | the type of the random generator. |
[in,out] | r | a random generator. |
[in] | p | the numerator of the fraction. |
[in] | q | the denominator of the fraction (require q > 0). |
Definition at line 139 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::Max(), and RandomLib::UniformInteger< IntType, bits >::Min().
Referenced by coverage32(), coverage64(), RandomLib::UniformInteger< IntType, bits >::GreaterThanEqual(), RandomLib::UniformInteger< IntType, bits >::LessThanEqual(), and RandomLib::DiscreteNormalAlt< IntType, bits >::operator()().
|
inline |
Compare with a fraction, *this ≤ p/q
Random | the type of the random generator. |
[in,out] | r | a random generator. |
[in] | p | the numerator of the fraction. |
[in] | q | the denominator of the fraction (require q > 0). |
Definition at line 156 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::LessThan().
Referenced by coverage32(), coverage64(), and RandomLib::UniformInteger< IntType, bits >::GreaterThan().
|
inline |
Compare with a fraction, *this > p/q
Random | the type of the random generator. |
[in,out] | r | a random generator. |
[in] | p | the numerator of the fraction. |
[in] | q | the denominator of the fraction (require q > 0). |
Definition at line 168 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::LessThanEqual().
Referenced by coverage32(), coverage64(), and RandomLib::DiscreteNormalAlt< IntType, bits >::operator()().
|
inline |
Compare with a fraction, *this ≥ p/q
Random | the type of the random generator. |
[in,out] | r | a random generator. |
[in] | p | the numerator of the fraction. |
[in] | q | the denominator of the fraction (require q > 0). |
Definition at line 180 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::LessThan().
Referenced by coverage32(), coverage64(), and RandomLib::RandomNumber< bits >::LessThan().
|
inlinestatic |
Check that overflow will not happen.
[in] | mmax | the largest m in the constructor. |
[in] | qmax | the largest q in LessThan(). |
It is important that this check be carried out. If overflow occurs, incorrect results are obtained and the constructor may never terminate.
Definition at line 192 of file UniformInteger.hpp.
|
related |
Print a UniformInteger. Format is [min,max] unless the entropy is zero, in which case it's val.
Definition at line 242 of file UniformInteger.hpp.
References RandomLib::UniformInteger< IntType, bits >::Entropy(), RandomLib::UniformInteger< IntType, bits >::Max(), and RandomLib::UniformInteger< IntType, bits >::Min().