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.source64;
19
20 import java.util.Arrays;
21
22 import org.apache.commons.rng.JumpableUniformRandomProvider;
23 import org.apache.commons.rng.UniformRandomProvider;
24 import org.apache.commons.rng.core.util.NumberFactory;
25
26 /**
27 * A fast RNG implementing the {@code XorShift1024*} algorithm.
28 *
29 * <p>Note: This has been superseded by {@link XorShift1024StarPhi}. The sequences emitted
30 * by both generators are correlated.</p>
31 *
32 * @see <a href="http://xorshift.di.unimi.it/xorshift1024star.c">Original source code</a>
33 * @see <a href="https://en.wikipedia.org/wiki/Xorshift">Xorshift (Wikipedia)</a>
34 * @since 1.0
35 */
36 public class XorShift1024Star extends LongProvider implements JumpableUniformRandomProvider {
37 /** Size of the state vector. */
38 private static final int SEED_SIZE = 16;
39 /** The coefficients for the jump function. */
40 private static final long[] JUMP_COEFFICIENTS = {
41 0x84242f96eca9c41dL, 0xa3c65b8776f96855L, 0x5b34a39f070b5837L, 0x4489affce4f31a1eL,
42 0x2ffeeb0a48316f40L, 0xdc2d9891fe68c022L, 0x3659132bb12fea70L, 0xaac17d8efa43cab8L,
43 0xc4cb815590989b13L, 0x5ee975283d71c93bL, 0x691548c86c1bd540L, 0x7910c41d10a1e6a5L,
44 0x0b5fc64563b3e2a8L, 0x047f7684e9fc949dL, 0xb99181f2d8f685caL, 0x284600e3f30e38c3L
45 };
46 /** State. */
47 private final long[] state = new long[SEED_SIZE];
48 /** The multiplier for the XorShift1024 algorithm. */
49 private final long multiplier;
50 /** Index in "state" array. */
51 private int index;
52
53 /**
54 * Creates a new instance.
55 *
56 * @param seed Initial seed.
57 * If the length is larger than 16, only the first 16 elements will
58 * be used; if smaller, the remaining elements will be automatically
59 * set. A seed containing all zeros will create a non-functional generator.
60 */
61 public XorShift1024Star(long[] seed) {
62 this(seed, 1181783497276652981L);
63 }
64
65 /**
66 * Creates a new instance.
67 *
68 * @param seed Initial seed.
69 * If the length is larger than 16, only the first 16 elements will
70 * be used; if smaller, the remaining elements will be automatically
71 * set. A seed containing all zeros will create a non-functional generator.
72 * @param multiplier The multiplier for the XorShift1024 algorithm.
73 * @since 1.3
74 */
75 protected XorShift1024Star(long[] seed, long multiplier) {
76 setSeedInternal(seed);
77 this.multiplier = multiplier;
78 }
79
80 /**
81 * Creates a copy instance.
82 *
83 * @param source Source to copy.
84 * @since 1.3
85 */
86 protected XorShift1024Star(XorShift1024Star source) {
87 super(source);
88 System.arraycopy(source.state, 0, state, 0, SEED_SIZE);
89 multiplier = source.multiplier;
90 index = source.index;
91 }
92
93 /** {@inheritDoc} */
94 @Override
95 protected byte[] getStateInternal() {
96 final long[] s = Arrays.copyOf(state, SEED_SIZE + 1);
97 s[SEED_SIZE] = index;
98
99 return composeStateInternal(NumberFactory.makeByteArray(s),
100 super.getStateInternal());
101 }
102
103 /** {@inheritDoc} */
104 @Override
105 protected void setStateInternal(byte[] s) {
106 final byte[][] c = splitStateInternal(s, (SEED_SIZE + 1) * 8);
107
108 final long[] tmp = NumberFactory.makeLongArray(c[0]);
109 System.arraycopy(tmp, 0, state, 0, SEED_SIZE);
110 index = (int) tmp[SEED_SIZE];
111
112 super.setStateInternal(c[1]);
113 }
114
115 /**
116 * Seeds the RNG.
117 *
118 * @param seed Seed.
119 */
120 private void setSeedInternal(long[] seed) {
121 // Reset the whole state of this RNG (i.e. "state" and "index").
122 // Filling procedure is not part of the reference code.
123 fillState(state, seed);
124 index = 0;
125 }
126
127 /** {@inheritDoc} */
128 @Override
129 public long next() {
130 final long s0 = state[index];
131 index = (index + 1) & 15;
132 long s1 = state[index];
133 s1 ^= s1 << 31; // a
134 state[index] = s1 ^ s0 ^ (s1 >>> 11) ^ (s0 >>> 30); // b,c
135 return state[index] * multiplier;
136 }
137
138 /**
139 * {@inheritDoc}
140 *
141 * <p>The jump size is the equivalent of 2<sup>512</sup>
142 * calls to {@link UniformRandomProvider#nextLong() nextLong()}. It can provide
143 * up to 2<sup>512</sup> non-overlapping subsequences.</p>
144 *
145 * @since 1.3
146 */
147 @Override
148 public UniformRandomProvider jump() {
149 final UniformRandomProvider copy = copy();
150 performJump();
151 return copy;
152 }
153
154 /**
155 * Create a copy.
156 *
157 * @return the copy
158 * @since 1.3
159 */
160 protected XorShift1024Star copy() {
161 // This exists to ensure the jump function returns
162 // the correct class type. It should not be public.
163 return new XorShift1024Star(this);
164 }
165
166 /**
167 * Perform the jump to advance the generator state. Resets the cached state of the generator.
168 */
169 private void performJump() {
170 final long[] newState = new long[SEED_SIZE];
171 for (final long jc : JUMP_COEFFICIENTS) {
172 for (int b = 0; b < 64; b++) {
173 if ((jc & (1L << b)) != 0) {
174 for (int i = 0; i < SEED_SIZE; i++) {
175 newState[i] ^= state[(i + index) & 15];
176 }
177 }
178 next();
179 }
180 }
181 for (int j = 0; j < 16; j++) {
182 state[(j + index) & 15] = newState[j];
183 }
184 resetCachedState();
185 }
186 }