Class AliasMethodDiscreteSampler.SmallTableAliasMethodDiscreteSampler

java.lang.Object

org.apache.commons.rng.sampling.distribution.AliasMethodDiscreteSampler

org.apache.commons.rng.sampling.distribution.AliasMethodDiscreteSampler.SmallTableAliasMethodDiscreteSampler

All Implemented Interfaces:

DiscreteSampler, SharedStateDiscreteSampler, SharedStateSampler<SharedStateDiscreteSampler>

Enclosing class:

AliasMethodDiscreteSampler

private static final class AliasMethodDiscreteSampler.SmallTableAliasMethodDiscreteSampler
extends AliasMethodDiscreteSampler

Sample from the computed tables exploiting the small power-of-two table size. This implements a variant of the optimised algorithm as per Vose (1991):

bits = obtained required number of random bits
v = (some of the bits) * constant1
j = (rest of the bits) * constant2
if v < prob[j] then
  return j
else
  return alias[j]

This is a variant because the bits are not multiplied by constants. In the case of v the constant is a scale that is pre-applied to the probability table. In the case of j the constant is not used to scale a deviate to an index; the index is from a power-of-2 range and so the bits are used directly.

This is implemented using up to 64 bits from the random generator. The index for the table is computed using a mask to extract up to 11 of the lower bits from an integer. The probability is computed using a second integer combined with the remaining bits to create 53-bits for the numerator of a fraction with denominator 2⁵³. This is only computed on demand.

Note: This supports a table size of up to 2^11, or 2048, exclusive. Any larger requires consuming more than 64-bits and the algorithm is not more efficient than the AliasMethodDiscreteSampler.

Sampling uses 1 or 2 calls to UniformRandomProvider.nextInt().

Since:

1.3

Field Summary

Fields

Modifier and Type	Field	Description
private final int	mask	The mask to isolate the lower bits.

Fields inherited from class AliasMethodDiscreteSampler

alias, probability, rng

Constructor Summary

Constructors

Constructor	Description
SmallTableAliasMethodDiscreteSampler(UniformRandomProvider rng, long[] probability, int[] alias)	Create a new instance.

Method Summary

Modifier and Type	Method	Description
int	sample()	Creates an int sample.
SharedStateDiscreteSampler	withUniformRandomProvider(UniformRandomProvider rng)	Create a new instance of the sampler with the same underlying state using the given uniform random provider as the source of randomness.

Methods inherited from class AliasMethodDiscreteSampler

of, of, toString

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface DiscreteSampler

samples, samples

Field Details

mask

private final int mask

The mask to isolate the lower bits.

Constructor Details

SmallTableAliasMethodDiscreteSampler

SmallTableAliasMethodDiscreteSampler(UniformRandomProvider rng,
 long[] probability,
 int[] alias)

Create a new instance.

Parameters:

rng - Generator of uniformly distributed random numbers.

probability - Probability table.

alias - Alias table.

Method Details

sample

public int sample()

Description copied from class: AliasMethodDiscreteSampler

Creates an int sample.

Specified by:

sample in interface DiscreteSampler

Overrides:

sample in class AliasMethodDiscreteSampler

Returns:

a sample.

withUniformRandomProvider

public SharedStateDiscreteSampler withUniformRandomProvider(UniformRandomProvider rng)

Create a new instance of the sampler with the same underlying state using the given uniform random provider as the source of randomness.

Specified by:

withUniformRandomProvider in interface SharedStateSampler<SharedStateDiscreteSampler>

Overrides:

withUniformRandomProvider in class AliasMethodDiscreteSampler

Parameters:

rng - Generator of uniformly distributed random numbers.

Returns:

the sampler