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