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