001/*
002Written in 2015 by Sebastiano Vigna (vigna@acm.org)
003
004To the extent possible under law, the author has dedicated all copyright
005and related and neighboring rights to this software to the public domain
006worldwide. This software is distributed without any warranty.
007
008See <http://creativecommons.org/publicdomain/zero/1.0/>. */
009package squidpony.squidmath;
010
011import squidpony.StringKit;
012
013/**
014 * This is a SplittableRandom-style generator, meant to have a tiny state
015 * that permits storing many different generators with low overhead.
016 * It should be rather fast, though no guarantees can be made on all hardware.
017 * <br>
018 * Benchmarking on a Windows laptop with an i7-4700MQ processor running OpenJDK 8
019 * reports generation of 64-bit random long output as 17.8x faster than generating
020 * an equivalent number of random longs with java.util.Random, and generation of
021 * 32-bit random int output as 9.8x faster. Specifically, generating 1 billion longs
022 * took about 1.28 nanoseconds per long (1.277 seconds for the whole group) with
023 * LightRNG, while java.util.Random (which is meant to produce int, to be fair) took
024 * about 22.8 nanoseconds per long (22.797 seconds for the whole group). XorRNG
025 * appears to be occasionally faster on int output than LightRNG, but it isn't clear
026 * why or what causes that (JIT or GC internals, possibly). XorRNG is slightly
027 * slower at generating 64-bit random data, including long and double, but not by
028 * a significant degree (a multiplier between 0.9 and 1.2 times). The only deciding
029 * factor then is state size, where LightRNG is as small as possible for any JVM
030 * object with even a single field: 16 bytes (on a 64-bit JVM; 8-byte objects with
031 * 4 bytes or less of non-static members may be possible on 32-bit JVMs but I can't
032 * find anything confirming that guess).
033 * <br>
034 * So yes, this should be very fast, and with only a single long used per LightRNG,
035 * it is about as memory-efficient as these generators get.
036 * <br>
037 * Written in 2015 by Sebastiano Vigna (vigna@acm.org)
038 * @author Sebastiano Vigna
039 * @author Tommy Ettinger
040 */
041public class LightRNG implements RandomnessSource, StatefulRandomness
042{
043        /** 2 raised to the 53, - 1. */
044    private static final long DOUBLE_MASK = ( 1L << 53 ) - 1;
045    /** 2 raised to the -53. */
046    private static final double NORM_53 = 1. / ( 1L << 53 );
047    /** 2 raised to the 24, -1. */
048    private static final long FLOAT_MASK = ( 1L << 24 ) - 1;
049    /** 2 raised to the -24. */
050    private static final double NORM_24 = 1. / ( 1L << 24 );
051
052        private static final long serialVersionUID = -374415589203474497L;
053
054    public long state; /* The state can be seeded with any value. */
055
056    /** Creates a new generator seeded using Math.random. */
057    public LightRNG() {
058        this((long) Math.floor(Math.random() * Long.MAX_VALUE));
059    }
060
061    public LightRNG( final long seed ) {
062        setSeed(seed);
063    }
064
065    @Override
066    public int next( int bits ) {
067        return (int)( nextLong() & ( 1L << bits ) - 1 );
068    }
069
070    /**
071     * Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
072     * @return any long, all 64 bits are random
073     */
074    @Override
075    public long nextLong() {
076        long z = ( state += 0x9E3779B97F4A7C15L );
077        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
078        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
079        return z ^ (z >>> 31);
080    }
081
082    /**
083     * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the
084     * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to
085     * copy the state so it isn't shared, usually, and produce a new value with the same exact state.
086     *
087     * @return a copy of this RandomnessSource
088     */
089    @Override
090    public RandomnessSource copy() {
091        return new LightRNG(state);
092    }
093
094    /**
095     * Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
096     * @return any int, all 32 bits are random
097     */
098    public int nextInt() {
099        return (int)nextLong();
100    }
101
102    /**
103     * Exclusive on the upper bound.  The lower bound is 0.
104     * @param bound the upper bound; should be positive
105     * @return a random int less than n and at least equal to 0
106     */
107    public int nextInt( final int bound ) {
108        if ( bound <= 0 ) return 0;
109        int threshold = (0x7fffffff - bound + 1) % bound;
110        for (;;) {
111            int bits = (int)(nextLong() & 0x7fffffff);
112            if (bits >= threshold)
113                return bits % bound;
114        }
115    }
116    /**
117     * Inclusive lower, exclusive upper.
118     * @param lower the lower bound, inclusive, can be positive or negative
119     * @param upper the upper bound, exclusive, should be positive, must be greater than lower
120     * @return a random int at least equal to lower and less than upper
121     */
122    public int nextInt( final int lower, final int upper ) {
123        if ( upper - lower <= 0 ) throw new IllegalArgumentException("Upper bound must be greater than lower bound");
124        return lower + nextInt(upper - lower);
125    }
126
127    /**
128     * Exclusive on the upper bound. The lower bound is 0.
129     * @param bound the upper bound; should be positive
130     * @return a random long less than n
131     */
132    public long nextLong( final long bound ) {
133        if ( bound <= 0 ) return 0;
134        long threshold = (0x7fffffffffffffffL - bound + 1) % bound;
135        for (;;) {
136            long bits = nextLong() & 0x7fffffffffffffffL;
137            if (bits >= threshold)
138                return bits % bound;
139        }
140    }
141
142    /**
143     * Inclusive lower, exclusive upper.
144     * @param lower the lower bound, inclusive, can be positive or negative
145     * @param upper the upper bound, exclusive, should be positive, must be greater than lower
146     * @return a random long at least equal to lower and less than upper
147     */
148    public long nextLong( final long lower, final long upper ) {
149        if ( upper - lower <= 0 )  throw new IllegalArgumentException("Upper bound must be greater than lower bound");
150        return lower + nextLong(upper - lower);
151    }
152    /**
153     * Gets a uniform random double in the range [0.0,1.0)
154     * @return a random double at least equal to 0.0 and less than 1.0
155     */
156    public double nextDouble() {
157        return ( nextLong() & DOUBLE_MASK ) * NORM_53;
158    }
159
160    /**
161     * Gets a uniform random double in the range [0.0,outer) given a positive parameter outer. If outer
162     * is negative, it will be the (exclusive) lower bound and 0.0 will be the (inclusive) upper bound.
163     * @param outer the exclusive outer bound, can be negative
164     * @return a random double between 0.0 (inclusive) and outer (exclusive)
165     */
166    public double nextDouble(final double outer) {
167        return nextDouble() * outer;
168    }
169
170    /**
171     * Gets a uniform random float in the range [0.0,1.0)
172     * @return a random float at least equal to 0.0 and less than 1.0
173     */
174    public float nextFloat() {
175        return (float)( ( nextLong() & FLOAT_MASK ) * NORM_24 );
176    }
177
178    /**
179     * Gets a random value, true or false.
180     * Calls nextLong() once.
181     * @return a random true or false value.
182     */
183    public boolean nextBoolean() {
184        return ( nextLong() & 1 ) != 0L;
185    }
186
187    /**
188     * Given a byte array as a parameter, this will fill the array with random bytes (modifying it
189     * in-place). Calls nextLong() {@code Math.ceil(bytes.length / 8.0)} times.
190     * @param bytes a byte array that will have its contents overwritten with random bytes.
191     */
192    public void nextBytes( final byte[] bytes ) {
193        int i = bytes.length, n = 0;
194        while( i != 0 ) {
195            n = Math.min( i, 8 );
196            for ( long bits = nextLong(); n-- != 0; bits >>= 8 ) bytes[ --i ] = (byte)bits;
197        }
198    }
199
200
201
202    /**
203     * Sets the seed of this generator (which is also the current state).
204     * @param seed the seed to use for this LightRNG, as if it was constructed with this seed.
205     */
206    public void setSeed( final long seed ) {
207        state = seed;
208    }
209    /**
210     * Sets the seed (also the current state) of this generator.
211     * @param seed the seed to use for this LightRNG, as if it was constructed with this seed.
212     */
213    @Override
214    public void setState( final long seed ) {
215        state = seed;
216    }
217    /**
218     * Gets the current state of this generator.
219     * @return the current seed of this LightRNG, changed once per call to nextLong()
220     */
221    @Override
222    public long getState() {
223        return state;
224    }
225
226    /**
227     * Advances or rolls back the LightRNG's state without actually generating numbers. Skip forward
228     * or backward a number of steps specified by advance, where a step is equal to one call to nextInt().
229     * @param advance Number of future generations to skip past. Can be negative to backtrack.
230     * @return the state after skipping.
231     */
232    public long skip(long advance)
233    {
234        return state += 0x9E3779B97F4A7C15L * advance;
235    }
236
237
238    @Override
239    public String toString() {
240        return "LightRNG with state 0x" + StringKit.hex(state) + 'L';
241    }
242
243}