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:

D. E. Knuth and A. C. Yao, The Complexity of Nonuniform Random Number Generation, in "Algorithms and Complexity" (Academic Press, 1976), pp. 357–428.
J. Lumbroso, Optimal Discrete Uniform Generation from Coin Flips, and Applications, http://arxiv.org/abs/1304.1916 (2013)

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 = 2^bits. 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 + log₂σ. If Lumbroso's algorithm for sampling in [0,m) were used the log₂σ 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.

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.

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) + log_bm. 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 log₂m below. The red line shows what Lumbroso calls the "toll", the number of bits in excess of the entropy that are required for sampling.

Random bits to sample in [0,m) for b = 2

Template Parameters

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 = 2^bits.

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]	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.

Member Function Documentation

template<typename IntType = int, int bits = 1>

IntType RandomLib::UniformInteger< IntType, bits >::Min ( ) const

inline

Returns: the minimum of the current range.

Definition at line 99 of file UniformInteger.hpp.

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

template<typename IntType = int, int bits = 1>

IntType RandomLib::UniformInteger< IntType, bits >::Max ( ) const

inline

Returns: the maximum of the current range.

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

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() = 2^{Entropy() * 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

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

template<typename IntType = int, int bits = 1>

void RandomLib::UniformInteger< IntType, bits >::Add ( IntType c )

inline

Add a constant to the range

Parameters

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

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

Random the type of the random generator.

Parameters

[in,out]	r	a random generator.
[in]	p	the numerator of the fraction.
[in]	q	the 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

Random the type of the random generator.

Parameters

[in,out]	r	a random generator.
[in]	p	the numerator of the fraction.
[in]	q	the 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

Random the type of the random generator.

Parameters

[in,out]	r	a random generator.
[in]	p	the numerator of the fraction.
[in]	q	the 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

Random the type of the random generator.

Parameters

[in,out]	r	a random generator.
[in]	p	the numerator of the fraction.
[in]	q	the 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]	mmax	the largest m in the constructor.
[in]	qmax	the 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
	)

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:

UniformInteger.hpp

Public Member Functions

Static Public Member Functions

Related Functions

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

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