Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*************************************************************************
- * 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;
- /**
- * <i>Standard random</i>. This class provides methods for generating
- * random number from various distributions.
- * <p>
- * For additional documentation, see <a href="http://introcs.cs.princeton.edu/22library">Section 2.2</a> of
- * <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> 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);
- }
- // singleton pattern - can'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 and N-1.
- */
- 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 a + uniform(b - 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 equals 1.
- */
- public static int discrete(double[] a) {
- double EPSILON = 1E-15;
- 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);
- double r = uniform();
- sum = 0.0;
- for (int i = 0; i < a.length; i++) {
- sum = sum + a[i];
- if (sum >= r) return i;
- }
- return -1;
- }
- /**
- * 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.printf("%2d " , uniform(100));
- StdOut.printf("%8.5f ", uniform(10.0, 99.0));
- StdOut.printf("%5b " , bernoulli(.5));
- StdOut.printf("%7.5f ", gaussian(9.0, .2));
- StdOut.printf("%2d " , discrete(t));
- StdOut.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement