RandomLib  1.10
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Macros Pages
Public Member Functions | Static Public Member Functions | Related Functions | List of all members
RandomLib::UniformInteger< IntType, bits > Class Template Reference

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)
 

Detailed Description

template<typename IntType = int, int bits = 1>
class RandomLib::UniformInteger< IntType, bits >

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.

ky-5.png
Knuth-Yao for m = 5

UniformInteger collapses all of the full subtrees above to their parent nodes to yield this tree where now some of the outcomes are ranges.

ky-5-collapse.png
Collapsed Knuth-Yao for m = 5

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.

uniform-bits.png
Random bits to sample in [0,m) for b = 2
Template Parameters
IntTypethe type of the integer (must be signed).
bitsthe number of bits in each digit used for sampling; the base for sampling is b = 2bits.

Definition at line 80 of file UniformInteger.hpp.

Constructor & Destructor Documentation

template<typename IntType , int bits>
template<class Random >
RandomLib::UniformInteger< IntType, bits >::UniformInteger ( Random r,
IntType  m,
bool  flip = false 
)

Constructor creating a partially sampled integer in [0, m)

Parameters
[in]rrandom object.
[in]mconstructed object represents an integer in [0, m).
[in]flipif 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.

Member Function Documentation

template<typename IntType = int, int bits = 1>
IntType RandomLib::UniformInteger< IntType, bits >::Min ( ) const
inline
template<typename IntType = int, int bits = 1>
IntType RandomLib::UniformInteger< IntType, bits >::Max ( ) const
inline
template<typename IntType = int, int bits = 1>
IntType RandomLib::UniformInteger< IntType, bits >::Entropy ( ) const
inline
Returns
the entropy of the current range (in units of random digits).

Max() + 1 - Min() = 2Entropy() * bits.

Definition at line 109 of file UniformInteger.hpp.

Referenced by coverage32(), coverage64(), main(), and RandomLib::UniformInteger< IntType, bits >::operator<<().

template<typename IntType = int, int bits = 1>
template<class Random >
IntType RandomLib::UniformInteger< IntType, bits >::operator() ( Random r)
inline

Sample until the entropy vanishes, i.e., Min() = Max().

Returns
the resulting integer sample.

Definition at line 115 of file UniformInteger.hpp.

template<typename IntType = int, int bits = 1>
void RandomLib::UniformInteger< IntType, bits >::Negate ( )
inline
template<typename IntType = int, int bits = 1>
void RandomLib::UniformInteger< IntType, bits >::Add ( IntType  c)
inline

Add a constant to the range

Parameters
[in]cthe 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()().

template<typename IntType = int, int bits = 1>
template<class Random >
bool RandomLib::UniformInteger< IntType, bits >::LessThan ( Random r,
IntType  p,
IntType  q 
)
inline

Compare with a fraction, *this < p/q

Template Parameters
Randomthe type of the random generator.
Parameters
[in,out]ra random generator.
[in]pthe numerator of the fraction.
[in]qthe denominator of the fraction (require q > 0).
Returns
true if *this < p/q.

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()().

template<typename IntType = int, int bits = 1>
template<class Random >
bool RandomLib::UniformInteger< IntType, bits >::LessThanEqual ( Random r,
IntType  p,
IntType  q 
)
inline

Compare with a fraction, *this ≤ p/q

Template Parameters
Randomthe type of the random generator.
Parameters
[in,out]ra random generator.
[in]pthe numerator of the fraction.
[in]qthe denominator of the fraction (require q > 0).
Returns
true if *this ≤ p/q.

Definition at line 156 of file UniformInteger.hpp.

References RandomLib::UniformInteger< IntType, bits >::LessThan().

Referenced by coverage32(), coverage64(), and RandomLib::UniformInteger< IntType, bits >::GreaterThan().

template<typename IntType = int, int bits = 1>
template<class Random >
bool RandomLib::UniformInteger< IntType, bits >::GreaterThan ( Random r,
IntType  p,
IntType  q 
)
inline

Compare with a fraction, *this > p/q

Template Parameters
Randomthe type of the random generator.
Parameters
[in,out]ra random generator.
[in]pthe numerator of the fraction.
[in]qthe denominator of the fraction (require q > 0).
Returns
true if *this > p/q.

Definition at line 168 of file UniformInteger.hpp.

References RandomLib::UniformInteger< IntType, bits >::LessThanEqual().

Referenced by coverage32(), coverage64(), and RandomLib::DiscreteNormalAlt< IntType, bits >::operator()().

template<typename IntType = int, int bits = 1>
template<class Random >
bool RandomLib::UniformInteger< IntType, bits >::GreaterThanEqual ( Random r,
IntType  p,
IntType  q 
)
inline

Compare with a fraction, *this ≥ p/q

Template Parameters
Randomthe type of the random generator.
Parameters
[in,out]ra random generator.
[in]pthe numerator of the fraction.
[in]qthe denominator of the fraction (require q > 0).
Returns
true if *this ≥ p/q.

Definition at line 180 of file UniformInteger.hpp.

References RandomLib::UniformInteger< IntType, bits >::LessThan().

Referenced by coverage32(), coverage64(), and RandomLib::RandomNumber< bits >::LessThan().

template<typename IntType = int, int bits = 1>
static bool RandomLib::UniformInteger< IntType, bits >::Check ( IntType  mmax,
IntType  qmax 
)
inlinestatic

Check that overflow will not happen.

Parameters
[in]mmaxthe largest m in the constructor.
[in]qmaxthe largest q in LessThan().
Returns
true if overflow will not happen.

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.

Friends And Related Function Documentation

template<typename IntType , int bits>
std::ostream & operator<< ( std::ostream &  os,
const UniformInteger< IntType, bits > &  u 
)
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().


The documentation for this class was generated from the following file: