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 // randseednop controls whether the global Seed is a no-op. 317 var randseednop = godebug.New("randseednop") 318 319 // globalRand returns the generator to use for the top-level convenience 320 // functions. 321 func globalRand() *Rand { 322 if r := globalRandGenerator.Load(); r != nil { 323 return r 324 } 325 326 // This is the first call. Initialize based on GODEBUG. 327 var r *Rand 328 if randautoseed.Value() == "0" { 329 randautoseed.IncNonDefault() 330 r = New(new(lockedSource)) 331 r.Seed(1) 332 } else { 333 r = &Rand{ 334 src: &runtimeSource{}, 335 s64: &runtimeSource{}, 336 } 337 } 338 339 if !globalRandGenerator.CompareAndSwap(nil, r) { 340 // Two different goroutines called some top-level 341 // function at the same time. While the results in 342 // that case are unpredictable, if we just use r here, 343 // and we are using a seed, we will most likely return 344 // the same value for both calls. That doesn't seem ideal. 345 // Just use the first one to get in. 346 return globalRandGenerator.Load() 347 } 348 349 return r 350 } 351 352 //go:linkname runtime_rand runtime.rand 353 func runtime_rand() uint64 354 355 // runtimeSource is an implementation of Source64 that uses the runtime 356 // fastrand functions. 357 type runtimeSource struct { 358 // The mutex is used to avoid race conditions in Read. 359 mu sync.Mutex 360 } 361 362 func (*runtimeSource) Int63() int64 { 363 return int64(runtime_rand() & rngMask) 364 } 365 366 func (*runtimeSource) Seed(int64) { 367 panic("internal error: call to runtimeSource.Seed") 368 } 369 370 func (*runtimeSource) Uint64() uint64 { 371 return runtime_rand() 372 } 373 374 func (fs *runtimeSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) { 375 fs.mu.Lock() 376 n, err = read(p, fs, readVal, readPos) 377 fs.mu.Unlock() 378 return 379 } 380 381 // Seed uses the provided seed value to initialize the default Source to a 382 // deterministic state. Seed values that have the same remainder when 383 // divided by 2³¹-1 generate the same pseudo-random sequence. 384 // Seed, unlike the [Rand.Seed] method, is safe for concurrent use. 385 // 386 // If Seed is not called, the generator is seeded randomly at program startup. 387 // 388 // Prior to Go 1.20, the generator was seeded like Seed(1) at program startup. 389 // To force the old behavior, call Seed(1) at program startup. 390 // Alternately, set GODEBUG=randautoseed=0 in the environment 391 // before making any calls to functions in this package. 392 // 393 // Deprecated: As of Go 1.20 there is no reason to call Seed with 394 // a random value. Programs that call Seed with a known value to get 395 // a specific sequence of results should use New(NewSource(seed)) to 396 // obtain a local random generator. 397 // 398 // As of Go 1.24 [Seed] is a no-op. To restore the previous behavior set 399 // GODEBUG=randseednop=0. 400 func Seed(seed int64) { 401 if randseednop.Value() != "0" { 402 return 403 } 404 randseednop.IncNonDefault() 405 406 orig := globalRandGenerator.Load() 407 408 // If we are already using a lockedSource, we can just re-seed it. 409 if orig != nil { 410 if _, ok := orig.src.(*lockedSource); ok { 411 orig.Seed(seed) 412 return 413 } 414 } 415 416 // Otherwise either 417 // 1) orig == nil, which is the normal case when Seed is the first 418 // top-level function to be called, or 419 // 2) orig is already a runtimeSource, in which case we need to change 420 // to a lockedSource. 421 // Either way we do the same thing. 422 423 r := New(new(lockedSource)) 424 r.Seed(seed) 425 426 if !globalRandGenerator.CompareAndSwap(orig, r) { 427 // Something changed underfoot. Retry to be safe. 428 Seed(seed) 429 } 430 } 431 432 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64 433 // from the default [Source]. 434 func Int63() int64 { return globalRand().Int63() } 435 436 // Uint32 returns a pseudo-random 32-bit value as a uint32 437 // from the default [Source]. 438 func Uint32() uint32 { return globalRand().Uint32() } 439 440 // Uint64 returns a pseudo-random 64-bit value as a uint64 441 // from the default [Source]. 442 func Uint64() uint64 { return globalRand().Uint64() } 443 444 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32 445 // from the default [Source]. 446 func Int31() int32 { return globalRand().Int31() } 447 448 // Int returns a non-negative pseudo-random int from the default [Source]. 449 func Int() int { return globalRand().Int() } 450 451 // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n) 452 // from the default [Source]. 453 // It panics if n <= 0. 454 func Int63n(n int64) int64 { return globalRand().Int63n(n) } 455 456 // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n) 457 // from the default [Source]. 458 // It panics if n <= 0. 459 func Int31n(n int32) int32 { return globalRand().Int31n(n) } 460 461 // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n) 462 // from the default [Source]. 463 // It panics if n <= 0. 464 func Intn(n int) int { return globalRand().Intn(n) } 465 466 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0) 467 // from the default [Source]. 468 func Float64() float64 { return globalRand().Float64() } 469 470 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0) 471 // from the default [Source]. 472 func Float32() float32 { return globalRand().Float32() } 473 474 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers 475 // in the half-open interval [0,n) from the default [Source]. 476 func Perm(n int) []int { return globalRand().Perm(n) } 477 478 // Shuffle pseudo-randomizes the order of elements using the default [Source]. 479 // n is the number of elements. Shuffle panics if n < 0. 480 // swap swaps the elements with indexes i and j. 481 func Shuffle(n int, swap func(i, j int)) { globalRand().Shuffle(n, swap) } 482 483 // Read generates len(p) random bytes from the default [Source] and 484 // writes them into p. It always returns len(p) and a nil error. 485 // Read, unlike the [Rand.Read] method, is safe for concurrent use. 486 // 487 // Deprecated: For almost all use cases, [crypto/rand.Read] is more appropriate. 488 // If a deterministic source is required, use [math/rand/v2.ChaCha8.Read]. 489 func Read(p []byte) (n int, err error) { return globalRand().Read(p) } 490 491 // NormFloat64 returns a normally distributed float64 in the range 492 // [-[math.MaxFloat64], +[math.MaxFloat64]] with 493 // standard normal distribution (mean = 0, stddev = 1) 494 // from the default [Source]. 495 // To produce a different normal distribution, callers can 496 // adjust the output using: 497 // 498 // sample = NormFloat64() * desiredStdDev + desiredMean 499 func NormFloat64() float64 { return globalRand().NormFloat64() } 500 501 // ExpFloat64 returns an exponentially distributed float64 in the range 502 // (0, +[math.MaxFloat64]] with an exponential distribution whose rate parameter 503 // (lambda) is 1 and whose mean is 1/lambda (1) from the default [Source]. 504 // To produce a distribution with a different rate parameter, 505 // callers can adjust the output using: 506 // 507 // sample = ExpFloat64() / desiredRateParameter 508 func ExpFloat64() float64 { return globalRand().ExpFloat64() } 509 510 type lockedSource struct { 511 lk sync.Mutex 512 s *rngSource 513 } 514 515 func (r *lockedSource) Int63() (n int64) { 516 r.lk.Lock() 517 n = r.s.Int63() 518 r.lk.Unlock() 519 return 520 } 521 522 func (r *lockedSource) Uint64() (n uint64) { 523 r.lk.Lock() 524 n = r.s.Uint64() 525 r.lk.Unlock() 526 return 527 } 528 529 func (r *lockedSource) Seed(seed int64) { 530 r.lk.Lock() 531 r.seed(seed) 532 r.lk.Unlock() 533 } 534 535 // seedPos implements Seed for a lockedSource without a race condition. 536 func (r *lockedSource) seedPos(seed int64, readPos *int8) { 537 r.lk.Lock() 538 r.seed(seed) 539 *readPos = 0 540 r.lk.Unlock() 541 } 542 543 // seed seeds the underlying source. 544 // The caller must have locked r.lk. 545 func (r *lockedSource) seed(seed int64) { 546 if r.s == nil { 547 r.s = newSource(seed) 548 } else { 549 r.s.Seed(seed) 550 } 551 } 552 553 // read implements Read for a lockedSource without a race condition. 554 func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) { 555 r.lk.Lock() 556 n, err = read(p, r.s, readVal, readPos) 557 r.lk.Unlock() 558 return 559 } 560