package stdlib; /* *********************************************************************** * Compilation: javac StdRandom.java * Execution: java StdRandom * * 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 pseudorandom numbers in [0, 1). * * - This library allows you to set and get the pseudorandom number seed. * * - See http://www.honeylocust.com/RngPack/ for an industrial * strength random number generator in Java. * *************************************************************************/ import java.util.Random; /** * Standard random. This class provides methods for generating * random number from various distributions. *
* For additional documentation, see Section 2.2 of * Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and 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() { } /** * Set the seed of the psedurandom number generator. */ public static void setSeed(long s) { seed = s; random = new Random(seed); } /** * Get the seed of the psedurandom number generator. */ public static long getSeed() { return seed; } /** * Return real number uniformly in [0, 1). */ public static double uniform() { return random.nextDouble(); } /** * Return an integer uniformly between 0 (inclusive) and N (exclusive). */ public static int uniform(int N) { return random.nextInt(N); } /////////////////////////////////////////////////////////////////////////// // STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA // THE STATIC METHODS ABOVE. /////////////////////////////////////////////////////////////////////////// /** * Return real number uniformly in [0, 1). */ public static double random() { return uniform(); } /** * Return int uniformly in [a, b). */ public static int uniform(int a, int b) { return (int) (a + uniform() * (((double)b)-((double)a))); } /** * Return real number uniformly in [a, b). */ public static double uniform(double a, double b) { return a + uniform() * (b-a); } /** * Return a boolean, which is true with probability p, and false otherwise. */ public static boolean bernoulli(double p) { return uniform() < p; } /** * Return a boolean, which is true with probability .5, and false otherwise. */ public static boolean bernoulli() { return bernoulli(0.5); } /** * Return a real number with a standard Gaussian distribution. */ public static double gaussian() { // use the polar form of the Box-Muller transform double r, x, y; do { x = uniform(-1.0, 1.0); y = uniform(-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 } /** * Return a real number from a gaussian distribution with given mean and stddev */ public static double gaussian(double mean, double stddev) { return mean + stddev * gaussian(); } /** * Return an integer with a geometric distribution with mean 1/p. */ public static int geometric(double p) { // using algorithm given by Knuth return (int) Math.ceil(Math.log(uniform()) / Math.log(1.0 - p)); } /** * Return an integer with a Poisson distribution with mean lambda. */ public static int poisson(double lambda) { // using algorithm given by Knuth // see http://en.wikipedia.org/wiki/Poisson_distribution int k = 0; double p = 1.0; double L = Math.exp(-lambda); do { k++; p *= uniform(); } while (p >= L); return k-1; } /** * Return a real number with a Pareto distribution with parameter alpha. */ public static double pareto(double alpha) { return Math.pow(1 - uniform(), -1.0/alpha) - 1.0; } /** * Return a real number with a Cauchy distribution. */ public static double cauchy() { return Math.tan(Math.PI * (uniform() - 0.5)); } /** * Return a number from a discrete distribution: i with probability a[i]. * Precondition: array entries are nonnegative and their sum (very nearly) equals 1.0. */ public static int discrete(double[] a) { double EPSILON = 1E-14; double sum = 0.0; for (int i = 0; i < a.length; i++) { if (a[i] < 0.0) throw new IllegalArgumentException("array entry " + i + " is negative: " + a[i]); sum = sum + a[i]; } if (sum > 1.0 + EPSILON || sum < 1.0 - EPSILON) throw new IllegalArgumentException("sum of array entries not equal to one: " + 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 = uniform(); sum = 0.0; for (int i = 0; i < a.length; i++) { sum = sum + a[i]; if (sum > r) return i; } } } /** * Return a real number from an exponential distribution with rate lambda. */ public static double exp(double lambda) { return -Math.log(1 - uniform()) / lambda; } /** * Rearrange the elements of an array in random order. */ public static void shuffle(Object[] a) { int N = a.length; for (int i = 0; i < N; i++) { int r = i + uniform(N-i); // between i and N-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearrange the elements of a double array in random order. */ public static void shuffle(double[] a) { int N = a.length; for (int i = 0; i < N; i++) { int r = i + uniform(N-i); // between i and N-1 double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearrange the elements of an int array in random order. */ public static void shuffle(int[] a) { int N = a.length; for (int i = 0; i < N; i++) { int r = i + uniform(N-i); // between i and N-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearrange the elements of the subarray a[lo..hi] in random order. */ public static void shuffle(Object[] a, int lo, int hi) { if (lo < 0 || lo > hi || hi >= a.length) throw new RuntimeException("Illegal subarray range"); for (int i = lo; i <= hi; i++) { int r = i + uniform(hi-i+1); // between i and hi Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearrange the elements of the subarray a[lo..hi] in random order. */ public static void shuffle(double[] a, int lo, int hi) { if (lo < 0 || lo > hi || hi >= a.length) throw new RuntimeException("Illegal subarray range"); for (int i = lo; i <= hi; i++) { int r = i + uniform(hi-i+1); // between i and hi double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearrange the elements of the subarray a[lo..hi] in random order. */ public static void shuffle(int[] a, int lo, int hi) { if (lo < 0 || lo > hi || hi >= a.length) throw new RuntimeException("Illegal subarray range"); for (int i = lo; i <= hi; i++) { int r = i + uniform(hi-i+1); // between i and hi int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Unit test. */ public static void main(String[] args) { int N = Integer.parseInt(args[0]); if (args.length == 2) StdRandom.setSeed(Long.parseLong(args[1])); double[] t = { .5, .3, .1, .1 }; StdOut.println("seed = " + StdRandom.getSeed()); for (int i = 0; i < N; i++) { StdOut.format("%2d " , uniform(100)); StdOut.format("%8.5f ", uniform(10.0, 99.0)); StdOut.format("%5b " , bernoulli(.5)); StdOut.format("%7.5f ", gaussian(9.0, .2)); StdOut.format("%2d " , discrete(t)); StdOut.println(); } String[] a = "A B C D E F G".split(" "); for (String s : a) StdOut.print(s + " "); StdOut.println(); } }