Package org.apache.commons.rng.sampling.distribution

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

Field Summary

Fields

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

Fields inherited from class org.apache.commons.rng.sampling.distribution.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 org.apache.commons.rng.sampling.distribution.AliasMethodDiscreteSampler

of, of, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.apache.commons.rng.sampling.distribution.DiscreteSampler

samples, samples

Field Detail

mask

private final int mask

The mask to isolate the lower bits.

Constructor Detail

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 Detail

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