001package squidpony.squidmath; 002 003import squidpony.StringKit; 004 005/** 006 * An RNG that has a drastically longer period than the other generators in SquidLib, other than MersenneTwister, 007 * without sacrificing speed or HTML target compatibility. If you don't already know what the period of an RNG is, this 008 * probably isn't needed for your purposes, or many purposes in games at all. It is primarily meant for applications 009 * that need to generate massive amounts of random numbers, more than pow(2, 64) (18,446,744,073,709,551,616), without 010 * repeating sequences of generated numbers. An RNG's period refers to the number of numbers it generates given a single 011 * seed before the sequence repeats from the beginning. The period of this class is pow(2, 1024) minus 1 012 * (179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805,500,963,132,708, 013 * 477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639,474,124,377,767,893,424,865,485, 014 * 276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342,462,881,473,913,110,540,827,237,163,350,510,684, 015 * 586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,215). 016 * This class may be particularly useful in conjunction with the shuffle method of RNG; the period of an RNG determines 017 * how many possible "shuffles", a.k.a orderings or permutations, can be produced over all calls to a permuting method 018 * like shuffle. A LightRNG-backed RNG with a period of pow(2, 64) will only be able to produce all possible "shuffles" 019 * for lists or arrays of 20 items or less. If a LongPeriodRNG is given to the constructor of an RNG and a large enough 020 * state has been given to the LongPeriodRNG (the String or long[] constructors can allow this), then lists or arrays of up 021 * to 170 elements can have all possible orderings produced by shuffle(), though it will take near-impossibly-many calls. 022 * This class has 128 bytes of state plus more in overhead (compare to the 16-byte-with-overhead LightRNG), but due to 023 * its massive period and createMany() static method, you can create a large number of subsequences with rather long 024 * periods themselves from a single seed. This uses the xorshift-1024* algorithm, and has competitive speed. 025 * Created by Tommy Ettinger on 3/21/2016. 026 * Ported from CC0-licensed C code by Sebastiano Vigna, at http://xorshift.di.unimi.it/xorshift1024star.c 027 */ 028public class LongPeriodRNG implements RandomnessSource { 029 030 public long[] state = new long[16]; 031 public int choice; 032 private static final long serialVersionUID = 163524490381383244L; 033 private static final long jumpTable[] = {0x84242f96eca9c41dL, 034 0xa3c65b8776f96855L, 0x5b34a39f070b5837L, 0x4489affce4f31a1eL, 035 0x2ffeeb0a48316f40L, 0xdc2d9891fe68c022L, 0x3659132bb12fea70L, 036 0xaac17d8efa43cab8L, 0xc4cb815590989b13L, 0x5ee975283d71c93bL, 037 0x691548c86c1bd540L, 0x7910c41d10a1e6a5L, 0x0b5fc64563b3e2a8L, 038 0x047f7684e9fc949dL, 0xb99181f2d8f685caL, 0x284600e3f30e38c3L 039 }; 040 041 /** 042 * Builds a LongPeriodRNG and initializes this class' 1024 bits of state with a random seed passed into SplitMix64, 043 * the algorithm also used by LightRNG. A different algorithm is used in non-constructor code to generate random 044 * numbers, which is a recommended technique to generate seeds. 045 */ 046 public LongPeriodRNG() { 047 reseed(); 048 } 049 050 /** 051 * Builds a LongPeriodRNG and initializes this class' 1024 bits of state with many calls to a SplitMix64-based RNG 052 * with a random seed influenced by Math.random() and also the time (in milliseconds to keep GWT compatibility), 053 * mixing Math.random() calls in to alter the SplitMix64 state at uneven intervals. 054 * @param seed a 64-bit seed; can be any value. 055 */ 056 public LongPeriodRNG(long seed) { 057 reseed(seed); 058 } 059 060 public void reseed() 061 { 062 LightRNG lr = new LightRNG(System.currentTimeMillis() ^ 063 (Double.doubleToLongBits(Math.random()) << 32) | 064 (Double.doubleToLongBits(Math.random()) & 0xffffffffL)); 065 long ts = lr.nextLong() ^ lr.nextLong() ^ lr.nextLong(); 066 if (ts == 0) 067 ts++; 068 choice = (int) (ts & 15); 069 state[0] = ts; 070 for (int i = 1; i < 16; i++) { 071 //Chosen by trial and error to unevenly reseed 4 times, where i is 2, 5, 10, or 13 072 if((6 & (i * 1281783497376652987L)) == 6) 073 lr.state ^= (Double.doubleToLongBits(Math.random()) << 32) | 074 (Double.doubleToLongBits(Math.random()) & 0xffffffffL); 075 state[i] = lr.nextLong() ^ lr.nextLong() ^ lr.nextLong(); 076 state[i - 1] ^= state[i]; 077 if(state[i - 1] == 0) state[i - 1]++; 078 } 079 } 080 /** 081 * Reinitializes this class' 1024 bits of state with the given seed passed into SplitMix64, the algorithm also used by 082 * LightRNG. A different algorithm is used in actual number generating code, which is a recommended technique to 083 * generate seeds. 084 * 085 * @param seed a 64-bit seed; can be any value. 086 */ 087 public void reseed(long seed) { 088 state = init(seed); 089 choice = (int) (seed & 15); 090 } 091 /** 092 * Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed, using a different 093 * strategy depending on the seed. If seed is null, this uses the same state as any other null seed. If seed is a 094 * String with length 15 or less, this generates a 64-bit hash of the seed and uses it in the same way the constructor 095 * that takes a long creates 1024 bits of state from a 64-bit seed. If seed is a String with length 16 or more, this 096 * splits the string up and generates 16 hashes from progressively smaller substrings of seed. The highest quality 097 * states will result from passing this a very long String. 098 * 099 * @param seed a String seed; can be any value, but produces the best results if it at least 16 characters long 100 */ 101 public LongPeriodRNG(String seed) { 102 reseed(seed); 103 } 104 105 /** 106 * Reinitializes this class' 1024 bits of state with the given seed, using a different strategy depending on the seed. 107 * If seed is null, this uses the same state as any other null seed. If seed is a String with length 15 or less, this 108 * generates a 64-bit hash of the seed and uses it in the same way the constructor that takes a long creates 1024 bits 109 * of state from a 64-bit seed. If seed is a String with length 16 or more, this splits the string up and generates 16 110 * hashes from progressively smaller substrings of seed. The highest quality states will result from passing this a 111 * very long String. 112 * 113 * @param seed a String seed; can be any value, but produces the best results if it at least 16 characters long 114 */ 115 public void reseed(String seed) 116 { 117 if (seed == null) { 118 state = new long[]{0x0101, 0x1212, 0x2323, 0x3434, 0x4545, 0x5656, 0x6767, 0x7878, 119 0x8989, 0x9A9A, 0xABAB, 0xBCBC, 0xCDCD, 0xDEDE, 0xEFEF, 0xF0F0}; 120 choice = 0; 121 } else { 122 int len = seed.length(); 123 if (len < 16) { 124 long h = CrossHash.hash64(seed); 125 state = init(h); 126 choice = (int) (h & 15); 127 } else { 128 char[] chars = seed.toCharArray(); 129 state = new long[] 130 { 131 validate(CrossHash.hash64(chars)), 132 validate(CrossHash.hash64(chars, len / 16, len)), 133 validate(CrossHash.hash64(chars, 2 * len / 16, len)), 134 validate(CrossHash.hash64(chars, 3 * len / 16, len)), 135 validate(CrossHash.hash64(chars, 4 * len / 16, len)), 136 validate(CrossHash.hash64(chars, 5 * len / 16, len)), 137 validate(CrossHash.hash64(chars, 6 * len / 16, len)), 138 validate(CrossHash.hash64(chars, 7 * len / 16, len)), 139 validate(CrossHash.hash64(chars, 8 * len / 16, len)), 140 validate(CrossHash.hash64(chars, 9 * len / 16, len)), 141 validate(CrossHash.hash64(chars, 10 * len / 16, len)), 142 validate(CrossHash.hash64(chars, 11 * len / 16, len)), 143 validate(CrossHash.hash64(chars, 12 * len / 16, len)), 144 validate(CrossHash.hash64(chars, 13 * len / 16, len)), 145 validate(CrossHash.hash64(chars, 14 * len / 16, len)), 146 validate(CrossHash.hash64(chars, 15 * len / 16, len)), 147 }; 148 choice = (int) (state[0] & 15); 149 } 150 } 151 } 152 /** 153 * Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed as a long array, which 154 * may or may not have 16 elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 155 * bits). If seed is null, this produces the same state as the String constructor does when given a null seed. If seed 156 * has fewer than 16 elements, this repeats earlier elements once it runs out of unused longs. If seed has 16 or more 157 * elements, this exclusive-ors elements after the sixteenth with longs it has already placed into the state, causing 158 * all elements of the seed to have an effect on the state, and making the 16-element case copy all longs exactly. 159 * @param seed a long array seed; can have any number of elements, though 16 is ideal 160 */ 161 public LongPeriodRNG(long[] seed) { 162 reseed(seed); 163 } 164 165 /** 166 * Reinitializes this class' 1024 bits of state with the given seed as a long array, which may or may not have 16 167 * elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 bits). If seed is null, 168 * this produces the same state as the String constructor does when given a null seed. If seed has fewer than 16 169 * elements, this repeats earlier elements once it runs out of unused longs. If seed has 16 or more elements, this 170 * exclusive-ors elements after the sixteenth with longs it has already placed into the state, causing all elements of 171 * the seed to have an effect on the state, and making the 16-element case copy all longs exactly. 172 * @param seed a long array seed; can have any number of elements, though 16 is ideal 173 */ 174 public void reseed(long[] seed) 175 { 176 if (seed == null || seed.length == 0) { 177 state = new long[]{0x0101, 0x1212, 0x2323, 0x3434, 0x4545, 0x5656, 0x6767, 0x7878, 178 0x8989, 0x9A9A, 0xABAB, 0xBCBC, 0xCDCD, 0xDEDE, 0xEFEF, 0xF0F0}; 179 choice = 0; 180 } else if(seed.length < 16) 181 { 182 for (int i = 0, s = 0; i < 16; i++, s = (s+1) % seed.length) { 183 state[i] = seed[s]; 184 if(state[i] == 0) state[i]++; 185 } 186 choice = (int) (state[0] & 15); 187 } 188 else 189 { 190 for (int i = 0, s = 0; s < seed.length; s++, i = (i+1) % 16) { 191 state[i] ^= seed[s]; 192 if(state[i] == 0) state[i]++; 193 } 194 choice = (int) (state[0] & 15); 195 } 196 } 197 198 private static long validate(long seed) 199 { 200 if(seed == 0) return 1; 201 else return seed; 202 } 203 private static long[] init(long seed) 204 { 205 long[] state = new long[16]; 206 for (int i = 0; i < 16; i++) { 207 long z = ( seed += 0x9E3779B97F4A7C15L ); 208 z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; 209 z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; 210 state[i] = z ^ (z >>> 31); 211 if(state[i] == 0) state[i]++; 212 } 213 return state; 214 } 215 public LongPeriodRNG(LongPeriodRNG other) 216 { 217 choice = other.choice; 218 System.arraycopy(other.state, 0, state, 0, 16); 219 } 220 221 @Override 222 public int next( int bits ) { 223 return (int)( nextLong() & ( 1L << bits ) - 1 ); 224 } 225 226 /** 227 * Can return any long, positive or negative, of any size permissible in a 64-bit signed integer. 228 * <br> 229 * Written by Sebastiano Vigna, from http://xorshift.di.unimi.it/xorshift1024star.c 230 * @return any long, all 64 bits are random 231 */ 232 @Override 233 public long nextLong() { 234 final long s0 = state[choice]; 235 long s1 = state[choice = (choice + 1) & 15]; 236 s1 ^= s1 << 31; // a 237 state[choice] = s1 ^ s0 ^ (s1 >> 11) ^ (s0 >> 30); // b,c 238 return state[choice] * 1181783497276652981L; 239 } 240 241 /** 242 * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the 243 * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to 244 * copy the state so it isn't shared, usually, and produce a new value with the same exact state. 245 * 246 * @return a copy of this RandomnessSource 247 */ 248 @Override 249 public RandomnessSource copy() { 250 LongPeriodRNG next = new LongPeriodRNG(); 251 System.arraycopy(state, 0, next.state, 0, 16); 252 next.choice = choice; 253 return next; 254 255 } 256 257 /** 258 * This is the jump function for the generator. It is equivalent to 2^512 calls to nextLong(); it can be used to 259 * generate 2^512 non-overlapping subsequences for parallel computations. Alters the state of this object. 260 * <br> 261 * Written by Sebastiano Vigna, from http://xorshift.di.unimi.it/xorshift1024star.c , don't ask how it works. 262 * */ 263 public void jump() { 264 265 long[] t = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 266 for(int i = 0; i < 16; i++) 267 for(int b = 0; b < 64; b++) { 268 if ((jumpTable[i] & 1L << b) != 0) { 269 for (int j = 0; j < 16; j++) 270 t[j] ^= state[(j + choice) & 15]; 271 } 272 nextLong(); 273 } 274 275 for(int j = 0; j < 16; j++) 276 state[(j + choice) & 15] = t[j]; 277 } 278 279 /** 280 * Creates many LongPeriodRNG objects in an array, where each will generate a sequence of 2 to the 512 numbers that 281 * will not overlap with other sequences in the array. The number of items in the array is specified by count. 282 * @param count the number of LongPeriodRNG objects to generate in the array. 283 * @return an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences. 284 */ 285 public static LongPeriodRNG[] createMany(int count) 286 { 287 if(count < 1) count = 1; 288 LongPeriodRNG origin = new LongPeriodRNG(); 289 LongPeriodRNG[] values = new LongPeriodRNG[count]; 290 for (int i = 0; i < count; i++) { 291 values[i] = new LongPeriodRNG(origin); 292 origin.jump(); 293 } 294 return values; 295 } 296 297 /** 298 * Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that 299 * will not overlap with other sequences in the array. The number of items in the array is specified by count. A 300 * seed can be given that will affect all items in the array, but with each item using a different section of the 301 * massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random 302 * sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given 303 * to this method a different time (useful for testing). 304 * @param count the number of LongPeriodRNG objects to generate in the array. 305 * @param seed the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce 306 * @return an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences. 307 */ 308 public static LongPeriodRNG[] createMany(int count, long seed) 309 { 310 if(count < 1) count = 1; 311 LongPeriodRNG origin = new LongPeriodRNG(seed); 312 LongPeriodRNG[] values = new LongPeriodRNG[count]; 313 for (int i = 0; i < count; i++) { 314 values[i] = new LongPeriodRNG(origin); 315 origin.jump(); 316 } 317 return values; 318 } 319 320 /** 321 * Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that 322 * will not overlap with other sequences in the array. The number of items in the array is specified by count. A 323 * seed can be given that will affect all items in the array, but with each item using a different section of the 324 * massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random 325 * sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given 326 * to this method a different time (useful for testing). 327 * @param count the number of LongPeriodRNG objects to generate in the array. 328 * @param seed the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce 329 * @return an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences. 330 */ 331 public static LongPeriodRNG[] createMany(int count, String seed) 332 { 333 if(count < 1) count = 1; 334 LongPeriodRNG origin = new LongPeriodRNG(seed); 335 LongPeriodRNG[] values = new LongPeriodRNG[count]; 336 for (int i = 0; i < count; i++) { 337 values[i] = new LongPeriodRNG(origin); 338 origin.jump(); 339 } 340 return values; 341 } 342 343 /** 344 * Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that 345 * will not overlap with other sequences in the array. The number of items in the array is specified by count. A 346 * seed can be given that will affect all items in the array, but with each item using a different section of the 347 * massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random 348 * sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given 349 * to this method a different time (useful for testing). 350 * @param count the number of LongPeriodRNG objects to generate in the array. 351 * @param seed the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce 352 * @return an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences. 353 */ 354 public static LongPeriodRNG[] createMany(int count, long[] seed) 355 { 356 if(count < 1) count = 1; 357 LongPeriodRNG origin = new LongPeriodRNG(seed); 358 LongPeriodRNG[] values = new LongPeriodRNG[count]; 359 for (int i = 0; i < count; i++) { 360 values[i] = new LongPeriodRNG(origin); 361 origin.jump(); 362 } 363 return values; 364 } 365 366 367 @Override 368 public String toString() { 369 return "LongPeriodRNG with state hash 0x" + StringKit.hexHash(state) + "L, choice 0x" + StringKit.hex(choice); 370 } 371}