1 /*
2 * License : The MIT License
3 * Copyright(c) 2022 Olyutorskii
4 */
5
6 package io.github.olyutorskii.aletojio.rng.mwc;
7
8 import io.github.olyutorskii.aletojio.rng.RndInt32;
9 import java.util.Objects;
10
11 /**
12 * lag-r Multiply-with-carry random number generator.
13 *
14 * <p>Random sequence X(n) is derived as follows with parameter a(multiplier), b(divisor).
15 * <ul>
16 * <li>{@code T(n) = a * X(n-r) + C(n-1)}
17 * <li>{@code C(n) = T(n) / b}
18 * <li>{@code X(n) = T(n) mod b}
19 * </ul>
20 *
21 * <p>r is the length of the record that stores past results.
22 * "carry" comes from C(n-1).
23 *
24 * @see <a href="https://en.wikipedia.org/wiki/Multiply-with-carry_pseudorandom_number_generator">
25 * Multiply-with-carry pseudorandom number generator (Wikipedia)
26 * </a>
27 */
28 public class Mwc implements RndInt32 {
29
30 private static final int DEF_RECORDS = 1038;
31 private static final long DEF_MULTIPLIER = 611373678L;
32 private static final long DEF_DIVISOR = 1L << 32;
33
34 private static final int INIT_OLDEST = 0x0000_0001;
35 private static final int INIT_CARRY = 1;
36
37 private static final String ERRMSG_SMALLLEN = "too short records length";
38 private static final String ERRMSG_SMALLMUL = "too small multiplier";
39 private static final String ERRMSG_SMALLDIV = "too small divisor";
40 private static final String ERRMSG_SEEDLEN = "unmatch seeds length";
41
42
43 private final long mul;
44 private final long div;
45
46 private final int[] records;
47 private final int length;
48
49 private int index;
50
51 private long carry;
52
53
54 /**
55 * Constructor.
56 *
57 * <ul>
58 * <li>record length must be greater than 0.
59 * <li>multiplier must be greater than 1.
60 * <li>divisor must be greater than 1.
61 * </ul>
62 *
63 * <p>If you want 32-bit uniformly distributed random numbers,
64 * the divisor must be 2**32, but you can compromise with 2**32 -1.
65 *
66 * @param recLen records length
67 * @param mulArg multiplier
68 * @param divArg divisor
69 * @throws IllegalArgumentException illegal argument
70 */
71 public Mwc(int recLen, long mulArg, long divArg) throws IllegalArgumentException {
72 super();
73
74 if (recLen < 1) {
75 throw new IllegalArgumentException(ERRMSG_SMALLLEN);
76 }
77 if (mulArg < 2L) {
78 throw new IllegalArgumentException(ERRMSG_SMALLMUL);
79 }
80 if (divArg < 2L) {
81 throw new IllegalArgumentException(ERRMSG_SMALLDIV);
82 }
83
84 this.records = new int[recLen];
85 this.length = this.records.length;
86
87 this.index = 0;
88 this.records[this.index] = INIT_OLDEST;
89
90 this.mul = mulArg;
91 this.div = divArg;
92 this.carry = INIT_CARRY;
93
94 return;
95 }
96
97 /**
98 * Constructor.
99 *
100 * <ul>
101 * <li>record length must be greater than 0.
102 * <li>multiplier must be greater than 1.
103 * </ul>
104 *
105 * <p>Default divisor value = 2**32.
106 *
107 * @param recLen records length
108 * @param mulArg multiplier
109 * @throws IllegalArgumentException illegal argument
110 */
111 public Mwc(int recLen, long mulArg) throws IllegalArgumentException {
112 this(recLen, mulArg, DEF_DIVISOR);
113 return;
114 }
115
116 /**
117 * Constructor.
118 *
119 * <ul>
120 * <li>Default record length = 1038
121 * <li>Default multiplier value = 611373678
122 * <li>Default divisor value = 2**32
123 * </ul>
124 *
125 * <p>* Caution : If you don't provide your entropy to seeds,
126 * it takes over million trials until the seed is scrambled.
127 *
128 * @throws IllegalArgumentException illegal argument
129 * @see <a href="http://digitalcommons.wayne.edu/cgi/viewcontent.cgi?article=1725&context=jmasm">
130 * Random Number Generators
131 * </a>
132 */
133 public Mwc() throws IllegalArgumentException {
134 this(DEF_RECORDS, DEF_MULTIPLIER);
135 return;
136 }
137
138
139 /**
140 * Return length of past records.
141 *
142 * @return length of past records
143 */
144 public int getRecords() {
145 return this.length;
146 }
147
148 /**
149 * Return carry value.
150 *
151 * @return carry value
152 */
153 public long getCarry() {
154 return this.carry;
155 }
156
157 /**
158 * Set carry value.
159 *
160 * @param lVal new carry value
161 */
162 public void setCarry(long lVal) {
163 this.carry = lVal;
164 return;
165 }
166
167 /**
168 * Set seeds.
169 *
170 * <p>Seeds length must be same as the result records.
171 *
172 * <p>Younger index represent older results.
173 *
174 * @param seeds seeds
175 * @throws NullPointerException argument is null
176 * @throws IllegalArgumentException size unmatched
177 */
178 public void setSeeds(int... seeds)
179 throws NullPointerException, IllegalArgumentException {
180 Objects.requireNonNull(seeds);
181
182 if (seeds.length != this.length) {
183 throw new IllegalArgumentException(ERRMSG_SEEDLEN);
184 }
185
186 System.arraycopy(seeds, 0, this.records, 0, this.length);
187
188 // [0] is oldest
189 this.index = 0;
190
191 return;
192
193 }
194
195 /**
196 * Get oldest result.
197 *
198 * <p>It's mean X(n-r).
199 *
200 * @return oldest result
201 */
202 protected int getOldest() {
203 // If record-length meets certain conditions,
204 // it can provide fast implementations such as bit-mask.
205 int result = this.records[this.index];
206 return result;
207 }
208
209 /**
210 * Push latest result.
211 *
212 * <p>The oldest result at this time is lost.
213 *
214 * @param iVal latest result
215 */
216 protected void pushLatest(int iVal) {
217 // If record-length meets certain conditions,
218 // it can provide fast implementations such as bit-mask.
219 this.records[this.index++] = iVal;
220 if (this.index >= this.length) {
221 this.index = 0;
222 }
223 return;
224 }
225
226 /**
227 * Function that takes oldest result and last carry as arguments
228 * and returns T-value.
229 *
230 * @param oldest oldest result
231 * @param lastCarry last carry
232 * @return T-value
233 */
234 protected long funcTval(long oldest, long lastCarry) {
235 long result = this.mul * oldest + lastCarry;
236 return result;
237 }
238
239 /**
240 * Function that takes T-value as an argument and returns random result.
241 *
242 * @param tVal T-value
243 * @return random result
244 */
245 protected int funcRndFromTval(long tVal) {
246 // If divisor meets certain conditions,
247 // it can provide fast implementations such as bit-mask.
248 long lVal = tVal % this.div;
249 int result = (int) lVal;
250 return result;
251 }
252
253 /**
254 * Function that takes T-value as an argument and returns carry.
255 *
256 * @param tVal T-value
257 * @return carry
258 */
259 protected long funcCarryFromTval(long tVal) {
260 // If divisor meets certain conditions,
261 // it can provide fast implementations such as right shift.
262 long result = tVal / this.div;
263 return result;
264 }
265
266 /**
267 * {@inheritDoc}
268 *
269 * @return {@inheritDoc}
270 */
271 @Override
272 public int nextInt32() {
273 long oldest = getOldest();
274 long lastCarry = this.carry;
275
276 long tVal = funcTval(oldest, lastCarry);
277
278 int latest = funcRndFromTval(tVal);
279 long newCarry = funcCarryFromTval(tVal);
280
281 pushLatest(latest);
282 this.carry = newCarry;
283
284 return latest;
285 }
286
287 }