Uploaded image for project: 'Commons RNG'
  1. Commons RNG
  2. RNG-95




    • Improvement
    • Status: Closed
    • Minor
    • Resolution: Implemented
    • 1.3
    • 1.3
    • sampling
    • None


      The DiscreteUniformSampler delegates the creation of an integer in the range [0, n) to the UniformRandomProvider.

      This sampler will be repeatedly used to sample the same range. The default method in BaseProvider uses a dynamic algorithm that handles n differently when a power of 2.

      When the range is a power of 2 the method can use a series of bits from a random integer to generate a uniform integer in the range. This is fast.

      When the range is not a power of 2 the algorithm must reject samples when the sample would result in an over-representation of a particular value in the uniform range. This is necessary as n does not exactly fit into the number of possible values [0, 2^31) that can be produced by the generator (when using 31-bit signed integers). The rejection method uses integer arithmetic to determine the number of samples that fit into the range: samples = 2^31 / n. Extra samples that lead to over-representation are rejected: extra = 2^31 % n.

      Since n will not change a pre-computation step is possible to select the best algorithm.

      n is a power of 2:

      // Favouring the least significant bits
      // Pre-compute
      int mask = n - 1;
      return nextInt() & mask;
      // Or favouring the most significant bits
      // Pre-compute
      int shift = Integer.numberOfLeadingZeros(n) + 1;
      return nextInt() >>> shift;

      n is not a power of 2:

      // Sample using modulus
      // Pre-compute
      final int fence = (int)(0x80000000L - 0x80000000L % n - 1);
      int bits;
      do {
          bits = rng.nextInt() >>> 1;
      } while (bits > fence);
      return bits % n;
      // Or using 32-bit unsigned arithmetic avoiding modulus
      // Pre-compute
      final long fence = (1L << 32) % n;
      long result;
      do {
          // Compute 64-bit unsigned product of n * [0, 2^32 - 1)
          result = n * (rng.nextInt() & 0xffffffffL);
          // Test the sample uniformity.
      } while ((result & 0xffffffffL) < fence);
      // Divide by 2^32 to get the sample
      return (int)(result >>> 32);

      The second method uses a range of 2^32 instead of 2^31 so reducing the rejection probability and avoids the modulus operator; these both increase speed.

      Note algorithm 1 returns sample values in a repeat cycle from all values in the range [0, 2^31) due to the use of modulus, e.g.

      0, 1, 2, ..., 0, 1, 2, ...

      Algorithm 2 returns sample values in a linear order, e.g.

      0, 0, 1, 1, 2, 2, ...

      The suggested change is to implement smart pre-computation in the DiscreteUniformSampler based on the range and use the algorithms that favour the most significant bits from the generator.


        Issue Links



              aherbert Alex Herbert
              aherbert Alex Herbert
              0 Vote for this issue
              1 Start watching this issue



                Time Tracking

                  Original Estimate - Not Specified
                  Not Specified
                  Remaining Estimate - 0h
                  Time Spent - 40m