CodeCogs

Generates random numbers for a discrete distribution in constant time.

You're viewing an older version of this page (#465). View the current version.

Interface

#include <codecogs/statistics/distributions/discrete/discrete/randomfast.h>

using namespace Statistics::Distributions::Discrete::Discrete;

RandomFast(int n, T *p, bool normalise=true, double s = 0.7323) : Stats::Random::Mersenne(s), m_n(n), m_val(NULL), m_makecopy(false)
RandomFast(int n, T *prob, T *val, double s = 0.59012, bool makecopy = false) : Stats::Random::Mersenne(s), m_n(n), m_makecopy(makecopy)
~RandomFast()
inline unsigned int genIndex()
inline T genReal()
template <class T> void RandomFast<T>::init(int n, T *p, bool normalise)
int sampleFast(int N, double* p, bool normalise=true, double seed=0.1234)

Overview

This random generator is an alternative of RandomSample, and is optimised for discrete sampling of large distribution when you require constant time random number generation. However, due to rounding errors with this approach, if your distribution is very large, then you should use RandomSample for more accuracy.

This statistical distribution can take only discrete values, with a probability function

$P(x_k) \qquad k = 1, 2, \ldots, n$

(1)

that has a distribution function

$D(x_n) = \sum_{k = 1} ^ n P(x_k)$

(2)

and population mean

$\mu = \frac{1}{n} \sum_{k = 1} ^ n P(x_k)$

(3)

Example 1

The following example displays 20 random floating point numbers from a discrete distribution. It uses two different generators to achieve this. The first generator uses a particular value to initialize the seed, while the second one is using the system timer. Notice that it was necessary to divide the timer with the MERSENNEDIV value in order to keep the seed in the (0, 1) interval. Since the seed of the first generator is never changed, the first 10 numbers will always remain the same. However since the second generator is initialized via the system timer, the next 10 numbers will obviously vary with each execution of the program, Also notice the declaration of the probability array P and value array V. They are used as constructor arguments when declaring the generators to specify the probabilities P[i] associated to each value V[i] in the values table. Always make sure that the components of P sum up to 1.

#include <iostream.h>
#include <conio.h>
#include <time.h>
	
#include <codecogs/stats/dists/discrete/discrete/randomfast.h>
	
	void main() {
		
		double P[4] = {  0.1,  0.1,  0.2,   0.6 };
		double V[4] = { 3.14, 2.71, 0.33, 12.57 };
		
		Stats::Dist::Discrete::Discrete::RandomFast A(4, P, V, false, 0.762);
		Stats::Dist::Discrete::Discrete::RandomFast B(4, P, false, time(0) / MERSENNEDIV);
		
		for (int i = 0; i < 10; ++i)
			cout << A.genReal() << " ";
		cout << endl;
		getch();
		
		cout << endl;
		
		for (int i = 0; i < 10; ++i)
			cout << B.genReal() << " ";
		cout << endl
			getch();
		
	}

Below you will find 10 numbers corresponding to the output of the first generator :

12.57 0.33 2.71 0.33 12.57 3.14 12.57 12.57 0.33 12.57

Speed

The average running time for generating 100,000,000 random numbers using this class on a 750MHz microprocessor is 8 seconds.

Due to rounding errors, this class is not suited for use with very large number of input probability values, i.e. when n exceeds 10,000 values, the accuracy of the random numbers deteriorates.

References

MathWorld, http://mathworld.wolfram.com/DiscreteDistribution.html
The Newran03 random number generator library of Robert Davies, http://www.robertnz.net/nr03doc.htm

Members of RandomFast

CLASS METHOD

RandomFast

Constructor that sets up the class variables and initializes the associated random number generator with the given seed.

Parameters

Default value = 0.7323

normalise

Normalises the probabilities defined in p (Default=true)

The probability array of length n (should sum up to 1)

The number of values

CLASS METHOD

RandomFast

Constructor that sets up the class variables and initializes the associated random number generator with the given seed.

Parameters

makecopy

Default value = false

Default value = 0.59012

val

The set of values the generator may return

prob

The probability array of length n

The number of values

CLASS METHOD

RandomFast

Class destructor.

CLASS METHOD

genIndex

Returns a random deviate as an index into the discrete input rates, in range 0 to (N-1)

CLASS METHOD

genReal

Generates a random deviate from the discrete distribution.

CLASS METHOD

init

Parameters

normalise

Default Value = true

CLASS METHOD

sampleFast

This function is a simple wrapper around the randomfast class provided in this module. It uses a static to keep a single instance of this class, so that each call to this function returns a new random number. As a result this function is not necessarily thread safe, in the sense that with identical initial seed, the sequence of random numbers may differ on a multitasking or multi threaded system.

The seed is only set on the first call to this function. Thereafter this parameter is ignored. If you do no want to set the seed, then we suggest you use the system clock the first time you call this function, i.e.

#include <time.h>
...
sample(N,  p, time(0) / MERSENNEDIV);

If you require more advance behaviour, we strongly recommend that directly use the underlying class randomsample that is provided with this module.

Parameters

the number of rates in custom distribution

an array of N rates that define the occurrence rate of each event.

normalise

Default Value = true

seed

sets the initial seed for the random generator. Only used in the first call to this function

Returns

this function returns an index in the range 0 to (N-1), which act as an index into the array define in p.