1 //******************************************************************************
2 //
3 // File: Random.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.Random
6 //
7 // This Java source file is copyright (C) 2008 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.util;
41
42 import java.io.Serial;
43 import java.io.Serializable;
44 import java.lang.reflect.Constructor;
45
46 /**
47 * Class Random is the abstract base class for a pseudorandom number generator
48 * (PRNG) designed for use in parallel scientific programming. It differs from
49 * class java.util.Random in the following ways:
50 * <UL>
51 * <LI>
52 * Instances can be created by calling a static factory method. The factory
53 * method can take the name of a subclass as an argument and return an instance
54 * of that subclass of class Random. This makes it easier to write a program
55 * that can substitute a different PRNG algorithm at run time. Class {@linkplain
56 * DefaultRandom} provides a default PRNG algorithm.
57 * <BR>
58 * <LI>
59 * Whereas class java.util.Random generates 48-bit numbers under the hood, class
60 * Random generates 64-bit numbers. This makes class Random faster than class
61 * java.util.Random for some operations, notably the <code>nextDouble()</code>
62 * method.
63 * <BR>
64 * <LI>
65 * Whereas the PRNG algorithm in class java.util.Random has a period of about
66 * 2<SUP>48</SUP>, the default PRNG algorithm in class {@linkplain
67 * DefaultRandom} has a period of about 2<SUP>64</SUP>. This lets a parallel
68 * program scale up to larger problem sizes without exhausting the PRNG's
69 * period.
70 * <BR>
71 * <LI>
72 * To support the <I>leapfrogging</I> and <I>sequence splitting</I> techniques
73 * for generating pseudorandom numbers in multiple parallel threads or
74 * processes, class Random includes methods for skipping ahead in the sequence
75 * of generated numbers, without having to generate all the intermediate
76 * numbers.
77 * <BR>
78 * <LI>
79 * To avoid unnecessary thread synchronization overhead, class Random is not
80 * multiple thread safe. It assumes that the surrounding program ensures that
81 * only one thread at a time calls methods on an instance.
82 * </UL>
83 * <P>
84 * Each method for generating a number comes in two versions; for example:
85 * <PRE>
86 * public double nextDouble();
87 * public double nextDouble (long skip);
88 * </PRE> Calling the second version with an argument <code>skip</code> is
89 * equivalent to calling the first version <code>skip</code> times:
90 * <PRE>
91 * Random prng1 = Random.getInstance (1234L);
92 * double x = prng1.nextDouble (1000);
93 * Random prng2 = Random.getInstance (1234L);
94 * double y;
95 * for (int i = 0; i < 1000; ++ i)
96 * y = prng2.nextDouble();
97 * </PRE> At the end of the above code fragment, <code>x</code> and <code>y</code> will
98 * have the same value. However, calling <code>nextDouble(1000)</code> will
99 * typically be much faster than calling <code>nextDouble()</code> 1000 times.
100 * Conversely,
101 * <code>nextDouble(1)</code> is equivalent to <code>nextDouble()</code>, but the former
102 * will typically be slower than the latter.
103 * <P>
104 * An instance of class Random can be serialized; for example, to checkpoint the
105 * state of the PRNG into a file and restore its state later.
106 * <P>
107 * The design of class Random is inspired in part by Coddington's JAPARA
108 * library. For further information, see P. Coddington and A. Newell, JAPARA --
109 * A Java random number generator library for high-performance computing, in
110 * <I>Proceedings of the 18th IEEE International Parallel and Distributed
111 * Processing Symposium (IPDPS'04),</I> April 26-30, 2004, page 156.
112 *
113 * @author Alan Kaminsky
114 * @version 17-Aug-2009
115 */
116 public abstract class Random
117 implements Serializable {
118
119 @Serial
120 private static final long serialVersionUID = 1L;
121
122 // Hidden constants.
123 // 1/2^64, as a float and as a double.
124 private static double D_2_POW_NEG_64;
125 private static float F_2_POW_NEG_64;
126
127 static {
128 double x = 2.0;
129 x *= x; // 2^2
130 x *= x; // 2^4
131 x *= x; // 2^8
132 x *= x; // 2^16
133 x *= x; // 2^32
134 x *= x; // 2^64
135 D_2_POW_NEG_64 = 1.0 / x;
136 F_2_POW_NEG_64 = (float) D_2_POW_NEG_64;
137 }
138
139 // Hidden constructors.
140 /**
141 * Construct a new PRNG.
142 */
143 protected Random() {
144 }
145
146 // Exported operations.
147 /**
148 * Construct a new PRNG with the given seed using the default algorithm.
149 * <P>
150 * If the <code>"pj.prng"</code> Java system property is specified, it gives the
151 * fully-qualified class name of the default PRNG class that the
152 * <code>getInstance()</code> method will construct. Specifying the
153 * <code>"pj.prng"</code> property will substitute a different PRNG algorithm
154 * into a program without needing to recompile.
155 * <P>
156 * If the <code>"pj.prng"</code> Java system property is not specified, the
157 * <code>getInstance()</code> method will return an instance of class
158 * {@linkplain DefaultRandom}.
159 * <P>
160 * You can specify the <code>"pj.prng"</code> property on the Java command line
161 * like this:
162 *
163 * <code> java -Dpj.prng=MyOwnPrngClass . . .</code>
164 * <P>
165 * <I>Note:</I> Depending on the PRNG algorithm, certain seed values may not
166 * be allowed. See the PRNG algorithm subclass for further information.
167 *
168 * @param seed Seed.
169 * @exception IllegalArgumentException (unchecked exception) Thrown if the
170 * PRNG algorithm does not allow the given seed value.
171 * @exception TypeNotPresentException (unchecked exception) Thrown if a PRNG
172 * instance could not be constructed. The chained exception gives further
173 * information about the problem.
174 * @return a {@link edu.rit.util.Random} object.
175 */
176 public static Random getInstance(long seed) {
177 String algorithm = System.getProperty("pj.prng");
178 return algorithm == null
179 ? new DefaultRandom(seed)
180 : getInstance(seed, algorithm);
181 }
182
183 /**
184 * Construct a new PRNG with the given seed using the given algorithm.
185 * <P>
186 * <I>Note:</I> Depending on the PRNG algorithm, certain seed values may not
187 * be allowed. See the PRNG algorithm subclass for further information.
188 *
189 * @param seed Seed.
190 * @param algorithm Fully-qualified name of the class to construct. This
191 * must be a subclass of class Random.
192 * @exception IllegalArgumentException (unchecked exception) Thrown if the
193 * PRNG algorithm does not allow the given seed value.
194 * @exception TypeNotPresentException (unchecked exception) Thrown if a PRNG
195 * instance could not be constructed. The chained exception gives further
196 * information about the problem.
197 * @return a {@link edu.rit.util.Random} object.
198 */
199 public static Random getInstance(long seed,
200 String algorithm) {
201 try {
202 Class<?> cl = Class.forName(algorithm);
203 Constructor<?> ctor = cl.getConstructor(Long.TYPE);
204 return (Random) ctor.newInstance(seed);
205 } catch (Exception exc) {
206 throw new TypeNotPresentException(algorithm, exc);
207 }
208 }
209
210 /**
211 * Set this PRNG's seed.
212 * <P>
213 * <I>Note:</I> Depending on the PRNG algorithm, certain seed values may not
214 * be allowed. See the PRNG algorithm subclass for further information.
215 *
216 * @param seed Seed.
217 * @exception IllegalArgumentException (unchecked exception) Thrown if the
218 * PRNG algorithm does not allow the given seed value.
219 */
220 public abstract void setSeed(long seed);
221
222 /**
223 * Skip one position ahead in this PRNG's sequence.
224 */
225 public void skip() {
226 next();
227 }
228
229 /**
230 * Skip the given number of positions ahead in this PRNG's sequence. If
231 * <code>skip</code> <= 0, the <code>skip()</code> method does nothing.
232 *
233 * @param skip Number of positions to skip.
234 */
235 public void skip(long skip) {
236 if (skip > 0L) {
237 next(skip);
238 }
239 }
240
241 /**
242 * Return the Boolean value from the next pseudorandom value in this PRNG's
243 * sequence. With a probability of 0.5 <code>true</code> is returned, with a
244 * probability of 0.5 <code>false</code> is returned.
245 *
246 * @return Boolean value.
247 */
248 public boolean nextBoolean() {
249 // Use the high-order (sign) bit of the 64-bit random value.
250 return next() >= 0L;
251 }
252
253 /**
254 * Return the Boolean value from the pseudorandom value the given number of
255 * positions ahead in this PRNG's sequence. With a probability of 0.5
256 * <code>true</code> is returned, with a probability of 0.5 <code>false</code> is
257 * returned.
258 *
259 * @param skip Number of positions to skip.
260 * @return Boolean value.
261 * @exception IllegalArgumentException (unchecked exception) Thrown if
262 * <code>skip</code> <= 0.
263 */
264 public boolean nextBoolean(long skip) {
265 if (skip <= 0) {
266 throw new IllegalArgumentException("Random.nextBoolean(): skip = " + skip + " illegal");
267 }
268
269 // Use the high-order (sign) bit of the 64-bit random value.
270 return next(skip) >= 0L;
271 }
272
273 /**
274 * Return the byte value from the next pseudorandom value in this PRNG's
275 * sequence. Each value in the range −128 through 127 is returned with
276 * a probability of 1/2<SUP>8</SUP>.
277 *
278 * @return Byte value in the range −128 through 127 inclusive.
279 */
280 public byte nextByte() {
281 return (byte) next();
282 }
283
284 /**
285 * Return the byte value from the next pseudorandom value the given number
286 * of positions ahead in this PRNG's sequence. Each value in the range
287 * −128 through 127 is returned with a probability of 1/2<SUP>8</SUP>.
288 *
289 * @param skip Number of positions to skip.
290 * @return Byte value in the range −128 through 127 inclusive.
291 * @exception IllegalArgumentException (unchecked exception) Thrown if
292 * <code>skip</code> <= 0.
293 */
294 public byte nextByte(long skip) {
295 if (skip <= 0) {
296 throw new IllegalArgumentException("Random.nextByte(): skip = " + skip + " illegal");
297 }
298 return (byte) next(skip);
299 }
300
301 /**
302 * Return the unsigned byte value from the next pseudorandom value in this
303 * PRNG's sequence. Each value in the range 0 through 255 is returned with a
304 * probability of 1/2<SUP>8</SUP>.
305 *
306 * @return Unsigned byte value (as an <code>int</code>) in the range 0 through
307 * 255 inclusive.
308 */
309 public int nextUnsignedByte() {
310 return (int) (next() & 0xFFL);
311 }
312
313 /**
314 * Return the unsigned byte value from the next pseudorandom value the given
315 * number of positions ahead in this PRNG's sequence. Each value in the
316 * range 0 through 255 is returned with a probability of 1/2<SUP>8</SUP>.
317 *
318 * @param skip Number of positions to skip.
319 * @return Unsigned byte value (as an <code>int</code>) in the range 0 through
320 * 255 inclusive.
321 * @exception IllegalArgumentException (unchecked exception) Thrown if
322 * <code>skip</code> <= 0.
323 */
324 public int nextUnsignedByte(long skip) {
325 if (skip <= 0) {
326 throw new IllegalArgumentException("Random.nextUnsignedByte(): skip = " + skip + " illegal");
327 }
328 return (int) (next(skip) & 0xFFL);
329 }
330
331 /**
332 * Return the character value from the next pseudorandom value in this
333 * PRNG's sequence. Each value in the range <code>'\u0000'</code> through
334 * <code>'\uFFFF'</code> is returned with a probability of 1/2<SUP>16</SUP>.
335 *
336 * @return Character value in the range <code>'\u0000'</code> through
337 * <code>'\uFFFF'</code> inclusive.
338 */
339 public char nextCharacter() {
340 return (char) next();
341 }
342
343 /**
344 * Return the character value from the next pseudorandom value the given
345 * number of positions ahead in this PRNG's sequence. Each value in the
346 * range <code>'\u0000'</code> through <code>'\uFFFF'</code> is returned
347 * with a probability of 1/2<SUP>16</SUP>.
348 *
349 * @param skip Number of positions to skip.
350 * @return Character value in the range <code>'\u0000'</code> through
351 * <code>'\uFFFF'</code> inclusive.
352 * @exception IllegalArgumentException (unchecked exception) Thrown if
353 * <code>skip</code> <= 0.
354 */
355 public int nextCharacter(long skip) {
356 if (skip <= 0) {
357 throw new IllegalArgumentException("Random.nextCharacter(): skip = " + skip + " illegal");
358 }
359 return (char) next(skip);
360 }
361
362 /**
363 * Return the short value from the next pseudorandom value in this PRNG's
364 * sequence. Each value in the range −32768 through 32767 is returned
365 * with a probability of 1/2<SUP>16</SUP>.
366 *
367 * @return Short value in the range −32768 through 32767 inclusive.
368 */
369 public short nextShort() {
370 return (short) next();
371 }
372
373 /**
374 * Return the short value from the next pseudorandom value the given number
375 * of positions ahead in this PRNG's sequence. Each value in the range
376 * −32768 through 32767 is returned with a probability of
377 * 1/2<SUP>16</SUP>.
378 *
379 * @param skip Number of positions to skip.
380 * @return Short value in the range −32768 through 32767 inclusive.
381 * @exception IllegalArgumentException (unchecked exception) Thrown if
382 * <code>skip</code> <= 0.
383 */
384 public short nextShort(long skip) {
385 if (skip <= 0) {
386 throw new IllegalArgumentException("Random.nextShort(): skip = " + skip + " illegal");
387 }
388 return (short) next(skip);
389 }
390
391 /**
392 * Return the unsigned short value from the next pseudorandom value in this
393 * PRNG's sequence. Each value in the range 0 through 65535 is returned with
394 * a probability of 1/2<SUP>16</SUP>.
395 *
396 * @return Unsigned short value (as an <code>int</code>) in the range 0 through
397 * 65535 inclusive.
398 */
399 public int nextUnsignedShort() {
400 return (int) (next() & 0xFFFFL);
401 }
402
403 /**
404 * Return the unsigned short value from the next pseudorandom value the
405 * given number of positions ahead in this PRNG's sequence. Each value in
406 * the range 0 through 65535 is returned with a probability of
407 * 1/2<SUP>16</SUP>.
408 *
409 * @param skip Number of positions to skip.
410 * @return Unsigned short value (as an <code>int</code>) in the range 0 through
411 * 65535 inclusive.
412 * @exception IllegalArgumentException (unchecked exception) Thrown if
413 * <code>skip</code> <= 0.
414 */
415 public int nextUnsignedShort(long skip) {
416 if (skip <= 0) {
417 throw new IllegalArgumentException("Random.nextUnsignedShort(): skip = " + skip + " illegal");
418 }
419 return (int) (next(skip) & 0xFFFFL);
420 }
421
422 /**
423 * Return the integer value from the next pseudorandom value in this PRNG's
424 * sequence. Each value in the range −2147483648 through 2147483647 is
425 * returned with a probability of 1/2<SUP>32</SUP>.
426 *
427 * @return Integer value in the range −2147483648 through 2147483647
428 * inclusive.
429 */
430 public int nextInteger() {
431 return (int) next();
432 }
433
434 /**
435 * Return the integer value from the next pseudorandom value the given
436 * number of positions ahead in this PRNG's sequence. Each value in the
437 * range −2147483648 through 2147483647 is returned with a probability
438 * of 1/2<SUP>32</SUP>.
439 *
440 * @param skip Number of positions to skip.
441 * @return Integer value in the range −2147483648 through 2147483647
442 * inclusive.
443 * @exception IllegalArgumentException (unchecked exception) Thrown if
444 * <code>skip</code> <= 0.
445 */
446 public int nextInteger(long skip) {
447 if (skip <= 0) {
448 throw new IllegalArgumentException("Random.nextInteger(): skip = " + skip + " illegal");
449 }
450 return (int) next(skip);
451 }
452
453 /**
454 * Return the integer value in the given range from the next pseudorandom
455 * value in this PRNG's sequence. Each value in the range 0 through
456 * <I>N</I>−1 is returned with a probability of 1/<I>N</I>.
457 *
458 * @param n Range of values to return.
459 * @return Integer value in the range 0 through <I>N</I>−1 inclusive.
460 * @exception IllegalArgumentException (unchecked exception) Thrown if
461 * <I>N</I> <= 0.
462 */
463 public int nextInt(int n) {
464 if (n <= 0) {
465 throw new IllegalArgumentException("Random.nextInt(): n = " + n + " illegal");
466 }
467 return (int) Math.floor(nextDouble() * n);
468 }
469
470 /**
471 * Return the integer value in the given range from the pseudorandom value
472 * the given number of positions ahead in this PRNG's sequence. Each value
473 * in the range 0 through <I>N</I>−1 is returned with a probability of
474 * 1/<I>N</I>.
475 *
476 * @param n Range of values to return.
477 * @param skip Number of positions to skip.
478 * @return Integer value in the range 0 through <I>N</I>−1 inclusive.
479 * @exception IllegalArgumentException (unchecked exception) Thrown if
480 * <I>N</I> <= 0. Thrown if
481 * <code>skip</code> <= 0.
482 */
483 public int nextInt(int n,
484 long skip) {
485 if (n <= 0) {
486 throw new IllegalArgumentException("Random.nextInt(): n = " + n + " illegal");
487 }
488 return (int) Math.floor(nextDouble(skip) * n);
489 }
490
491 /**
492 * Return the long value from the next pseudorandom value in this PRNG's
493 * sequence. Each value in the range −9223372036854775808 through
494 * 9223372036854775807 is returned with a probability of 1/2<SUP>64</SUP>.
495 *
496 * @return Long value in the range −9223372036854775808 through
497 * 9223372036854775807 inclusive.
498 */
499 public long nextLong() {
500 return next();
501 }
502
503 /**
504 * Return the long value from the next pseudorandom value the given number
505 * of positions ahead in this PRNG's sequence. Each value in the range
506 * −9223372036854775808 through 9223372036854775807 is returned with a
507 * probability of 1/2<SUP>64</SUP>.
508 *
509 * @param skip Number of positions to skip.
510 * @return Long value in the range −9223372036854775808 through
511 * 9223372036854775807 inclusive.
512 * @exception IllegalArgumentException (unchecked exception) Thrown if
513 * <code>skip</code> <= 0.
514 */
515 public long nextLong(long skip) {
516 if (skip <= 0) {
517 throw new IllegalArgumentException("Random.nextLong(): skip = " + skip + " illegal");
518 }
519 return next(skip);
520 }
521
522 /**
523 * Return the single precision floating point value from the next
524 * pseudorandom value in this PRNG's sequence. The returned numbers have a
525 * uniform distribution in the range 0.0 (inclusive) to 1.0 (exclusive).
526 *
527 * @return Float value.
528 */
529 public float nextFloat() {
530 // Next random number is in the range -2^63 .. +2^63 - 1.
531 // Divide by 2^64 yielding a number in the range -0.5 .. +0.5.
532 // Add 0.5 yielding a number in the range 0.0 .. 1.0.
533 return (float) (next()) * F_2_POW_NEG_64 + 0.5f;
534 }
535
536 /**
537 * Return the single precision floating point value from the pseudorandom
538 * value the given number of positions ahead in this PRNG's sequence. The
539 * returned numbers have a uniform distribution in the range 0.0 (inclusive)
540 * to 1.0 (exclusive).
541 *
542 * @param skip Number of positions to skip.
543 * @return Float value.
544 * @exception IllegalArgumentException (unchecked exception) Thrown if
545 * <code>skip</code> <= 0.
546 */
547 public float nextFloat(long skip) {
548 if (skip <= 0) {
549 throw new IllegalArgumentException("Random.nextFloat(): skip = " + skip + " illegal");
550 }
551
552 // Next random number is in the range -2^63 .. +2^63 - 1.
553 // Divide by 2^64 yielding a number in the range -0.5 .. +0.5.
554 // Add 0.5 yielding a number in the range 0.0 .. 1.0.
555 return (float) (next(skip)) * F_2_POW_NEG_64 + 0.5f;
556 }
557
558 /**
559 * Return the double precision floating point value from the next
560 * pseudorandom value in this PRNG's sequence. The returned numbers have a
561 * uniform distribution in the range 0.0 (inclusive) to 1.0 (exclusive).
562 *
563 * @return Double value.
564 */
565 public double nextDouble() {
566 // Next random number is in the range -2^63 .. +2^63 - 1.
567 // Divide by 2^64 yielding a number in the range -0.5 .. +0.5.
568 // Add 0.5 yielding a number in the range 0.0 .. 1.0.
569 return (double) (next()) * D_2_POW_NEG_64 + 0.5;
570 }
571
572 /**
573 * Return the double precision floating point value from the pseudorandom
574 * value the given number of positions ahead in this PRNG's sequence. The
575 * returned numbers have a uniform distribution in the range 0.0 (inclusive)
576 * to 1.0 (exclusive).
577 *
578 * @param skip Number of positions to skip.
579 * @return Double value.
580 * @exception IllegalArgumentException (unchecked exception) Thrown if
581 * <code>skip</code> <= 0.
582 */
583 public double nextDouble(long skip) {
584 if (skip <= 0) {
585 throw new IllegalArgumentException("Random.nextDouble(): skip = " + skip + " illegal");
586 }
587
588 // Next random number is in the range -2^63 .. +2^63 - 1.
589 // Divide by 2^64 yielding a number in the range -0.5 .. +0.5.
590 // Add 0.5 yielding a number in the range 0.0 .. 1.0.
591 return (double) (next(skip)) * D_2_POW_NEG_64 + 0.5;
592 }
593
594 // Hidden operations.
595 /**
596 * Return the next 64-bit pseudorandom value in this PRNG's sequence.
597 *
598 * @return Pseudorandom value.
599 */
600 protected abstract long next();
601
602 /**
603 * Return the 64-bit pseudorandom value the given number of positions ahead
604 * in this PRNG's sequence.
605 *
606 * @param skip Number of positions to skip, assumed to be > 0.
607 * @return Pseudorandom value.
608 */
609 protected abstract long next(long skip);
610
611 }