001/* Written in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org) 002 003To the extent possible under law, the author has dedicated all copyright 004and related and neighboring rights to this software to the public domain 005worldwide. This software is distributed without any warranty. 006 007See <http://creativecommons.org/publicdomain/zero/1.0/>. */ 008package squidpony.squidmath; 009 010import squidpony.StringKit; 011 012/** 013 * A port of Blackman and Vigna's xoroshiro 128+ generator; should be very fast and produce high-quality output. 014 * Testing shows it is within 5% the speed of LightRNG, sometimes faster and sometimes slower, and has a larger period. 015 * It's called XoRo because it involves Xor as well as Rotate operations on the 128-bit pseudo-random state. 016 * Original version at http://xoroshiro.di.unimi.it/xoroshiro128plus.c 017 * Written in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org) 018 * @author Sebastiano Vigna 019 * @author David Blackman 020 * @author Tommy Ettinger 021 */ 022public class XoRoRNG implements RandomnessSource { 023 024 private static final long DOUBLE_MASK = (1L << 53) - 1; 025 private static final double NORM_53 = 1. / (1L << 53); 026 private static final long FLOAT_MASK = (1L << 24) - 1; 027 private static final double NORM_24 = 1. / (1L << 24); 028 029 private static final long serialVersionUID = 1018744536171610261L; 030 031 private long state0, state1; 032 033 /** 034 * Creates a new generator seeded using Math.random. 035 */ 036 public XoRoRNG() { 037 this((long) (Math.random() * Long.MAX_VALUE)); 038 } 039 040 public XoRoRNG(final long seed) { 041 setSeed(seed); 042 } 043 044 @Override 045 public int next(int bits) { 046 return (int) (nextLong() & (1L << bits) - 1); 047 } 048 049 @Override 050 public long nextLong() { 051 final long s0 = state0; 052 long s1 = state1; 053 final long result = s0 + s1; 054 055 s1 ^= s0; 056 state0 = Long.rotateLeft(s0, 55) ^ s1 ^ (s1 << 14); // a, b 057 state1 = Long.rotateLeft(s1, 36); // c 058 059 return result; 060 } 061 062 /** 063 * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the 064 * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to 065 * copy the state so it isn't shared, usually, and produce a new value with the same exact state. 066 * 067 * @return a copy of this RandomnessSource 068 */ 069 @Override 070 public RandomnessSource copy() { 071 XoRoRNG next = new XoRoRNG(state0); 072 next.state0 = state0; 073 next.state1 = state1; 074 return next; 075 } 076 077 078 /** 079 * Can return any int, positive or negative, of any size permissible in a 32-bit signed integer. 080 * @return any int, all 32 bits are random 081 */ 082 public int nextInt() { 083 return (int)nextLong(); 084 } 085 086 /** 087 * Exclusive on the upper bound. The lower bound is 0. 088 * @param bound the upper bound; should be positive 089 * @return a random int less than n and at least equal to 0 090 */ 091 public int nextInt( final int bound ) { 092 if ( bound <= 0 ) return 0; 093 int threshold = (0x7fffffff - bound + 1) % bound; 094 for (;;) { 095 int bits = (int)(nextLong() & 0x7fffffff); 096 if (bits >= threshold) 097 return bits % bound; 098 } 099 } 100 /** 101 * Inclusive lower, exclusive upper. 102 * @param lower the lower bound, inclusive, can be positive or negative 103 * @param upper the upper bound, exclusive, should be positive, must be greater than lower 104 * @return a random int at least equal to lower and less than upper 105 */ 106 public int nextInt( final int lower, final int upper ) { 107 if ( upper - lower <= 0 ) throw new IllegalArgumentException("Upper bound must be greater than lower bound"); 108 return lower + nextInt(upper - lower); 109 } 110 111 /** 112 * Exclusive on the upper bound. The lower bound is 0. 113 * @param bound the upper bound; should be positive 114 * @return a random long less than n 115 */ 116 public long nextLong( final long bound ) { 117 if ( bound <= 0 ) return 0; 118 long threshold = (0x7fffffffffffffffL - bound + 1) % bound; 119 for (;;) { 120 long bits = nextLong() & 0x7fffffffffffffffL; 121 if (bits >= threshold) 122 return bits % bound; 123 } 124 } 125 126 public double nextDouble() { 127 return (nextLong() & DOUBLE_MASK) * NORM_53; 128 } 129 130 public float nextFloat() { 131 return (float) ((nextLong() & FLOAT_MASK) * NORM_24); 132 } 133 134 public boolean nextBoolean() { 135 return (nextLong() & 1) != 0L; 136 } 137 138 public void nextBytes(final byte[] bytes) { 139 int i = bytes.length, n = 0; 140 while (i != 0) { 141 n = Math.min(i, 8); 142 for (long bits = nextLong(); n-- != 0; bits >>= 8) { 143 bytes[--i] = (byte) bits; 144 } 145 } 146 } 147 148 /** 149 * Sets the seed of this generator. Passing this 0 will just set it to -1 150 * instead. 151 * 152 * @param seed the number to use as the seed 153 */ 154 public void setSeed(final long seed) { 155 156 long state = seed + 0x9E3779B97F4A7C15L, 157 z = state; 158 z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; 159 z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; 160 state0 = z ^ (z >>> 31); 161 state = seed + 0x9E3779B97F4A7C15L; 162 z = state; 163 z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; 164 z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; 165 state1 = z ^ (z >>> 31); 166 } 167 168 @Override 169 public String toString() { 170 return "XoRoRNG with state hash 0x" + StringKit.hexHash(state0, state1) + 'L'; 171 } 172}