content: /*************************************************************************
   *  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].
       */
      public static int discrete(double[] a) {
          // precondition: sum of array entries equals 1
          double r = uniform();
          double sum = 0.0;
          for (int i = 0; i < a.length; i++) {
              sum = sum + a[i];
              if (sum >= r) return i;
          }
          assert false;
          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();
          }
      }
  
  }
  