Below is the syntax highlighted version of StdRandom.java
from § Standard Libraries.
Here is the Javadoc.
/****************************************************************************** * Compilation: javac StdRandom.java * Execution: java StdRandom * Dependencies: StdOut.java * * A library of static methods to generate pseudo-random numbers from * different distributions (bernoulli, uniform, gaussian, discrete, * and exponential). Also includes a method for shuffling an array. * * * % java StdRandom 5 * seed = 1316600602069 * 59 16.81826 true 8.83954 0 * 32 91.32098 true 9.11026 0 * 35 10.11874 true 8.95396 3 * 92 32.88401 true 8.87089 0 * 72 92.55791 true 9.46241 0 * * % java StdRandom 5 * seed = 1316600616575 * 96 60.17070 true 8.72821 0 * 79 32.01607 true 8.58159 0 * 81 59.49065 true 9.10423 1 * 96 51.65818 true 9.02102 0 * 99 17.55771 true 8.99762 0 * * % java StdRandom 5 1316600616575 * seed = 1316600616575 * 96 60.17070 true 8.72821 0 * 79 32.01607 true 8.58159 0 * 81 59.49065 true 9.10423 1 * 96 51.65818 true 9.02102 0 * 99 17.55771 true 8.99762 0 * * * Remark * ------ * - Relies on randomness of nextDouble() method in java.util.Random * to generate pseudo-random numbers in [0, 1). * * - This library allows you to set and get the pseudo-random number seed. * * - See http://www.honeylocust.com/RngPack/ for an industrial * strength random number generator in Java. * ******************************************************************************/ import java.util.Random; /** * The {@code StdRandom} class provides static methods for generating * random number from various discrete and continuous distributions, * including uniform, Bernoulli, geometric, Gaussian, exponential, Pareto, * Poisson, and Cauchy. It also provides method for shuffling an * array or subarray and generating random permutations. * * <p><b>Conventions.</b> * By convention, all intervals are half open. For example, * <code>uniformDouble(-1.0, 1.0)</code> returns a random number between * <code>-1.0</code> (inclusive) and <code>1.0</code> (exclusive). * Similarly, <code>shuffle(a, lo, hi)</code> shuffles the <code>hi - lo</code> * elements in the array <code>a[]</code>, starting at index <code>lo</code> * (inclusive) and ending at index <code>hi</code> (exclusive). * * <p><b>Performance.</b> * The methods all take constant expected time, except those that involve arrays. * The <em>shuffle</em> method takes time linear in the subarray to be shuffled; * the <em>discrete</em> methods take time linear in the length of the argument * array. * * <p><b>Additional information.</b> * For additional documentation, * see <a href="https://introcs.cs.princeton.edu/22library">Section 2.2</a> of * <i>Computer Science: An Interdisciplinary Approach</i> * by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public final class StdRandom { private static Random random; // pseudo-random number generator private static long seed; // pseudo-random number generator seed // static initializer static { // this is how the seed was set in Java 1.4 seed = System.currentTimeMillis(); random = new Random(seed); } // don't instantiate private StdRandom() { } /** * Sets the seed of the pseudo-random number generator. * This method enables you to produce the same sequence of "random" * number for each execution of the program. * Ordinarily, you should call this method at most once per program. * * @param s the seed */ public static void setSeed(long s) { seed = s; random = new Random(seed); } /** * Returns the seed of the pseudo-random number generator. * * @return the seed */ public static long getSeed() { return seed; } /** * Returns a random real number uniformly in [0, 1). * * @return a random real number uniformly in [0, 1) * @deprecated Replaced by {@link #uniformDouble()}. */ @Deprecated public static double uniform() { return uniformDouble(); } /** * Returns a random real number uniformly in [0, 1). * * @return a random real number uniformly in [0, 1) */ public static double uniformDouble() { return random.nextDouble(); } /** * Returns a random integer uniformly in [0, n). * * @param n number of possible integers * @return a random integer uniformly between 0 (inclusive) and {@code n} (exclusive) * @throws IllegalArgumentException if {@code n <= 0} * @deprecated Replaced by {@link #uniformInt(int n)}. */ @Deprecated public static int uniform(int n) { return uniformInt(n); } /** * Returns a random integer uniformly in [0, n). * * @param n number of possible integers * @return a random integer uniformly between 0 (inclusive) and {@code n} (exclusive) * @throws IllegalArgumentException if {@code n <= 0} */ public static int uniformInt(int n) { if (n <= 0) throw new IllegalArgumentException("argument must be positive: " + n); return random.nextInt(n); } /** * Returns a random long integer uniformly in [0, n). * * @param n number of possible {@code long} integers * @return a random long integer uniformly between 0 (inclusive) and {@code n} (exclusive) * @throws IllegalArgumentException if {@code n <= 0} * @deprecated Replaced by {@link #uniformLong(long n)}. */ @Deprecated public static long uniform(long n) { return uniformLong(n); } /** * Returns a random long integer uniformly in [0, n). * * @param n number of possible {@code long} integers * @return a random long integer uniformly between 0 (inclusive) and {@code n} (exclusive) * @throws IllegalArgumentException if {@code n <= 0} */ public static long uniformLong(long n) { if (n <= 0L) throw new IllegalArgumentException("argument must be positive: " + n); // https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#longs-long-long-long- long r = random.nextLong(); long m = n - 1; // power of two if ((n & m) == 0L) { return r & m; } // reject over-represented candidates long u = r >>> 1; while (u + m - (r = u % n) < 0L) { u = random.nextLong() >>> 1; } return r; } /////////////////////////////////////////////////////////////////////////// // STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA // THE STATIC METHODS ABOVE. /////////////////////////////////////////////////////////////////////////// /** * Returns a random real number uniformly in [0, 1). * * @return a random real number uniformly in [0, 1) * @deprecated Replaced by {@link #uniformDouble()}. */ @Deprecated public static double random() { return uniformDouble(); } /** * Returns a random integer uniformly in [a, b). * * @param a the left endpoint * @param b the right endpoint * @return a random integer uniformly in [a, b) * @throws IllegalArgumentException if {@code b <= a} * @throws IllegalArgumentException if {@code b - a >= Integer.MAX_VALUE} * @deprecated Replaced by {@link #uniformInt(int a, int b)}. */ @Deprecated public static int uniform(int a, int b) { return uniformInt(a, b); } /** * Returns a random integer uniformly in [a, b). * * @param a the left endpoint * @param b the right endpoint * @return a random integer uniformly in [a, b) * @throws IllegalArgumentException if {@code b <= a} * @throws IllegalArgumentException if {@code b - a >= Integer.MAX_VALUE} */ public static int uniformInt(int a, int b) { if ((b <= a) || ((long) b - a >= Integer.MAX_VALUE)) { throw new IllegalArgumentException("invalid range: [" + a + ", " + b + ")"); } return a + uniform(b - a); } /** * Returns a random real number uniformly in [a, b). * * @param a the left endpoint * @param b the right endpoint * @return a random real number uniformly in [a, b) * @throws IllegalArgumentException unless {@code a < b} * @deprecated Replaced by {@link #uniformDouble(double a, double b)}. */ @Deprecated public static double uniform(double a, double b) { return uniformDouble(a, b); } /** * Returns a random real number uniformly in [a, b). * * @param a the left endpoint * @param b the right endpoint * @return a random real number uniformly in [a, b) * @throws IllegalArgumentException unless {@code a < b} */ public static double uniformDouble(double a, double b) { if (!(a < b)) { throw new IllegalArgumentException("invalid range: [" + a + ", " + b + ")"); } return a + uniform() * (b-a); } /** * Returns a random boolean from a Bernoulli distribution with success * probability <em>p</em>. * * @param p the probability of returning {@code true} * @return {@code true} with probability {@code p} and * {@code false} with probability {@code 1 - p} * @throws IllegalArgumentException unless {@code 0} ≤ {@code p} ≤ {@code 1.0} */ public static boolean bernoulli(double p) { if (!(p >= 0.0 && p <= 1.0)) throw new IllegalArgumentException("probability p must be between 0.0 and 1.0: " + p); return uniformDouble() < p; } /** * Returns a random boolean from a Bernoulli distribution with success * probability 1/2. * * @return {@code true} with probability 1/2 and * {@code false} with probability 1/2 */ public static boolean bernoulli() { return bernoulli(0.5); } /** * Returns a random real number from a standard Gaussian distribution. * * @return a random real number from a standard Gaussian distribution * (mean 0 and standard deviation 1). */ public static double gaussian() { // use the polar form of the Box-Muller transform double r, x, y; do { x = uniformDouble(-1.0, 1.0); y = uniformDouble(-1.0, 1.0); r = x*x + y*y; } while (r >= 1 || r == 0); return x * Math.sqrt(-2 * Math.log(r) / r); // Remark: y * Math.sqrt(-2 * Math.log(r) / r) // is an independent random gaussian } /** * Returns a random real number from a Gaussian distribution with mean μ * and standard deviation σ. * * @param mu the mean * @param sigma the standard deviation * @return a real number distributed according to the Gaussian distribution * with mean {@code mu} and standard deviation {@code sigma} */ public static double gaussian(double mu, double sigma) { return mu + sigma * gaussian(); } /** * Returns a random integer from a geometric distribution with success * probability <em>p</em>. * The integer represents the number of independent trials * before the first success. * * @param p the parameter of the geometric distribution * @return a random integer from a geometric distribution with success * probability {@code p}; or {@code Integer.MAX_VALUE} if * {@code p} is (nearly) equal to {@code 1.0}. * @throws IllegalArgumentException unless {@code p >= 0.0} and {@code p <= 1.0} */ public static int geometric(double p) { if (!(p >= 0)) { throw new IllegalArgumentException("probability p must be greater than 0: " + p); } if (!(p <= 1.0)) { throw new IllegalArgumentException("probability p must not be larger than 1: " + p); } // using algorithm given by Knuth return (int) Math.ceil(Math.log(uniformDouble()) / Math.log(1.0 - p)); } /** * Returns a random integer from a Poisson distribution with mean λ. * * @param lambda the mean of the Poisson distribution * @return a random integer from a Poisson distribution with mean {@code lambda} * @throws IllegalArgumentException unless {@code lambda > 0.0} and not infinite */ public static int poisson(double lambda) { if (!(lambda > 0.0)) throw new IllegalArgumentException("lambda must be positive: " + lambda); if (Double.isInfinite(lambda)) throw new IllegalArgumentException("lambda must not be infinite: " + lambda); // using algorithm given by Knuth // see http://en.wikipedia.org/wiki/Poisson_distribution int k = 0; double p = 1.0; double expLambda = Math.exp(-lambda); do { k++; p *= uniformDouble(); } while (p >= expLambda); return k-1; } /** * Returns a random real number from the standard Pareto distribution. * * @return a random real number from the standard Pareto distribution */ public static double pareto() { return pareto(1.0); } /** * Returns a random real number from a Pareto distribution with * shape parameter α. * * @param alpha shape parameter * @return a random real number from a Pareto distribution with shape * parameter {@code alpha} * @throws IllegalArgumentException unless {@code alpha > 0.0} */ public static double pareto(double alpha) { if (!(alpha > 0.0)) throw new IllegalArgumentException("alpha must be positive: " + alpha); return Math.pow(1 - uniformDouble(), -1.0 / alpha) - 1.0; } /** * Returns a random real number from the Cauchy distribution. * * @return a random real number from the Cauchy distribution. */ public static double cauchy() { return Math.tan(Math.PI * (uniformDouble() - 0.5)); } /** * Returns a random integer from the specified discrete distribution. * * @param probabilities the probability of occurrence of each integer * @return a random integer from a discrete distribution: * {@code i} with probability {@code probabilities[i]} * @throws IllegalArgumentException if {@code probabilities} is {@code null} * @throws IllegalArgumentException if sum of array entries is not (very nearly) equal to {@code 1.0} * @throws IllegalArgumentException unless {@code probabilities[i] >= 0.0} for each index {@code i} */ public static int discrete(double[] probabilities) { if (probabilities == null) throw new IllegalArgumentException("argument array must not be null"); double EPSILON = 1.0E-14; double sum = 0.0; for (int i = 0; i < probabilities.length; i++) { if (!(probabilities[i] >= 0.0)) throw new IllegalArgumentException("array entry " + i + " must be non-negative: " + probabilities[i]); sum += probabilities[i]; } if (sum > 1.0 + EPSILON || sum < 1.0 - EPSILON) throw new IllegalArgumentException("sum of array entries does not approximately equal 1.0: " + sum); // the for loop may not return a value when both r is (nearly) 1.0 and when the // cumulative sum is less than 1.0 (as a result of floating-point roundoff error) while (true) { double r = uniformDouble(); sum = 0.0; for (int i = 0; i < probabilities.length; i++) { sum = sum + probabilities[i]; if (sum > r) return i; } } } /** * Returns a random integer from the specified discrete distribution. * * @param frequencies the frequency of occurrence of each integer * @return a random integer from a discrete distribution: * {@code i} with probability proportional to {@code frequencies[i]} * @throws IllegalArgumentException if {@code frequencies} is {@code null} * @throws IllegalArgumentException if all array entries are {@code 0} * @throws IllegalArgumentException if {@code frequencies[i]} is negative for any index {@code i} * @throws IllegalArgumentException if sum of frequencies exceeds {@code Integer.MAX_VALUE} (2<sup>31</sup> - 1) */ public static int discrete(int[] frequencies) { if (frequencies == null) throw new IllegalArgumentException("argument array must not be null"); long sum = 0; for (int i = 0; i < frequencies.length; i++) { if (frequencies[i] < 0) throw new IllegalArgumentException("array entry " + i + " must be non-negative: " + frequencies[i]); sum += frequencies[i]; } if (sum == 0) throw new IllegalArgumentException("at least one array entry must be positive"); if (sum >= Integer.MAX_VALUE) throw new IllegalArgumentException("sum of frequencies overflows an int"); // pick index i with probability proportional to frequency double r = uniformInt((int) sum); sum = 0; for (int i = 0; i < frequencies.length; i++) { sum += frequencies[i]; if (sum > r) return i; } // can't reach here assert false; return -1; } /** * Returns a random real number from an exponential distribution * with rate λ. * * @param lambda the rate of the exponential distribution * @return a random real number from an exponential distribution with * rate {@code lambda} * @throws IllegalArgumentException unless {@code lambda > 0.0} */ public static double exponential(double lambda) { if (!(lambda > 0.0)) throw new IllegalArgumentException("lambda must be positive: " + lambda); return -Math.log(1 - uniformDouble()) / lambda; } /** * Returns a random real number from an exponential distribution * with rate λ. * * @param lambda the rate of the exponential distribution * @return a random real number from an exponential distribution with * rate {@code lambda} * @throws IllegalArgumentException unless {@code lambda > 0.0} * @deprecated Replaced by {@link #exponential(double)}. */ @Deprecated public static double exp(double lambda) { return exponential(lambda); } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(Object[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniformInt(n-i); // between i and n-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(double[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniformInt(n-i); // between i and n-1 double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(int[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniformInt(n-i); // between i and n-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(char[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniformInt(n-i); // between i and n-1 char temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} * */ public static void shuffle(Object[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniformInt(hi-i); // between i and hi-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} */ public static void shuffle(double[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniformInt(hi-i); // between i and hi-1 double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} */ public static void shuffle(int[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniformInt(hi-i); // between i and hi-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Returns a uniformly random permutation of <em>n</em> elements. * * @param n number of elements * @throws IllegalArgumentException if {@code n} is negative * @return an array of length {@code n} that is a uniformly random permutation * of {@code 0}, {@code 1}, ..., {@code n-1} */ public static int[] permutation(int n) { if (n < 0) throw new IllegalArgumentException("n must be non-negative: " + n); int[] perm = new int[n]; for (int i = 0; i < n; i++) perm[i] = i; shuffle(perm); return perm; } /** * Returns a uniformly random permutation of <em>k</em> of <em>n</em> elements. * * @param n number of elements * @param k number of elements to select * @throws IllegalArgumentException if {@code n} is negative * @throws IllegalArgumentException unless {@code 0 <= k <= n} * @return an array of length {@code k} that is a uniformly random permutation * of {@code k} of the elements from {@code 0}, {@code 1}, ..., {@code n-1} */ public static int[] permutation(int n, int k) { if (n < 0) throw new IllegalArgumentException("n must be non-negative: " + n); if (k < 0 || k > n) throw new IllegalArgumentException("k must be between 0 and n: " + k); int[] perm = new int[k]; for (int i = 0; i < k; i++) { int r = uniformInt(i+1); // between 0 and i perm[i] = perm[r]; perm[r] = i; } for (int i = k; i < n; i++) { int r = uniformInt(i+1); // between 0 and i if (r < k) perm[r] = i; } return perm; } // throw an IllegalArgumentException if x is null // (x can be of type Object[], double[], int[], ...) private static void validateNotNull(Object x) { if (x == null) { throw new IllegalArgumentException("argument must not be null"); } } // throw an exception unless 0 <= lo <= hi <= length private static void validateSubarrayIndices(int lo, int hi, int length) { if (lo < 0 || hi > length || lo > hi) { throw new IllegalArgumentException("subarray indices out of bounds: [" + lo + ", " + hi + ")"); } } /** * Unit tests the methods in this class. * * @param args the command-line arguments */ public static void main(String[] args) { int n = Integer.parseInt(args[0]); if (args.length == 2) StdRandom.setSeed(Long.parseLong(args[1])); double[] probabilities = { 0.5, 0.3, 0.1, 0.1 }; int[] frequencies = { 5, 3, 1, 1 }; String[] a = "A B C D E F G".split(" "); StdOut.println("seed = " + StdRandom.getSeed()); for (int i = 0; i < n; i++) { StdOut.printf("%2d ", uniformInt(100)); StdOut.printf("%8.5f ", uniformDouble(10.0, 99.0)); StdOut.printf("%5b ", bernoulli(0.5)); StdOut.printf("%7.5f ", gaussian(9.0, 0.2)); StdOut.printf("%1d ", discrete(probabilities)); StdOut.printf("%1d ", discrete(frequencies)); StdOut.printf("%11d ", uniformLong(100000000000L)); StdRandom.shuffle(a); for (String s : a) StdOut.print(s); StdOut.println(); } } }