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