001package stdlib;
002/* ***********************************************************************
003 *  Compilation:  javac StdRandom.java
004 *  Execution:    java StdRandom
005 *
006 *  A library of static methods to generate pseudo-random numbers from
007 *  different distributions (bernoulli, uniform, gaussian, discrete,
008 *  and exponential). Also includes a method for shuffling an array.
009 *
010 *
011 *  %  java StdRandom 5
012 *  seed = 1316600602069
013 *  59 16.81826  true 8.83954  0
014 *  32 91.32098  true 9.11026  0
015 *  35 10.11874  true 8.95396  3
016 *  92 32.88401  true 8.87089  0
017 *  72 92.55791  true 9.46241  0
018 *
019 *  % java StdRandom 5
020 *  seed = 1316600616575
021 *  96 60.17070  true 8.72821  0
022 *  79 32.01607  true 8.58159  0
023 *  81 59.49065  true 9.10423  1
024 *  96 51.65818  true 9.02102  0
025 *  99 17.55771  true 8.99762  0
026 *
027 *  % java StdRandom 5 1316600616575
028 *  seed = 1316600616575
029 *  96 60.17070  true 8.72821  0
030 *  79 32.01607  true 8.58159  0
031 *  81 59.49065  true 9.10423  1
032 *  96 51.65818  true 9.02102  0
033 *  99 17.55771  true 8.99762  0
034 *
035 *
036 *  Remark
037 *  ------
038 *    - Relies on randomness of nextDouble() method in java.util.Random
039 *      to generate pseudorandom numbers in [0, 1).
040 *
041 *    - This library allows you to set and get the pseudorandom number seed.
042 *
043 *    - See http://www.honeylocust.com/RngPack/ for an industrial
044 *      strength random number generator in Java.
045 *
046 *************************************************************************/
047
048import java.util.Random;
049
050/**
051 *  <i>Standard random</i>. This class provides methods for generating
052 *  random number from various distributions.
053 *  <p>
054 *  For additional documentation, see <a href="http://introcs.cs.princeton.edu/22library">Section 2.2</a> of
055 *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
056 */
057public final class StdRandom {
058
059        private static Random random;    // pseudo-random number generator
060        private static long seed;        // pseudo-random number generator seed
061
062        // static initializer
063        static {
064                // this is how the seed was set in Java 1.4
065                seed = System.currentTimeMillis();
066                random = new Random(seed);
067        }
068
069        // don't instantiate
070        private StdRandom() { }
071
072        /**
073         * Set the seed of the psedurandom number generator.
074         */
075        public static void setSeed(long s) {
076                seed   = s;
077                random = new Random(seed);
078        }
079
080        /**
081         * Get the seed of the psedurandom number generator.
082         */
083        public static long getSeed() {
084                return seed;
085        }
086
087        /**
088         * Return real number uniformly in [0, 1).
089         */
090        public static double uniform() {
091                return random.nextDouble();
092        }
093
094        /**
095         * Return an integer uniformly between 0 (inclusive) and N (exclusive).
096         */
097        public static int uniform(int N) {
098                return random.nextInt(N);
099        }
100
101        ///////////////////////////////////////////////////////////////////////////
102        //  STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA
103        //  THE STATIC METHODS ABOVE.
104        ///////////////////////////////////////////////////////////////////////////
105
106        /**
107         * Return real number uniformly in [0, 1).
108         */
109        public static double random() {
110                return uniform();
111        }
112
113        /**
114         * Return int uniformly in [a, b).
115         */
116        public static int uniform(int a, int b) {
117                return (int) (a + uniform() * (((double)b)-((double)a)));
118        }
119
120        /**
121         * Return real number uniformly in [a, b).
122         */
123        public static double uniform(double a, double b) {
124                return a + uniform() * (b-a);
125        }
126
127        /**
128         * Return a boolean, which is true with probability p, and false otherwise.
129         */
130        public static boolean bernoulli(double p) {
131                return uniform() < p;
132        }
133
134        /**
135         * Return a boolean, which is true with probability .5, and false otherwise.
136         */
137        public static boolean bernoulli() {
138                return bernoulli(0.5);
139        }
140
141        /**
142         * Return a real number with a standard Gaussian distribution.
143         */
144        public static double gaussian() {
145                // use the polar form of the Box-Muller transform
146                double r, x, y;
147                do {
148                        x = uniform(-1.0, 1.0);
149                        y = uniform(-1.0, 1.0);
150                        r = x*x + y*y;
151                } while (r >= 1 || r == 0);
152                return x * Math.sqrt(-2 * Math.log(r) / r);
153
154                // Remark:  y * Math.sqrt(-2 * Math.log(r) / r)
155                // is an independent random gaussian
156        }
157
158        /**
159         * Return a real number from a gaussian distribution with given mean and stddev
160         */
161        public static double gaussian(double mean, double stddev) {
162                return mean + stddev * gaussian();
163        }
164
165        /**
166         * Return an integer with a geometric distribution with mean 1/p.
167         */
168        public static int geometric(double p) {
169                // using algorithm given by Knuth
170                return (int) Math.ceil(Math.log(uniform()) / Math.log(1.0 - p));
171        }
172
173        /**
174         * Return an integer with a Poisson distribution with mean lambda.
175         */
176        public static int poisson(double lambda) {
177                // using algorithm given by Knuth
178                // see http://en.wikipedia.org/wiki/Poisson_distribution
179                int k = 0;
180                double p = 1.0;
181                double L = Math.exp(-lambda);
182                do {
183                        k++;
184                        p *= uniform();
185                } while (p >= L);
186                return k-1;
187        }
188
189        /**
190         * Return a real number with a Pareto distribution with parameter alpha.
191         */
192        public static double pareto(double alpha) {
193                return Math.pow(1 - uniform(), -1.0/alpha) - 1.0;
194        }
195
196        /**
197         * Return a real number with a Cauchy distribution.
198         */
199        public static double cauchy() {
200                return Math.tan(Math.PI * (uniform() - 0.5));
201        }
202
203        /**
204         * Return a number from a discrete distribution: i with probability a[i].
205         * Precondition: array entries are nonnegative and their sum (very nearly) equals 1.0.
206         */
207        public static int discrete(double[] a) {
208                double EPSILON = 1E-14;
209                double sum = 0.0;
210                for (int i = 0; i < a.length; i++) {
211                        if (a[i] < 0.0) throw new IllegalArgumentException("array entry " + i + " is negative: " + a[i]);
212                        sum = sum + a[i];
213                }
214                if (sum > 1.0 + EPSILON || sum < 1.0 - EPSILON)
215                        throw new IllegalArgumentException("sum of array entries not equal to one: " + sum);
216
217                // the for loop may not return a value when both r is (nearly) 1.0 and when the
218                // cumulative sum is less than 1.0 (as a result of floating-point roundoff error)
219                while (true) {
220                        double r = uniform();
221                        sum = 0.0;
222                        for (int i = 0; i < a.length; i++) {
223                                sum = sum + a[i];
224                                if (sum > r) return i;
225                        }
226                }
227        }
228
229        /**
230         * Return a real number from an exponential distribution with rate lambda.
231         */
232        public static double exp(double lambda) {
233                return -Math.log(1 - uniform()) / lambda;
234        }
235
236        /**
237         * Rearrange the elements of an array in random order.
238         */
239        public static void shuffle(Object[] a) {
240                int N = a.length;
241                for (int i = 0; i < N; i++) {
242                        int r = i + uniform(N-i);     // between i and N-1
243                        Object temp = a[i];
244                        a[i] = a[r];
245                        a[r] = temp;
246                }
247        }
248
249        /**
250         * Rearrange the elements of a double array in random order.
251         */
252        public static void shuffle(double[] a) {
253                int N = a.length;
254                for (int i = 0; i < N; i++) {
255                        int r = i + uniform(N-i);     // between i and N-1
256                        double temp = a[i];
257                        a[i] = a[r];
258                        a[r] = temp;
259                }
260        }
261
262        /**
263         * Rearrange the elements of an int array in random order.
264         */
265        public static void shuffle(int[] a) {
266                int N = a.length;
267                for (int i = 0; i < N; i++) {
268                        int r = i + uniform(N-i);     // between i and N-1
269                        int temp = a[i];
270                        a[i] = a[r];
271                        a[r] = temp;
272                }
273        }
274
275
276        /**
277         * Rearrange the elements of the subarray a[lo..hi] in random order.
278         */
279        public static void shuffle(Object[] a, int lo, int hi) {
280                if (lo < 0 || lo > hi || hi >= a.length)
281                        throw new RuntimeException("Illegal subarray range");
282                for (int i = lo; i <= hi; i++) {
283                        int r = i + uniform(hi-i+1);     // between i and hi
284                        Object temp = a[i];
285                        a[i] = a[r];
286                        a[r] = temp;
287                }
288        }
289
290        /**
291         * Rearrange the elements of the subarray a[lo..hi] in random order.
292         */
293        public static void shuffle(double[] a, int lo, int hi) {
294                if (lo < 0 || lo > hi || hi >= a.length)
295                        throw new RuntimeException("Illegal subarray range");
296                for (int i = lo; i <= hi; i++) {
297                        int r = i + uniform(hi-i+1);     // between i and hi
298                        double temp = a[i];
299                        a[i] = a[r];
300                        a[r] = temp;
301                }
302        }
303
304        /**
305         * Rearrange the elements of the subarray a[lo..hi] in random order.
306         */
307        public static void shuffle(int[] a, int lo, int hi) {
308                if (lo < 0 || lo > hi || hi >= a.length)
309                        throw new RuntimeException("Illegal subarray range");
310                for (int i = lo; i <= hi; i++) {
311                        int r = i + uniform(hi-i+1);     // between i and hi
312                        int temp = a[i];
313                        a[i] = a[r];
314                        a[r] = temp;
315                }
316        }
317
318        /**
319         * Unit test.
320         */
321        public static void main(String[] args) {
322                int N = Integer.parseInt(args[0]);
323                if (args.length == 2) StdRandom.setSeed(Long.parseLong(args[1]));
324                double[] t = { .5, .3, .1, .1 };
325
326                StdOut.println("seed = " + StdRandom.getSeed());
327                for (int i = 0; i < N; i++) {
328                        StdOut.format("%2d "  , uniform(100));
329                        StdOut.format("%8.5f ", uniform(10.0, 99.0));
330                        StdOut.format("%5b "  , bernoulli(.5));
331                        StdOut.format("%7.5f ", gaussian(9.0, .2));
332                        StdOut.format("%2d "  , discrete(t));
333                        StdOut.println();
334                }
335
336                String[] a = "A B C D E F G".split(" ");
337                for (String s : a)
338                        StdOut.print(s + " ");
339                StdOut.println();
340        }
341
342}