Class AliasMethodDiscreteSampler.SmallTableAliasMethodDiscreteSampler

  • All Implemented Interfaces:
    DiscreteSampler, SharedStateDiscreteSampler, SharedStateSampler<SharedStateDiscreteSampler>
    Enclosing class:
    AliasMethodDiscreteSampler

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