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}