1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Package rand implements pseudo-random number generators. 6 // 7 // Random numbers are generated by a Source. Top-level functions, such as 8 // Float64 and Int, use a default shared Source that produces a deterministic 9 // sequence of values each time a program is run. Use the Seed function to 10 // initialize the default Source if different behavior is required for each run. 11 // The default Source is safe for concurrent use by multiple goroutines, but 12 // Sources created by NewSource are not. 13 // 14 // Mathematical interval notation such as [0, n) is used throughout the 15 // documentation for this package. 16 // 17 // For random numbers suitable for security-sensitive work, see the crypto/rand 18 // package. 19 package rand 20 21 import "sync" 22 23 // A Source represents a source of uniformly-distributed 24 // pseudo-random int64 values in the range [0, 1<<63). 25 type Source interface { 26 Int63() int64 27 Seed(seed int64) 28 } 29 30 // A Source64 is a Source that can also generate 31 // uniformly-distributed pseudo-random uint64 values in 32 // the range [0, 1<<64) directly. 33 // If a Rand r's underlying Source s implements Source64, 34 // then r.Uint64 returns the result of one call to s.Uint64 35 // instead of making two calls to s.Int63. 36 type Source64 interface { 37 Source 38 Uint64() uint64 39 } 40 41 // NewSource returns a new pseudo-random Source seeded with the given value. 42 // Unlike the default Source used by top-level functions, this source is not 43 // safe for concurrent use by multiple goroutines. 44 func NewSource(seed int64) Source { 45 var rng rngSource 46 rng.Seed(seed) 47 return &rng 48 } 49 50 // A Rand is a source of random numbers. 51 type Rand struct { 52 src Source 53 s64 Source64 // non-nil if src is source64 54 55 // readVal contains remainder of 63-bit integer used for bytes 56 // generation during most recent Read call. 57 // It is saved so next Read call can start where the previous 58 // one finished. 59 readVal int64 60 // readPos indicates the number of low-order bytes of readVal 61 // that are still valid. 62 readPos int8 63 } 64 65 // New returns a new Rand that uses random values from src 66 // to generate other random values. 67 func New(src Source) *Rand { 68 s64, _ := src.(Source64) 69 return &Rand{src: src, s64: s64} 70 } 71 72 // Seed uses the provided seed value to initialize the generator to a deterministic state. 73 // Seed should not be called concurrently with any other Rand method. 74 func (r *Rand) Seed(seed int64) { 75 if lk, ok := r.src.(*lockedSource); ok { 76 lk.seedPos(seed, &r.readPos) 77 return 78 } 79 80 r.src.Seed(seed) 81 r.readPos = 0 82 } 83 84 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64. 85 func (r *Rand) Int63() int64 { return r.src.Int63() } 86 87 // Uint32 returns a pseudo-random 32-bit value as a uint32. 88 func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) } 89 90 // Uint64 returns a pseudo-random 64-bit value as a uint64. 91 func (r *Rand) Uint64() uint64 { 92 if r.s64 != nil { 93 return r.s64.Uint64() 94 } 95 return uint64(r.Int63())>>31 | uint64(r.Int63())<<32 96 } 97 98 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32. 99 func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) } 100 101 // Int returns a non-negative pseudo-random int. 102 func (r *Rand) Int() int { 103 u := uint(r.Int63()) 104 return int(u << 1 >> 1) // clear sign bit if int == int32 105 } 106 107 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n). 108 // It panics if n <= 0. 109 func (r *Rand) Int63n(n int64) int64 { 110 if n <= 0 { 111 panic("invalid argument to Int63n") 112 } 113 if n&(n-1) == 0 { // n is power of two, can mask 114 return r.Int63() & (n - 1) 115 } 116 max := int64((1 << 63) - 1 - (1<<63)%uint64(n)) 117 v := r.Int63() 118 for v > max { 119 v = r.Int63() 120 } 121 return v % n 122 } 123 124 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n). 125 // It panics if n <= 0. 126 func (r *Rand) Int31n(n int32) int32 { 127 if n <= 0 { 128 panic("invalid argument to Int31n") 129 } 130 if n&(n-1) == 0 { // n is power of two, can mask 131 return r.Int31() & (n - 1) 132 } 133 max := int32((1 << 31) - 1 - (1<<31)%uint32(n)) 134 v := r.Int31() 135 for v > max { 136 v = r.Int31() 137 } 138 return v % n 139 } 140 141 // int31n returns, as an int32, a non-negative pseudo-random number in [0,n). 142 // n must be > 0, but int31n does not check this; the caller must ensure it. 143 // int31n exists because Int31n is inefficient, but Go 1 compatibility 144 // requires that the stream of values produced by math/rand remain unchanged. 145 // int31n can thus only be used internally, by newly introduced APIs. 146 // 147 // For implementation details, see: 148 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction 149 // https://lemire.me/blog/2016/06/30/fast-random-shuffling 150 func (r *Rand) int31n(n int32) int32 { 151 v := r.Uint32() 152 prod := uint64(v) * uint64(n) 153 low := uint32(prod) 154 if low < uint32(n) { 155 thresh := uint32(-n) % uint32(n) 156 for low < thresh { 157 v = r.Uint32() 158 prod = uint64(v) * uint64(n) 159 low = uint32(prod) 160 } 161 } 162 return int32(prod >> 32) 163 } 164 165 // Intn returns, as an int, a non-negative pseudo-random number in [0,n). 166 // It panics if n <= 0. 167 func (r *Rand) Intn(n int) int { 168 if n <= 0 { 169 panic("invalid argument to Intn") 170 } 171 if n <= 1<<31-1 { 172 return int(r.Int31n(int32(n))) 173 } 174 return int(r.Int63n(int64(n))) 175 } 176 177 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0). 178 func (r *Rand) Float64() float64 { 179 // A clearer, simpler implementation would be: 180 // return float64(r.Int63n(1<<53)) / (1<<53) 181 // However, Go 1 shipped with 182 // return float64(r.Int63()) / (1 << 63) 183 // and we want to preserve that value stream. 184 // 185 // There is one bug in the value stream: r.Int63() may be so close 186 // to 1<<63 that the division rounds up to 1.0, and we've guaranteed 187 // that the result is always less than 1.0. 188 // 189 // We tried to fix this by mapping 1.0 back to 0.0, but since float64 190 // values near 0 are much denser than near 1, mapping 1 to 0 caused 191 // a theoretically significant overshoot in the probability of returning 0. 192 // Instead of that, if we round up to 1, just try again. 193 // Getting 1 only happens 1/2⁵³ of the time, so most clients 194 // will not observe it anyway. 195 again: 196 f := float64(r.Int63()) / (1 << 63) 197 if f == 1 { 198 goto again // resample; this branch is taken O(never) 199 } 200 return f 201 } 202 203 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0). 204 func (r *Rand) Float32() float32 { 205 // Same rationale as in Float64: we want to preserve the Go 1 value 206 // stream except we want to fix it not to return 1.0 207 // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64). 208 again: 209 f := float32(r.Float64()) 210 if f == 1 { 211 goto again // resample; this branch is taken O(very rarely) 212 } 213 return f 214 } 215 216 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n). 217 func (r *Rand) Perm(n int) []int { 218 m := make([]int, n) 219 // In the following loop, the iteration when i=0 always swaps m[0] with m[0]. 220 // A change to remove this useless iteration is to assign 1 to i in the init 221 // statement. But Perm also effects r. Making this change will affect 222 // the final state of r. So this change can't be made for compatibility 223 // reasons for Go 1. 224 for i := 0; i < n; i++ { 225 j := r.Intn(i + 1) 226 m[i] = m[j] 227 m[j] = i 228 } 229 return m 230 } 231 232 // Shuffle pseudo-randomizes the order of elements. 233 // n is the number of elements. Shuffle panics if n < 0. 234 // swap swaps the elements with indexes i and j. 235 func (r *Rand) Shuffle(n int, swap func(i, j int)) { 236 if n < 0 { 237 panic("invalid argument to Shuffle") 238 } 239 240 // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle 241 // Shuffle really ought not be called with n that doesn't fit in 32 bits. 242 // Not only will it take a very long time, but with 2³¹! possible permutations, 243 // there's no way that any PRNG can have a big enough internal state to 244 // generate even a minuscule percentage of the possible permutations. 245 // Nevertheless, the right API signature accepts an int n, so handle it as best we can. 246 i := n - 1 247 for ; i > 1<<31-1-1; i-- { 248 j := int(r.Int63n(int64(i + 1))) 249 swap(i, j) 250 } 251 for ; i > 0; i-- { 252 j := int(r.int31n(int32(i + 1))) 253 swap(i, j) 254 } 255 } 256 257 // Read generates len(p) random bytes and writes them into p. It 258 // always returns len(p) and a nil error. 259 // Read should not be called concurrently with any other Rand method. 260 func (r *Rand) Read(p []byte) (n int, err error) { 261 if lk, ok := r.src.(*lockedSource); ok { 262 return lk.read(p, &r.readVal, &r.readPos) 263 } 264 return read(p, r.Int63, &r.readVal, &r.readPos) 265 } 266 267 func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, err error) { 268 pos := *readPos 269 val := *readVal 270 for n = 0; n < len(p); n++ { 271 if pos == 0 { 272 val = int63() 273 pos = 7 274 } 275 p[n] = byte(val) 276 val >>= 8 277 pos-- 278 } 279 *readPos = pos 280 *readVal = val 281 return 282 } 283 284 /* 285 * Top-level convenience functions 286 */ 287 288 var globalRand = New(&lockedSource{src: NewSource(1).(Source64)}) 289 290 // Seed uses the provided seed value to initialize the default Source to a 291 // deterministic state. If Seed is not called, the generator behaves as 292 // if seeded by Seed(1). Seed values that have the same remainder when 293 // divided by 2^31-1 generate the same pseudo-random sequence. 294 // Seed, unlike the Rand.Seed method, is safe for concurrent use. 295 func Seed(seed int64) { globalRand.Seed(seed) } 296 297 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64 298 // from the default Source. 299 func Int63() int64 { return globalRand.Int63() } 300 301 // Uint32 returns a pseudo-random 32-bit value as a uint32 302 // from the default Source. 303 func Uint32() uint32 { return globalRand.Uint32() } 304 305 // Uint64 returns a pseudo-random 64-bit value as a uint64 306 // from the default Source. 307 func Uint64() uint64 { return globalRand.Uint64() } 308 309 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32 310 // from the default Source. 311 func Int31() int32 { return globalRand.Int31() } 312 313 // Int returns a non-negative pseudo-random int from the default Source. 314 func Int() int { return globalRand.Int() } 315 316 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n) 317 // from the default Source. 318 // It panics if n <= 0. 319 func Int63n(n int64) int64 { return globalRand.Int63n(n) } 320 321 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n) 322 // from the default Source. 323 // It panics if n <= 0. 324 func Int31n(n int32) int32 { return globalRand.Int31n(n) } 325 326 // Intn returns, as an int, a non-negative pseudo-random number in [0,n) 327 // from the default Source. 328 // It panics if n <= 0. 329 func Intn(n int) int { return globalRand.Intn(n) } 330 331 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0) 332 // from the default Source. 333 func Float64() float64 { return globalRand.Float64() } 334 335 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0) 336 // from the default Source. 337 func Float32() float32 { return globalRand.Float32() } 338 339 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n) 340 // from the default Source. 341 func Perm(n int) []int { return globalRand.Perm(n) } 342 343 // Shuffle pseudo-randomizes the order of elements using the default Source. 344 // n is the number of elements. Shuffle panics if n < 0. 345 // swap swaps the elements with indexes i and j. 346 func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) } 347 348 // Read generates len(p) random bytes from the default Source and 349 // writes them into p. It always returns len(p) and a nil error. 350 // Read, unlike the Rand.Read method, is safe for concurrent use. 351 func Read(p []byte) (n int, err error) { return globalRand.Read(p) } 352 353 // NormFloat64 returns a normally distributed float64 in the range 354 // [-math.MaxFloat64, +math.MaxFloat64] with 355 // standard normal distribution (mean = 0, stddev = 1) 356 // from the default Source. 357 // To produce a different normal distribution, callers can 358 // adjust the output using: 359 // 360 // sample = NormFloat64() * desiredStdDev + desiredMean 361 // 362 func NormFloat64() float64 { return globalRand.NormFloat64() } 363 364 // ExpFloat64 returns an exponentially distributed float64 in the range 365 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter 366 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source. 367 // To produce a distribution with a different rate parameter, 368 // callers can adjust the output using: 369 // 370 // sample = ExpFloat64() / desiredRateParameter 371 // 372 func ExpFloat64() float64 { return globalRand.ExpFloat64() } 373 374 type lockedSource struct { 375 lk sync.Mutex 376 src Source64 377 } 378 379 func (r *lockedSource) Int63() (n int64) { 380 r.lk.Lock() 381 n = r.src.Int63() 382 r.lk.Unlock() 383 return 384 } 385 386 func (r *lockedSource) Uint64() (n uint64) { 387 r.lk.Lock() 388 n = r.src.Uint64() 389 r.lk.Unlock() 390 return 391 } 392 393 func (r *lockedSource) Seed(seed int64) { 394 r.lk.Lock() 395 r.src.Seed(seed) 396 r.lk.Unlock() 397 } 398 399 // seedPos implements Seed for a lockedSource without a race condition. 400 func (r *lockedSource) seedPos(seed int64, readPos *int8) { 401 r.lk.Lock() 402 r.src.Seed(seed) 403 *readPos = 0 404 r.lk.Unlock() 405 } 406 407 // read implements Read for a lockedSource without a race condition. 408 func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) { 409 r.lk.Lock() 410 n, err = read(p, r.src.Int63, readVal, readPos) 411 r.lk.Unlock() 412 return 413 } 414