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