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}