1 /******************************************************************************* 2 * Copyright 2011 See AUTHORS file. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 ******************************************************************************/ 16 17 package com.badlogic.gdx.math; 18 19 import java.util.Random; 20 21 /** This class implements the xorshift128+ algorithm that is a very fast, top-quality 64-bit pseudo-random number generator. The 22 * quality of this PRNG is much higher than {@link Random}'s, and its cycle length is 2<sup>128</sup> − 1, which 23 * is more than enough for any single-thread application. More details and algorithms can be found <a 24 * href="http://xorshift.di.unimi.it/">here</a>. 25 * <p> 26 * Instances of RandomXS128 are not thread-safe. 27 * 28 * @author Inferno 29 * @author davebaol */ 30 public class RandomXS128 extends Random { 31 32 /** Normalization constant for double. */ 33 private static final double NORM_DOUBLE = 1.0 / (1L << 53); 34 35 /** Normalization constant for float. */ 36 private static final double NORM_FLOAT = 1.0 / (1L << 24); 37 38 /** The first half of the internal state of this pseudo-random number generator. */ 39 private long seed0; 40 41 /** The second half of the internal state of this pseudo-random number generator. */ 42 private long seed1; 43 44 /** Creates a new random number generator. This constructor sets the seed of the random number generator to a value very likely 45 * to be distinct from any other invocation of this constructor. 46 * <p> 47 * This implementation creates a {@link Random} instance to generate the initial seed. */ 48 public RandomXS128 () { 49 setSeed(new Random().nextLong()); 50 } 51 52 /** Creates a new random number generator using a single {@code long} seed. 53 * @param seed the initial seed */ 54 public RandomXS128 (long seed) { 55 setSeed(seed); 56 } 57 58 /** Creates a new random number generator using two {@code long} seeds. 59 * @param seed0 the first part of the initial seed 60 * @param seed1 the second part of the initial seed */ 61 public RandomXS128 (long seed0, long seed1) { 62 setState(seed0, seed1); 63 } 64 65 /** Returns the next pseudo-random, uniformly distributed {@code long} value from this random number generator's sequence. 66 * <p> 67 * Subclasses should override this, as this is used by all other methods. */ 68 @Override 69 public long nextLong () { 70 long s1 = this.seed0; 71 final long s0 = this.seed1; 72 this.seed0 = s0; 73 s1 ^= s1 << 23; 74 return (this.seed1 = (s1 ^ s0 ^ (s1 >>> 17) ^ (s0 >>> 26))) + s0; 75 } 76 77 /** This protected method is final because, contrary to the superclass, it's not used anymore by the other methods. */ 78 @Override 79 protected final int next (int bits) { 80 return (int)(nextLong() & ((1L << bits) - 1)); 81 } 82 83 /** Returns the next pseudo-random, uniformly distributed {@code int} value from this random number generator's sequence. 84 * <p> 85 * This implementation uses {@link #nextLong()} internally. */ 86 @Override 87 public int nextInt () { 88 return (int)nextLong(); 89 } 90 91 /** Returns a pseudo-random, uniformly distributed {@code int} value between 0 (inclusive) and the specified value (exclusive), 92 * drawn from this random number generator's sequence. 93 * <p> 94 * This implementation uses {@link #nextLong()} internally. 95 * @param n the positive bound on the random number to be returned. 96 * @return the next pseudo-random {@code int} value between {@code 0} (inclusive) and {@code n} (exclusive). */ 97 @Override 98 public int nextInt (final int n) { 99 return (int)nextLong(n); 100 } 101 102 /** Returns a pseudo-random, uniformly distributed {@code long} value between 0 (inclusive) and the specified value (exclusive), 103 * drawn from this random number generator's sequence. The algorithm used to generate the value guarantees that the result is 104 * uniform, provided that the sequence of 64-bit values produced by this generator is. 105 * <p> 106 * This implementation uses {@link #nextLong()} internally. 107 * @param n the positive bound on the random number to be returned. 108 * @return the next pseudo-random {@code long} value between {@code 0} (inclusive) and {@code n} (exclusive). */ 109 public long nextLong (final long n) { 110 if (n <= 0) throw new IllegalArgumentException("n must be positive"); 111 for (;;) { 112 final long bits = nextLong() >>> 1; 113 final long value = bits % n; 114 if (bits - value + (n - 1) >= 0) return value; 115 } 116 } 117 118 /** Returns a pseudo-random, uniformly distributed {@code double} value between 0.0 and 1.0 from this random number generator's 119 * sequence. 120 * <p> 121 * This implementation uses {@link #nextLong()} internally. */ 122 @Override 123 public double nextDouble () { 124 return (nextLong() >>> 11) * NORM_DOUBLE; 125 } 126 127 /** Returns a pseudo-random, uniformly distributed {@code float} value between 0.0 and 1.0 from this random number generator's 128 * sequence. 129 * <p> 130 * This implementation uses {@link #nextLong()} internally. */ 131 @Override 132 public float nextFloat () { 133 return (float)((nextLong() >>> 40) * NORM_FLOAT); 134 } 135 136 /** Returns a pseudo-random, uniformly distributed {@code boolean } value from this random number generator's sequence. 137 * <p> 138 * This implementation uses {@link #nextLong()} internally. */ 139 @Override 140 public boolean nextBoolean () { 141 return (nextLong() & 1) != 0; 142 } 143 144 /** Generates random bytes and places them into a user-supplied byte array. The number of random bytes produced is equal to the 145 * length of the byte array. 146 * <p> 147 * This implementation uses {@link #nextLong()} internally. */ 148 @Override 149 public void nextBytes (final byte[] bytes) { 150 int n = 0; 151 int i = bytes.length; 152 while (i != 0) { 153 n = i < 8 ? i : 8; // min(i, 8); 154 for (long bits = nextLong(); n-- != 0; bits >>= 8) 155 bytes[--i] = (byte)bits; 156 } 157 } 158 159 /** Sets the internal seed of this generator based on the given {@code long} value. 160 * <p> 161 * The given seed is passed twice through a hash function. This way, if the user passes a small value we avoid the short 162 * irregular transient associated with states having a very small number of bits set. 163 * @param seed a nonzero seed for this generator (if zero, the generator will be seeded with {@link Long#MIN_VALUE}). */ 164 @Override 165 public void setSeed (final long seed) { 166 long seed0 = murmurHash3(seed == 0 ? Long.MIN_VALUE : seed); 167 setState(seed0, murmurHash3(seed0)); 168 } 169 170 /** Sets the internal state of this generator. 171 * @param seed0 the first part of the internal state 172 * @param seed1 the second part of the internal state */ 173 public void setState (final long seed0, final long seed1) { 174 this.seed0 = seed0; 175 this.seed1 = seed1; 176 } 177 178 /** 179 * Returns the internal seeds to allow state saving. 180 * @param seed must be 0 or 1, designating which of the 2 long seeds to return 181 * @return the internal seed that can be used in setState 182 */ 183 public long getState(int seed) { 184 return seed == 0 ? seed0 : seed1; 185 } 186 187 private final static long murmurHash3 (long x) { 188 x ^= x >>> 33; 189 x *= 0xff51afd7ed558ccdL; 190 x ^= x >>> 33; 191 x *= 0xc4ceb9fe1a85ec53L; 192 x ^= x >>> 33; 193 194 return x; 195 } 196 197 } 198
