1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.rng.core.source32;
19
20 import org.apache.commons.rng.core.util.NumberFactory;
21
22 import java.util.Arrays;
23
24 /**
25 * Middle Square Weyl Sequence Random Number Generator.
26 *
27 * <p>A fast all-purpose 32-bit generator. Memory footprint is 192 bits and the period is at least
28 * {@code 2^64}.</p>
29 *
30 * <p>Implementation is based on the paper
31 * <a href="https://arxiv.org/abs/1704.00358v3">Middle Square Weyl Sequence RNG</a>.</p>
32 *
33 * @see <a href="https://en.wikipedia.org/wiki/Middle-square_method">Middle Square Method</a>
34 * @since 1.3
35 */
36 public class MiddleSquareWeylSequence extends IntProvider {
37 /** Size of the seed array. */
38 private static final int SEED_SIZE = 3;
39 /**
40 * The default seed.
41 * This has a high quality Weyl increment (containing many bit state transitions).
42 */
43 private static final long[] DEFAULT_SEED =
44 {0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L};
45
46 /** State of the generator. */
47 private long x;
48 /** State of the Weyl sequence. */
49 private long w;
50 /**
51 * Increment for the Weyl sequence. This must be odd to ensure a full period.
52 *
53 * <p>This is not final to support the restore functionality.</p>
54 */
55 private long s;
56
57 /**
58 * Creates a new instance.
59 *
60 * <p>Note: The generator output quality is highly dependent on the initial seed.
61 * If the generator is seeded poorly (for example with all zeros) it is possible the
62 * generator may output zero for many cycles before the internal state recovers randomness.
63 * The seed elements are used to set:</p>
64 *
65 * <ol>
66 * <li>The state of the generator
67 * <li>The state of the Weyl sequence
68 * <li>The increment of the Weyl sequence
69 * </ol>
70 *
71 * <p>The third element is set to odd to ensure a period of at least 2<sup>64</sup>. If the
72 * increment is of low complexity then the Weyl sequence does not contribute high quality
73 * randomness. It is recommended to use a permutation of 8 hex characters for the upper
74 * and lower 32-bits of the increment.</p>
75 *
76 * <p>The state of the generator is squared during each cycle. There is a possibility that
77 * different seeds can produce the same output, for example 0 and 2<sup>32</sup> produce
78 * the same square. This can be avoided by using the high complexity Weyl increment for the
79 * state seed element.</p>
80 *
81 * @param seed Initial seed.
82 * If the length is larger than 3, only the first 3 elements will
83 * be used; if smaller, the remaining elements will be automatically set.
84 */
85 public MiddleSquareWeylSequence(long[] seed) {
86 if (seed.length < SEED_SIZE) {
87 // Complete the seed with a default to avoid
88 // low complexity Weyl increments.
89 final long[] tmp = Arrays.copyOf(seed, SEED_SIZE);
90 System.arraycopy(DEFAULT_SEED, seed.length, tmp, seed.length, SEED_SIZE - seed.length);
91 setSeedInternal(tmp);
92 } else {
93 setSeedInternal(seed);
94 }
95 }
96
97 /**
98 * Seeds the RNG.
99 *
100 * @param seed Seed.
101 */
102 private void setSeedInternal(long[] seed) {
103 x = seed[0];
104 w = seed[1];
105 // Ensure the increment is odd to provide a maximal period Weyl sequence.
106 this.s = seed[2] | 1L;
107 }
108
109 /** {@inheritDoc} */
110 @Override
111 protected byte[] getStateInternal() {
112 return composeStateInternal(NumberFactory.makeByteArray(new long[] {x, w, s}),
113 super.getStateInternal());
114 }
115
116 /** {@inheritDoc} */
117 @Override
118 protected void setStateInternal(byte[] state) {
119 final byte[][] c = splitStateInternal(state, SEED_SIZE * 8);
120 setSeedInternal(NumberFactory.makeLongArray(c[0]));
121 super.setStateInternal(c[1]);
122 }
123
124 /** {@inheritDoc} */
125 @Override
126 public int next() {
127 x *= x;
128 x += w += s;
129 x = (x >>> 32) | (x << 32);
130 return (int) x;
131 }
132
133 /** {@inheritDoc} */
134 @Override
135 public long nextLong() {
136 // Avoid round trip from long to int to long by performing two iterations inline
137 x *= x;
138 x += w += s;
139 final long i1 = x & 0xffffffff00000000L;
140 x = (x >>> 32) | (x << 32);
141 x *= x;
142 x += w += s;
143 final long i2 = x >>> 32;
144 x = i2 | x << 32;
145 return i1 | i2;
146 }
147 }