//****************************************************************************** // // File: Random.java // Package: edu.rit.util // Unit: Class edu.rit.util.Random // // This Java source file is copyright (C) 2008 by Alan Kaminsky. All rights // reserved. For further information, contact the author, Alan Kaminsky, at // ark@cs.rit.edu. // // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free // software; you can redistribute it and/or modify it under the terms of the GNU // General Public License as published by the Free Software Foundation; either // version 3 of the License, or (at your option) any later version. // // PJ is distributed in the hope that it will be useful, but WITHOUT ANY // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR // A PARTICULAR PURPOSE. See the GNU General Public License for more details. // // Linking this library statically or dynamically with other modules is making a // combined work based on this library. Thus, the terms and conditions of the // GNU General Public License cover the whole combination. // // As a special exception, the copyright holders of this library give you // permission to link this library with independent modules to produce an // executable, regardless of the license terms of these independent modules, and // to copy and distribute the resulting executable under terms of your choice, // provided that you also meet, for each linked independent module, the terms // and conditions of the license of that module. An independent module is a // module which is not derived from or based on this library. If you modify this // library, you may extend this exception to your version of the library, but // you are not obligated to do so. If you do not wish to do so, delete this // exception statement from your version. // // A copy of the GNU General Public License is provided in the file gpl.txt. You // may also obtain a copy of the GNU General Public License on the World Wide // Web at http://www.gnu.org/licenses/gpl.html. // //****************************************************************************** package edu.rit.util; import java.io.Serializable; import java.lang.reflect.Constructor; /** * Class Random is the abstract base class for a pseudorandom number generator * (PRNG) designed for use in parallel scientific programming. It differs from * class java.util.Random in the following ways: *

* Instances can be created by calling a static factory method. The factory * method can take the name of a subclass as an argument and return an instance * of that subclass of class Random. This makes it easier to write a program * that can substitute a different PRNG algorithm at run time. Class {@linkplain * DefaultRandom} provides a default PRNG algorithm. *
*
* Whereas class java.util.Random generates 48-bit numbers under the hood, class * Random generates 64-bit numbers. This makes class Random faster than class * java.util.Random for some operations, notably the nextDouble() * method. *
*
* Whereas the PRNG algorithm in class java.util.Random has a period of about * 2⁴⁸, the default PRNG algorithm in class {@linkplain * DefaultRandom} has a period of about 2⁶⁴. This lets a parallel * program scale up to larger problem sizes without exhausting the PRNG's * period. *
*
* To support the leapfrogging and sequence splitting techniques * for generating pseudorandom numbers in multiple parallel threads or * processes, class Random includes methods for skipping ahead in the sequence * of generated numbers, without having to generate all the intermediate * numbers. *
*
* To avoid unnecessary thread synchronization overhead, class Random is not * multiple thread safe. It assumes that the surrounding program ensures that * only one thread at a time calls methods on an instance. *

* Each method for generating a number comes in two versions; for example: *

 *     public double nextDouble();
 *     public double nextDouble (long skip);
 *

* Calling the second version with an argument skip is equivalent to * calling the first version skip times: *

 *     Random prng1 = Random.getInstance (1234L);
 *     double x = prng1.nextDouble (1000);
 *     Random prng2 = Random.getInstance (1234L);
 *     double y;
 *     for (int i = 0; i < 1000; ++ i)
 *         y = prng2.nextDouble();
 *

* At the end of the above code fragment, x and y will have * the same value. However, calling nextDouble(1000) will typically be * much faster than calling nextDouble() 1000 times. Conversely, * nextDouble(1) is equivalent to nextDouble(), but the former * will typically be slower than the latter. *

* An instance of class Random can be serialized; for example, to checkpoint the * state of the PRNG into a file and restore its state later. *

* The design of class Random is inspired in part by Coddington's JAPARA * library. For further information, see P. Coddington and A. Newell, JAPARA -- * A Java random number generator library for high-performance computing, in * Proceedings of the 18th IEEE International Parallel and Distributed * Processing Symposium (IPDPS'04), April 26-30, 2004, page 156. * * @author Alan Kaminsky * @version 17-Aug-2009 */ public abstract class Random implements Serializable { // Hidden constants. // 1/2^64, as a float and as a double. private static double D_2_POW_NEG_64; private static float F_2_POW_NEG_64; static { double x = 2.0; x *= x; // 2^2 x *= x; // 2^4 x *= x; // 2^8 x *= x; // 2^16 x *= x; // 2^32 x *= x; // 2^64 D_2_POW_NEG_64 = 1.0 / x; F_2_POW_NEG_64 = (float) D_2_POW_NEG_64; } // Hidden constructors. /** * Construct a new PRNG. */ protected Random() { } // Exported operations. /** * Construct a new PRNG with the given seed using the default algorithm. *

* If the "pj.prng" Java system property is specified, it gives the * fully-qualified class name of the default PRNG class that the * getInstance() method will construct. Specifying the * "pj.prng" property will substitute a different PRNG algorithm * into a program without needing to recompile. *

* If the "pj.prng" Java system property is not specified, the * getInstance() method will return an instance of class * {@linkplain DefaultRandom}. *

* You can specify the "pj.prng" property on the Java command line * like this: *

* java -Dpj.prng=MyOwnPrngClass . . . *

* Note: Depending on the PRNG algorithm, certain seed values may not * be allowed. See the PRNG algorithm subclass for further information. * * @param seed Seed. * @param algorithm Fully-qualified name of the class to construct. This * must be a subclass of class Random. * * @exception IllegalArgumentException * (unchecked exception) Thrown if the PRNG algorithm does not allow the * given seed value. * @exception TypeNotPresentException * (unchecked exception) Thrown if a PRNG instance could not be * constructed. The chained exception gives further information about * the problem. */ public static Random getInstance (long seed, String algorithm) { try { Class cl = Class.forName (algorithm); Constructor ctor = cl.getConstructor (Long.TYPE); return (Random) ctor.newInstance (seed); } catch (Exception exc) { throw new TypeNotPresentException (algorithm, exc); } } /** * Set this PRNG's seed. *

* Note: Depending on the PRNG algorithm, certain seed values may not * be allowed. See the PRNG algorithm subclass for further information. * * @param seed Seed. * * @exception IllegalArgumentException * (unchecked exception) Thrown if the PRNG algorithm does not allow the * given seed value. */ public abstract void setSeed (long seed); /** * Skip one position ahead in this PRNG's sequence. */ public void skip() { next(); } /** * Skip the given number of positions ahead in this PRNG's sequence. If * skip <= 0, the skip() method does nothing. * * @param skip Number of positions to skip. */ public void skip (long skip) { if (skip > 0L) next (skip); } /** * Return the Boolean value from the next pseudorandom value in this PRNG's * sequence. With a probability of 0.5 true is returned, with a * probability of 0.5 false is returned. * * @return Boolean value. */ public boolean nextBoolean() { // Use the high-order (sign) bit of the 64-bit random value. return next() >= 0L; } /** * Return the Boolean value from the pseudorandom value the given number of * positions ahead in this PRNG's sequence. With a probability of 0.5 * true is returned, with a probability of 0.5 false is * returned. * * @param skip Number of positions to skip. * * @return Boolean value. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public boolean nextBoolean (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextBoolean(): skip = " + skip + " illegal"); } // Use the high-order (sign) bit of the 64-bit random value. return next (skip) >= 0L; } /** * Return the byte value from the next pseudorandom value in this PRNG's * sequence. Each value in the range −128 through 127 is returned with * a probability of 1/2⁸. * * @return Byte value in the range −128 through 127 inclusive. */ public byte nextByte() { return (byte) next(); } /** * Return the byte value from the next pseudorandom value the given number * of positions ahead in this PRNG's sequence. Each value in the range * −128 through 127 is returned with a probability of 1/2⁸. * * @param skip Number of positions to skip. * * @return Byte value in the range −128 through 127 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public byte nextByte (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextByte(): skip = " + skip + " illegal"); } return (byte) next (skip); } /** * Return the unsigned byte value from the next pseudorandom value in this * PRNG's sequence. Each value in the range 0 through 255 is returned with a * probability of 1/2⁸. * * @return Unsigned byte value (as an int) in the range 0 through * 255 inclusive. */ public int nextUnsignedByte() { return (int) (next() & 0xFFL); } /** * Return the unsigned byte value from the next pseudorandom value the given * number of positions ahead in this PRNG's sequence. Each value in the * range 0 through 255 is returned with a probability of 1/2⁸. * * @param skip Number of positions to skip. * * @return Unsigned byte value (as an int) in the range 0 through * 255 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public int nextUnsignedByte (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextUnsignedByte(): skip = " + skip + " illegal"); } return (int) (next (skip) & 0xFFL); } /** * Return the character value from the next pseudorandom value in this * PRNG's sequence. Each value in the range '\u0000' through * '\uFFFF' is returned with a probability of 1/2¹⁶. * * @return Character value in the range '\u0000' through * '\uFFFF' inclusive. */ public char nextCharacter() { return (char) next(); } /** * Return the character value from the next pseudorandom value the given * number of positions ahead in this PRNG's sequence. Each value in the * range '\u0000' through '\uFFFF' is returned * with a probability of 1/2¹⁶. * * @param skip Number of positions to skip. * * @return Character value in the range '\u0000' through * '\uFFFF' inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public int nextCharacter (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextCharacter(): skip = " + skip + " illegal"); } return (char) next (skip); } /** * Return the short value from the next pseudorandom value in this PRNG's * sequence. Each value in the range −32768 through 32767 is returned * with a probability of 1/2¹⁶. * * @return Short value in the range −32768 through 32767 inclusive. */ public short nextShort() { return (short) next(); } /** * Return the short value from the next pseudorandom value the given number * of positions ahead in this PRNG's sequence. Each value in the range * −32768 through 32767 is returned with a probability of * 1/2¹⁶. * * @param skip Number of positions to skip. * * @return Short value in the range −32768 through 32767 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public short nextShort (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextShort(): skip = " + skip + " illegal"); } return (short) next (skip); } /** * Return the unsigned short value from the next pseudorandom value in this * PRNG's sequence. Each value in the range 0 through 65535 is returned with * a probability of 1/2¹⁶. * * @return Unsigned short value (as an int) in the range 0 through * 65535 inclusive. */ public int nextUnsignedShort() { return (int) (next() & 0xFFFFL); } /** * Return the unsigned short value from the next pseudorandom value the * given number of positions ahead in this PRNG's sequence. Each value in * the range 0 through 65535 is returned with a probability of * 1/2¹⁶. * * @param skip Number of positions to skip. * * @return Unsigned short value (as an int) in the range 0 through * 65535 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public int nextUnsignedShort (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextUnsignedShort(): skip = " + skip + " illegal"); } return (int) (next (skip) & 0xFFFFL); } /** * Return the integer value from the next pseudorandom value in this PRNG's * sequence. Each value in the range −2147483648 through 2147483647 is * returned with a probability of 1/2³². * * @return Integer value in the range −2147483648 through 2147483647 * inclusive. */ public int nextInteger() { return (int) next(); } /** * Return the integer value from the next pseudorandom value the given * number of positions ahead in this PRNG's sequence. Each value in the * range −2147483648 through 2147483647 is returned with a probability * of 1/2³². * * @param skip Number of positions to skip. * * @return Integer value in the range −2147483648 through 2147483647 * inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public int nextInteger (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextInteger(): skip = " + skip + " illegal"); } return (int) next (skip); } /** * Return the integer value in the given range from the next pseudorandom * value in this PRNG's sequence. Each value in the range 0 through * N−1 is returned with a probability of 1/N. * * @param n Range of values to return. * * @return Integer value in the range 0 through N−1 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if N <= 0. */ public int nextInt (int n) { if (n <= 0) { throw new IllegalArgumentException ("Random.nextInt(): n = " + n + " illegal"); } return (int) Math.floor (nextDouble() * n); } /** * Return the integer value in the given range from the pseudorandom value * the given number of positions ahead in this PRNG's sequence. Each value * in the range 0 through N−1 is returned with a probability of * 1/N. * * @param n Range of values to return. * @param skip Number of positions to skip. * * @return Integer value in the range 0 through N−1 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if N <= 0. Thrown if * skip <= 0. */ public int nextInt (int n, long skip) { if (n <= 0) { throw new IllegalArgumentException ("Random.nextInt(): n = " + n + " illegal"); } return (int) Math.floor (nextDouble (skip) * n); } /** * Return the long value from the next pseudorandom value in this PRNG's * sequence. Each value in the range −9223372036854775808 through * 9223372036854775807 is returned with a probability of 1/2⁶⁴. * * @return Long value in the range −9223372036854775808 through * 9223372036854775807 inclusive. */ public long nextLong() { return next(); } /** * Return the long value from the next pseudorandom value the given number * of positions ahead in this PRNG's sequence. Each value in the range * −9223372036854775808 through 9223372036854775807 is returned with a * probability of 1/2⁶⁴. * * @param skip Number of positions to skip. * * @return Long value in the range −9223372036854775808 through * 9223372036854775807 inclusive. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public long nextLong (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextLong(): skip = " + skip + " illegal"); } return next (skip); } /** * Return the single precision floating point value from the next * pseudorandom value in this PRNG's sequence. The returned numbers have a * uniform distribution in the range 0.0 (inclusive) to 1.0 (exclusive). * * @return Float value. */ public float nextFloat() { // Next random number is in the range -2^63 .. +2^63 - 1. // Divide by 2^64 yielding a number in the range -0.5 .. +0.5. // Add 0.5 yielding a number in the range 0.0 .. 1.0. return (float) (next()) * F_2_POW_NEG_64 + 0.5f; } /** * Return the single precision floating point value from the pseudorandom * value the given number of positions ahead in this PRNG's sequence. The * returned numbers have a uniform distribution in the range 0.0 (inclusive) * to 1.0 (exclusive). * * @param skip Number of positions to skip. * * @return Float value. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public float nextFloat (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextFloat(): skip = " + skip + " illegal"); } // Next random number is in the range -2^63 .. +2^63 - 1. // Divide by 2^64 yielding a number in the range -0.5 .. +0.5. // Add 0.5 yielding a number in the range 0.0 .. 1.0. return (float) (next (skip)) * F_2_POW_NEG_64 + 0.5f; } /** * Return the double precision floating point value from the next * pseudorandom value in this PRNG's sequence. The returned numbers have a * uniform distribution in the range 0.0 (inclusive) to 1.0 (exclusive). * * @return Double value. */ public double nextDouble() { // Next random number is in the range -2^63 .. +2^63 - 1. // Divide by 2^64 yielding a number in the range -0.5 .. +0.5. // Add 0.5 yielding a number in the range 0.0 .. 1.0. return (double) (next()) * D_2_POW_NEG_64 + 0.5; } /** * Return the double precision floating point value from the pseudorandom * value the given number of positions ahead in this PRNG's sequence. The * returned numbers have a uniform distribution in the range 0.0 (inclusive) * to 1.0 (exclusive). * * @param skip Number of positions to skip. * * @return Double value. * * @exception IllegalArgumentException * (unchecked exception) Thrown if skip <= 0. */ public double nextDouble (long skip) { if (skip <= 0) { throw new IllegalArgumentException ("Random.nextDouble(): skip = " + skip + " illegal"); } // Next random number is in the range -2^63 .. +2^63 - 1. // Divide by 2^64 yielding a number in the range -0.5 .. +0.5. // Add 0.5 yielding a number in the range 0.0 .. 1.0. return (double) (next (skip)) * D_2_POW_NEG_64 + 0.5; } // Hidden operations. /** * Return the next 64-bit pseudorandom value in this PRNG's sequence. * * @return Pseudorandom value. */ protected abstract long next(); /** * Return the 64-bit pseudorandom value the given number of positions ahead * in this PRNG's sequence. * * @param skip Number of positions to skip, assumed to be > 0. * * @return Pseudorandom value. */ protected abstract long next (long skip); }