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}