1 //******************************************************************************
2 //
3 // File: DefaultRandom.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.DefaultRandom
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
44 /**
45 * Class DefaultRandom provides a default pseudorandom number generator (PRNG)
46 * designed for use in parallel scientific programming. To create an instance of
47 * class DefaultRandom, either use the <code>DefaultRandom()</code> constructor, or
48 * use the static <code>getInstance(long)</code> method in class {@linkplain
49 * Random}.
50 * <P>
51 * Class DefaultRandom generates random numbers by hashing successive counter
52 * values. The seed initializes the counter. The hash function is defined in W.
53 * Press et al., <I>Numerical Recipes: The Art of Scientific Computing, Third
54 * Edition</I> (Cambridge University Press, 2007), page 352. The hash function
55 * applied to the counter value <I>i</I> is:
56 * <P>
57 * <I>x</I> := 3935559000370003845 * <I>i</I> + 2691343689449507681 (mod
58 * 2<SUP>64</SUP>)
59 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> right-shift 21)
60 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> left-shift 37)
61 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> right-shift 4)
62 * <BR><I>x</I> := 4768777513237032717 * <I>x</I> (mod 2<SUP>64</SUP>)
63 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> left-shift 20)
64 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> right-shift 41)
65 * <BR><I>x</I> := <I>x</I> xor (<I>x</I> left-shift 5)
66 * <BR>Return <I>x</I>
67 * <P>
68 * (The shift and arithmetic operations are all performed on unsigned 64-bit
69 * numbers.)
70 *
71 * @author Alan Kaminsky
72 * @version 30-Mar-2008
73 */
74 public class DefaultRandom
75 extends Random {
76
77 @Serial
78 private static final long serialVersionUID = 1L;
79
80 // Hidden data members.
81 // Seed for this PRNG.
82 private long seed;
83
84 // 128 bytes of extra padding to avert cache interference.
85 private transient long p0, p1, p2, p3, p4, p5, p6, p7;
86 private transient long p8, p9, pa, pb, pc, pd, pe, pf;
87
88 // Exported constructors.
89 /**
90 * Construct a new PRNG with the given seed. Any seed value is allowed.
91 *
92 * @param seed Seed.
93 */
94 public DefaultRandom(long seed) {
95 setSeed(seed);
96 }
97
98 // Exported operations.
99 /**
100 * {@inheritDoc}
101 *
102 * Set this PRNG's seed. Any seed value is allowed.
103 */
104 public void setSeed(long seed) {
105 this.seed = hash(seed);
106 }
107
108 // Hidden operations.
109 /**
110 * Return the next 64-bit pseudorandom value in this PRNG's sequence.
111 *
112 * @return Pseudorandom value.
113 */
114 protected long next() {
115 ++seed;
116 return hash(seed);
117 }
118
119 /**
120 * {@inheritDoc}
121 *
122 * Return the 64-bit pseudorandom value the given number of positions ahead
123 * in this PRNG's sequence.
124 */
125 protected long next(long skip) {
126 seed += skip;
127 return hash(seed);
128 }
129
130 /**
131 * Return the hash of the given value.
132 */
133 private static long hash(long x) {
134 x = 3935559000370003845L * x + 2691343689449507681L;
135 x = x ^ (x >>> 21);
136 x = x ^ (x << 37);
137 x = x ^ (x >>> 4);
138 x = 4768777513237032717L * x;
139 x = x ^ (x << 20);
140 x = x ^ (x >>> 41);
141 x = x ^ (x << 5);
142 return x;
143 }
144
145 }