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.stream.Stream; 21 import org.apache.commons.rng.JumpableUniformRandomProvider; 22 import org.apache.commons.rng.SplittableUniformRandomProvider; 23 import org.apache.commons.rng.UniformRandomProvider; 24 import org.apache.commons.rng.core.util.NumberFactory; 25 import org.apache.commons.rng.core.util.RandomStreams; 26 27 /** 28 * A 64-bit all purpose generator. 29 * 30 * <p>This is a member of the LXM family of generators: L=Linear congruential generator; 31 * X=Xor based generator; and M=Mix. This member uses a 64-bit LCG and 1024-bit Xor-based 32 * generator. It is named as {@code "L64X1024MixRandom"} in the {@code java.util.random} 33 * package introduced in JDK 17; the LXM family is described in further detail in: 34 * 35 * <blockquote>Steele and Vigna (2021) LXM: better splittable pseudorandom number generators 36 * (and almost as fast). Proceedings of the ACM on Programming Languages, Volume 5, 37 * Article 148, pp 1–31.</blockquote> 38 * 39 * <p>Memory footprint is 1184 bits and the period is 2<sup>64</sup> (2<sup>1024</sup> - 1). 40 * 41 * <p>This generator implements 42 * {@link org.apache.commons.rng.LongJumpableUniformRandomProvider LongJumpableUniformRandomProvider}. 43 * In addition instances created with a different additive parameter for the LCG are robust 44 * against accidental correlation in a multi-threaded setting. The additive parameters must be 45 * different in the most significant 63-bits. 46 * 47 * <p>This generator implements 48 * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}. 49 * The stream of generators created using the {@code splits} methods support parallelisation 50 * and are robust against accidental correlation by using unique values for the additive parameter 51 * for each instance in the same stream. The primitive streaming methods support parallelisation 52 * but with no assurances of accidental correlation; each thread uses a new instance with a 53 * randomly initialised state. 54 * 55 * @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming 56 * Languages 5, 1-31</a> 57 * @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html"> 58 * JDK 17 java.util.random javadoc</a> 59 * @since 1.5 60 */ 61 public class L64X1024Mix extends AbstractL64 implements SplittableUniformRandomProvider { 62 /** Size of the seed vector. */ 63 private static final int SEED_SIZE = 18; 64 /** Size of the XBG state vector. */ 65 private static final int XBG_STATE_SIZE = 16; 66 /** Size of the LCG state vector. */ 67 private static final int LCG_STATE_SIZE = SEED_SIZE - XBG_STATE_SIZE; 68 /** LCG multiplier. */ 69 private static final long M = LXMSupport.M64; 70 71 /** State of the XBG. */ 72 private final long[] x = new long[XBG_STATE_SIZE]; 73 /** Index in "state" array. */ 74 private int index; 75 76 /** 77 * Creates a new instance. 78 * 79 * @param seed Initial seed. 80 * If the length is larger than 18, only the first 18 elements will 81 * be used; if smaller, the remaining elements will be automatically 82 * set. A seed containing all zeros in the last 16 elements 83 * will create a non-functional XBG sub-generator and a low 84 * quality output with a period of 2<sup>64</sup>. 85 * 86 * <p>The 1st element is used to set the LCG increment; the least significant bit 87 * is set to odd to ensure a full period LCG. The 2nd element is used 88 * to set the LCG state.</p> 89 */ 90 public L64X1024Mix(long[] seed) { 91 super(seed = extendSeed(seed, SEED_SIZE)); 92 System.arraycopy(seed, SEED_SIZE - XBG_STATE_SIZE, x, 0, XBG_STATE_SIZE); 93 // Initialising to 15 ensures that (index + 1) % 16 == 0 and the 94 // first state picked from the XBG generator is state[0]. 95 index = XBG_STATE_SIZE - 1; 96 } 97 98 /** 99 * Creates a copy instance. 100 * 101 * @param source Source to copy. 102 */ 103 protected L64X1024Mix(L64X1024Mix source) { 104 super(source); 105 System.arraycopy(source.x, 0, x, 0, XBG_STATE_SIZE); 106 index = source.index; 107 } 108 109 /** {@inheritDoc} */ 110 @Override 111 protected byte[] getStateInternal() { 112 final long[] s = new long[XBG_STATE_SIZE + 1]; 113 System.arraycopy(x, 0, s, 0, XBG_STATE_SIZE); 114 s[XBG_STATE_SIZE] = index; 115 return composeStateInternal(NumberFactory.makeByteArray(s), 116 super.getStateInternal()); 117 } 118 119 /** {@inheritDoc} */ 120 @Override 121 protected void setStateInternal(byte[] s) { 122 final byte[][] c = splitStateInternal(s, (XBG_STATE_SIZE + 1) * Long.BYTES); 123 124 final long[] tmp = NumberFactory.makeLongArray(c[0]); 125 System.arraycopy(tmp, 0, x, 0, XBG_STATE_SIZE); 126 index = (int) tmp[XBG_STATE_SIZE]; 127 128 super.setStateInternal(c[1]); 129 } 130 131 /** {@inheritDoc} */ 132 @Override 133 public long next() { 134 // LXM generate. 135 // Old state is used for the output allowing parallel pipelining 136 // on processors that support multiple concurrent instructions. 137 138 final int q = index; 139 index = (q + 1) & 15; 140 final long s0 = x[index]; 141 long s15 = x[q]; 142 final long s = ls; 143 144 // Mix 145 final long z = LXMSupport.lea64(s + s0); 146 147 // LCG update 148 ls = M * s + la; 149 150 // XBG update 151 s15 ^= s0; 152 x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27); 153 x[index] = Long.rotateLeft(s15, 36); 154 155 return z; 156 } 157 158 /** 159 * {@inheritDoc} 160 * 161 * <p>The jump size is the equivalent of moving the state <em>backwards</em> by 162 * (2<sup>1024</sup> - 1) positions. It can provide up to 2<sup>64</sup> 163 * non-overlapping subsequences. 164 */ 165 @Override 166 public UniformRandomProvider jump() { 167 return super.jump(); 168 } 169 170 /** 171 * {@inheritDoc} 172 * 173 * <p>The jump size is the equivalent of moving the state <em>backwards</em> by 174 * 2<sup>32</sup> (2<sup>1024</sup> - 1) positions. It can provide up to 175 * 2<sup>32</sup> non-overlapping subsequences of length 2<sup>32</sup> 176 * (2<sup>1024</sup> - 1); each subsequence can provide up to 2<sup>32</sup> 177 * non-overlapping subsequences of length (2<sup>1024</sup> - 1) using the 178 * {@link #jump()} method. 179 */ 180 @Override 181 public JumpableUniformRandomProvider longJump() { 182 return super.longJump(); 183 } 184 185 /** {@inheritDoc} */ 186 @Override 187 AbstractL64 copy() { 188 // This exists to ensure the jump function performed in the super class returns 189 // the correct class type. It should not be public. 190 return new L64X1024Mix(this); 191 } 192 193 /** {@inheritDoc} */ 194 @Override 195 public SplittableUniformRandomProvider split(UniformRandomProvider source) { 196 return create(source.nextLong(), source); 197 } 198 199 /** {@inheritDoc} */ 200 @Override 201 public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) { 202 return RandomStreams.generateWithSeed(streamSize, source, L64X1024Mix::create); 203 } 204 205 /** 206 * Create a new instance using the given {@code seed} and {@code source} of randomness 207 * to initialise the instance. 208 * 209 * @param seed Seed used to initialise the instance. 210 * @param source Source of randomness used to initialise the instance. 211 * @return A new instance. 212 */ 213 private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) { 214 final long[] s = new long[SEED_SIZE]; 215 // LCG state. The addition uses the input seed. 216 // The LCG addition parameter is set to odd so left-shift the seed. 217 s[0] = seed << 1; 218 s[1] = source.nextLong(); 219 // XBG state must not be all zero 220 long x = 0; 221 for (int i = LCG_STATE_SIZE; i < s.length; i++) { 222 s[i] = source.nextLong(); 223 x |= s[i]; 224 } 225 if (x == 0) { 226 // SplitMix style seed ensures at least one non-zero value 227 x = s[LCG_STATE_SIZE - 1]; 228 for (int i = LCG_STATE_SIZE; i < s.length; i++) { 229 s[i] = LXMSupport.lea64(x); 230 x += LXMSupport.GOLDEN_RATIO_64; 231 } 232 } 233 return new L64X1024Mix(s); 234 } 235 }