// Copyright 2009 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. // Package rand implements pseudo-random number generators suitable for tasks // such as simulation, but it should not be used for security-sensitive work. // // Random numbers are generated by a [Source], usually wrapped in a [Rand]. // Both types should be used by a single goroutine at a time: sharing among // multiple goroutines requires some kind of synchronization. // // Top-level functions, such as [Float64] and [Int], // are safe for concurrent use by multiple goroutines. // // This package's outputs might be easily predictable regardless of how it's // seeded. For random numbers suitable for security-sensitive work, see the // crypto/rand package. package rand import ( "internal/godebug" "sync" "sync/atomic" _ "unsafe" // for go:linkname ) // A Source represents a source of uniformly-distributed // pseudo-random int64 values in the range [0, 1<<63). // // A Source is not safe for concurrent use by multiple goroutines. type Source interface { Int63() int64 Seed(seed int64) } // A Source64 is a [Source] that can also generate // uniformly-distributed pseudo-random uint64 values in // the range [0, 1<<64) directly. // If a [Rand] r's underlying [Source] s implements Source64, // then r.Uint64 returns the result of one call to s.Uint64 // instead of making two calls to s.Int63. type Source64 interface { Source Uint64() uint64 } // NewSource returns a new pseudo-random [Source] seeded with the given value. // Unlike the default [Source] used by top-level functions, this source is not // safe for concurrent use by multiple goroutines. // The returned [Source] implements [Source64]. func NewSource(seed int64) Source { return newSource(seed) } func newSource(seed int64) *rngSource { var rng rngSource rng.Seed(seed) return &rng } // A Rand is a source of random numbers. type Rand struct { src Source s64 Source64 // non-nil if src is source64 // readVal contains remainder of 63-bit integer used for bytes // generation during most recent Read call. // It is saved so next Read call can start where the previous // one finished. readVal int64 // readPos indicates the number of low-order bytes of readVal // that are still valid. readPos int8 } // New returns a new [Rand] that uses random values from src // to generate other random values. func New(src Source) *Rand { s64, _ := src.(Source64) return &Rand{src: src, s64: s64} } // Seed uses the provided seed value to initialize the generator to a deterministic state. // Seed should not be called concurrently with any other [Rand] method. func (r *Rand) Seed(seed int64) { if lk, ok := r.src.(*lockedSource); ok { lk.seedPos(seed, &r.readPos) return } r.src.Seed(seed) r.readPos = 0 } // Int63 returns a non-negative pseudo-random 63-bit integer as an int64. func (r *Rand) Int63() int64 { return r.src.Int63() } // Uint32 returns a pseudo-random 32-bit value as a uint32. func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) } // Uint64 returns a pseudo-random 64-bit value as a uint64. func (r *Rand) Uint64() uint64 { if r.s64 != nil { return r.s64.Uint64() } return uint64(r.Int63())>>31 | uint64(r.Int63())<<32 } // Int31 returns a non-negative pseudo-random 31-bit integer as an int32. func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) } // Int returns a non-negative pseudo-random int. func (r *Rand) Int() int { u := uint(r.Int63()) return int(u << 1 >> 1) // clear sign bit if int == int32 } // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n). // It panics if n <= 0. func (r *Rand) Int63n(n int64) int64 { if n <= 0 { panic("invalid argument to Int63n") } if n&(n-1) == 0 { // n is power of two, can mask return r.Int63() & (n - 1) } max := int64((1 << 63) - 1 - (1<<63)%uint64(n)) v := r.Int63() for v > max { v = r.Int63() } return v % n } // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n). // It panics if n <= 0. func (r *Rand) Int31n(n int32) int32 { if n <= 0 { panic("invalid argument to Int31n") } if n&(n-1) == 0 { // n is power of two, can mask return r.Int31() & (n - 1) } max := int32((1 << 31) - 1 - (1<<31)%uint32(n)) v := r.Int31() for v > max { v = r.Int31() } return v % n } // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n). // n must be > 0, but int31n does not check this; the caller must ensure it. // int31n exists because Int31n is inefficient, but Go 1 compatibility // requires that the stream of values produced by math/rand remain unchanged. // int31n can thus only be used internally, by newly introduced APIs. // // For implementation details, see: // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction // https://lemire.me/blog/2016/06/30/fast-random-shuffling func (r *Rand) int31n(n int32) int32 { v := r.Uint32() prod := uint64(v) * uint64(n) low := uint32(prod) if low < uint32(n) { thresh := uint32(-n) % uint32(n) for low < thresh { v = r.Uint32() prod = uint64(v) * uint64(n) low = uint32(prod) } } return int32(prod >> 32) } // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n). // It panics if n <= 0. func (r *Rand) Intn(n int) int { if n <= 0 { panic("invalid argument to Intn") } if n <= 1<<31-1 { return int(r.Int31n(int32(n))) } return int(r.Int63n(int64(n))) } // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0). func (r *Rand) Float64() float64 { // A clearer, simpler implementation would be: // return float64(r.Int63n(1<<53)) / (1<<53) // However, Go 1 shipped with // return float64(r.Int63()) / (1 << 63) // and we want to preserve that value stream. // // There is one bug in the value stream: r.Int63() may be so close // to 1<<63 that the division rounds up to 1.0, and we've guaranteed // that the result is always less than 1.0. // // We tried to fix this by mapping 1.0 back to 0.0, but since float64 // values near 0 are much denser than near 1, mapping 1 to 0 caused // a theoretically significant overshoot in the probability of returning 0. // Instead of that, if we round up to 1, just try again. // Getting 1 only happens 1/2⁵³ of the time, so most clients // will not observe it anyway. again: f := float64(r.Int63()) / (1 << 63) if f == 1 { goto again // resample; this branch is taken O(never) } return f } // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0). func (r *Rand) Float32() float32 { // Same rationale as in Float64: we want to preserve the Go 1 value // stream except we want to fix it not to return 1.0 // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64). again: f := float32(r.Float64()) if f == 1 { goto again // resample; this branch is taken O(very rarely) } return f } // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers // in the half-open interval [0,n). func (r *Rand) Perm(n int) []int { m := make([]int, n) // In the following loop, the iteration when i=0 always swaps m[0] with m[0]. // A change to remove this useless iteration is to assign 1 to i in the init // statement. But Perm also effects r. Making this change will affect // the final state of r. So this change can't be made for compatibility // reasons for Go 1. for i := 0; i < n; i++ { j := r.Intn(i + 1) m[i] = m[j] m[j] = i } return m } // Shuffle pseudo-randomizes the order of elements. // n is the number of elements. Shuffle panics if n < 0. // swap swaps the elements with indexes i and j. func (r *Rand) Shuffle(n int, swap func(i, j int)) { if n < 0 { panic("invalid argument to Shuffle") } // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle // Shuffle really ought not be called with n that doesn't fit in 32 bits. // Not only will it take a very long time, but with 2³¹! possible permutations, // there's no way that any PRNG can have a big enough internal state to // generate even a minuscule percentage of the possible permutations. // Nevertheless, the right API signature accepts an int n, so handle it as best we can. i := n - 1 for ; i > 1<<31-1-1; i-- { j := int(r.Int63n(int64(i + 1))) swap(i, j) } for ; i > 0; i-- { j := int(r.int31n(int32(i + 1))) swap(i, j) } } // Read generates len(p) random bytes and writes them into p. It // always returns len(p) and a nil error. // Read should not be called concurrently with any other Rand method. func (r *Rand) Read(p []byte) (n int, err error) { switch src := r.src.(type) { case *lockedSource: return src.read(p, &r.readVal, &r.readPos) case *runtimeSource: return src.read(p, &r.readVal, &r.readPos) } return read(p, r.src, &r.readVal, &r.readPos) } func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) { pos := *readPos val := *readVal rng, _ := src.(*rngSource) for n = 0; n < len(p); n++ { if pos == 0 { if rng != nil { val = rng.Int63() } else { val = src.Int63() } pos = 7 } p[n] = byte(val) val >>= 8 pos-- } *readPos = pos *readVal = val return } /* * Top-level convenience functions */ // globalRandGenerator is the source of random numbers for the top-level // convenience functions. When possible it uses the runtime fastrand64 // function to avoid locking. This is not possible if the user called Seed, // either explicitly or implicitly via GODEBUG=randautoseed=0. var globalRandGenerator atomic.Pointer[Rand] var randautoseed = godebug.New("randautoseed") // globalRand returns the generator to use for the top-level convenience // functions. func globalRand() *Rand { if r := globalRandGenerator.Load(); r != nil { return r } // This is the first call. Initialize based on GODEBUG. var r *Rand if randautoseed.Value() == "0" { randautoseed.IncNonDefault() r = New(new(lockedSource)) r.Seed(1) } else { r = &Rand{ src: &runtimeSource{}, s64: &runtimeSource{}, } } if !globalRandGenerator.CompareAndSwap(nil, r) { // Two different goroutines called some top-level // function at the same time. While the results in // that case are unpredictable, if we just use r here, // and we are using a seed, we will most likely return // the same value for both calls. That doesn't seem ideal. // Just use the first one to get in. return globalRandGenerator.Load() } return r } //go:linkname runtime_rand runtime.rand func runtime_rand() uint64 // runtimeSource is an implementation of Source64 that uses the runtime // fastrand functions. type runtimeSource struct { // The mutex is used to avoid race conditions in Read. mu sync.Mutex } func (*runtimeSource) Int63() int64 { return int64(runtime_rand() & rngMask) } func (*runtimeSource) Seed(int64) { panic("internal error: call to runtimeSource.Seed") } func (*runtimeSource) Uint64() uint64 { return runtime_rand() } func (fs *runtimeSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) { fs.mu.Lock() n, err = read(p, fs, readVal, readPos) fs.mu.Unlock() return } // Seed uses the provided seed value to initialize the default Source to a // deterministic state. Seed values that have the same remainder when // divided by 2³¹-1 generate the same pseudo-random sequence. // Seed, unlike the [Rand.Seed] method, is safe for concurrent use. // // If Seed is not called, the generator is seeded randomly at program startup. // // Prior to Go 1.20, the generator was seeded like Seed(1) at program startup. // To force the old behavior, call Seed(1) at program startup. // Alternately, set GODEBUG=randautoseed=0 in the environment // before making any calls to functions in this package. // // Deprecated: As of Go 1.20 there is no reason to call Seed with // a random value. Programs that call Seed with a known value to get // a specific sequence of results should use New(NewSource(seed)) to // obtain a local random generator. func Seed(seed int64) { orig := globalRandGenerator.Load() // If we are already using a lockedSource, we can just re-seed it. if orig != nil { if _, ok := orig.src.(*lockedSource); ok { orig.Seed(seed) return } } // Otherwise either // 1) orig == nil, which is the normal case when Seed is the first // top-level function to be called, or // 2) orig is already a runtimeSource, in which case we need to change // to a lockedSource. // Either way we do the same thing. r := New(new(lockedSource)) r.Seed(seed) if !globalRandGenerator.CompareAndSwap(orig, r) { // Something changed underfoot. Retry to be safe. Seed(seed) } } // Int63 returns a non-negative pseudo-random 63-bit integer as an int64 // from the default [Source]. func Int63() int64 { return globalRand().Int63() } // Uint32 returns a pseudo-random 32-bit value as a uint32 // from the default [Source]. func Uint32() uint32 { return globalRand().Uint32() } // Uint64 returns a pseudo-random 64-bit value as a uint64 // from the default [Source]. func Uint64() uint64 { return globalRand().Uint64() } // Int31 returns a non-negative pseudo-random 31-bit integer as an int32 // from the default [Source]. func Int31() int32 { return globalRand().Int31() } // Int returns a non-negative pseudo-random int from the default [Source]. func Int() int { return globalRand().Int() } // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n) // from the default [Source]. // It panics if n <= 0. func Int63n(n int64) int64 { return globalRand().Int63n(n) } // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n) // from the default [Source]. // It panics if n <= 0. func Int31n(n int32) int32 { return globalRand().Int31n(n) } // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n) // from the default [Source]. // It panics if n <= 0. func Intn(n int) int { return globalRand().Intn(n) } // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0) // from the default [Source]. func Float64() float64 { return globalRand().Float64() } // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0) // from the default [Source]. func Float32() float32 { return globalRand().Float32() } // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers // in the half-open interval [0,n) from the default [Source]. func Perm(n int) []int { return globalRand().Perm(n) } // Shuffle pseudo-randomizes the order of elements using the default [Source]. // n is the number of elements. Shuffle panics if n < 0. // swap swaps the elements with indexes i and j. func Shuffle(n int, swap func(i, j int)) { globalRand().Shuffle(n, swap) } // Read generates len(p) random bytes from the default [Source] and // writes them into p. It always returns len(p) and a nil error. // Read, unlike the [Rand.Read] method, is safe for concurrent use. // // Deprecated: For almost all use cases, [crypto/rand.Read] is more appropriate. func Read(p []byte) (n int, err error) { return globalRand().Read(p) } // NormFloat64 returns a normally distributed float64 in the range // [-[math.MaxFloat64], +[math.MaxFloat64]] with // standard normal distribution (mean = 0, stddev = 1) // from the default [Source]. // To produce a different normal distribution, callers can // adjust the output using: // // sample = NormFloat64() * desiredStdDev + desiredMean func NormFloat64() float64 { return globalRand().NormFloat64() } // ExpFloat64 returns an exponentially distributed float64 in the range // (0, +[math.MaxFloat64]] with an exponential distribution whose rate parameter // (lambda) is 1 and whose mean is 1/lambda (1) from the default [Source]. // To produce a distribution with a different rate parameter, // callers can adjust the output using: // // sample = ExpFloat64() / desiredRateParameter func ExpFloat64() float64 { return globalRand().ExpFloat64() } type lockedSource struct { lk sync.Mutex s *rngSource } func (r *lockedSource) Int63() (n int64) { r.lk.Lock() n = r.s.Int63() r.lk.Unlock() return } func (r *lockedSource) Uint64() (n uint64) { r.lk.Lock() n = r.s.Uint64() r.lk.Unlock() return } func (r *lockedSource) Seed(seed int64) { r.lk.Lock() r.seed(seed) r.lk.Unlock() } // seedPos implements Seed for a lockedSource without a race condition. func (r *lockedSource) seedPos(seed int64, readPos *int8) { r.lk.Lock() r.seed(seed) *readPos = 0 r.lk.Unlock() } // seed seeds the underlying source. // The caller must have locked r.lk. func (r *lockedSource) seed(seed int64) { if r.s == nil { r.s = newSource(seed) } else { r.s.Seed(seed) } } // read implements Read for a lockedSource without a race condition. func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) { r.lk.Lock() n, err = read(p, r.s, readVal, readPos) r.lk.Unlock() return }