Skip to content

Instantly share code, notes, and snippets.

@futuresecurity
Created September 25, 2018 22:00
Show Gist options
  • Save futuresecurity/9a9b3d24fadd2ae295f6e2ee2bd98229 to your computer and use it in GitHub Desktop.
Save futuresecurity/9a9b3d24fadd2ae295f6e2ee2bd98229 to your computer and use it in GitHub Desktop.
Fast approximately uniform int sampling algorithm. See "Fast Random Integer Generation in an Interval" by Daniel Lemire for a similar unbiased algorithm.
default int nextInt_Biased(int upperBound)
{
if (upperBound == 0) { return nextInt(); }
if (upperBound == 1) { return 0; }
final long unsignedLimit = upperBound & 0xFFFF_FFFFL;
final int log2Ceil = 64 - Long.numberOfLeadingZeros(unsignedLimit - 1);
final int bitsOfRandomness = 64 - log2Ceil;
final long rand = nextUnsignedLongBits(bitsOfRandomness);
return (int)(long)((rand * unsignedLimit) >>> bitsOfRandomness);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment