Experimental uniform int sampling algorithm. Requires a UniformGenerator capable of producing up to 32 bit samples. Outputs a number in [0, bound - 1]. It builds on java.util.Random's nextInt(int) algorithm. It factors `bound` to better handle more values of `bound`. (Special care is taken for the factors which are a power of two. It avoids usin…

BoundedIntSampling.java

package io.github.futuresecurity.random.sampling;

import io.github.futuresecurity.random.UniformGenerator;

import java.util.SplittableRandom;

public class BoundedIntSampling
{
  public static int randomInt_TwoFactor32(int bound, UniformGenerator rng)
  {
    if (bound == 0) { return rng.nextInt(); }

    final int factorTwoPower = Integer.numberOfTrailingZeros(bound);
    final int oddFactor = bound >>> factorTwoPower;

    if (oddFactor != 1 && factorTwoPower != 0)
    {
      int r, rem;

      // XOR-Shift for non-zero distances is bijective. Right shift the highest bits into the lowest bits
      // Normally high order bits are "more random" but mod a power-of-two does not use high bits.
      r = rng.nextInt();
      r ^= r >>> (32 - factorTwoPower);

      rem = Integer.remainderUnsigned(r, bound);
      final int evenPart = r & lowBitIntMask(factorTwoPower);

      if (remainderRangeCheck(r, rem, bound))
      {
        return rem;
      }
      else
      {
        final int oddPart = randomInt_GeneralMod32(oddFactor, rng);
        return (oddPart << factorTwoPower) + evenPart;
      }
    }
    else if (oddFactor == 1)
    {
      if (bound == 1) { return 0; }
      return rng.nextUnsignedIntBits(factorTwoPower);
    }
    else
    {
      return randomInt_GeneralMod32(bound, rng);
    }
  }

  public static int randomInt_GeneralMod32(int bound, UniformGenerator rng)
  {
    while (true)
    {
      final int r = rng.nextInt(), rem;
      rem = Integer.remainderUnsigned(r, bound);

      if (remainderRangeCheck(r, rem, bound))
      {
        return rem;
      }
    }
  }

  private static int lowBitIntMask(int bitCount)
  {
    return (~0) >>> (32 - bitCount);
  }

  private static boolean remainderRangeCheck(int r, int rem, int bound)
  {
    // Get the largest multiple of bound <= r
    final int floorMultiple = r - rem;
    // Get one less than the next multiple. May overflow.
    final int endRange = floorMultiple + (bound - 1);
    // If overflow, then range [floorMultiple, endRange] doesn't fit in an int.
    return !unsignedLessThan(endRange, floorMultiple);
  }

  private static boolean unsignedLessThan(int a, int b)
  {
    return Integer.compareUnsigned(a, b) < 0;
  }

  private BoundedIntSampling() { }
}