// 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. // // Random numbers are generated by a Source. Top-level functions, such as // Float64 and Int, use a default shared Source that produces a deterministic // sequence of values each time a program is run. Use the Seed function to // initialize the default Source if different behavior is required for each run. // The default Source is safe for concurrent use by multiple goroutines, but // Sources created by NewSource are not. // // For random numbers suitable for security-sensitive work, see the crypto/rand // package. package rand import "sync" // A Source represents a source of uniformly-distributed // pseudo-random int64 values in the range [0, 1<<63). 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. func NewSource(seed int64) Source { 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 [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 [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 [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 [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 [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 [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 [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) { if lk, ok := r.src.(*lockedSource); ok { return lk.read(p, &r.readVal, &r.readPos) } return read(p, r.Int63, &r.readVal, &r.readPos) } func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, err error) { pos := *readPos val := *readVal for n = 0; n < len(p); n++ { if pos == 0 { val = int63() pos = 7 } p[n] = byte(val) val >>= 8 pos-- } *readPos = pos *readVal = val return } /* * Top-level convenience functions */ var globalRand = New(&lockedSource{src: NewSource(1).(Source64)}) // Seed uses the provided seed value to initialize the default Source to a // deterministic state. If Seed is not called, the generator behaves as // if seeded by Seed(1). Seed values that have the same remainder when // divided by 2^31-1 generate the same pseudo-random sequence. // Seed, unlike the Rand.Seed method, is safe for concurrent use. func Seed(seed int64) { globalRand.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 [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 [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 [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 [0.0,1.0) // from the default Source. func Float64() float64 { return globalRand.Float64() } // Float32 returns, as a float32, a pseudo-random number in [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 [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. 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 src Source64 } func (r *lockedSource) Int63() (n int64) { r.lk.Lock() n = r.src.Int63() r.lk.Unlock() return } func (r *lockedSource) Uint64() (n uint64) { r.lk.Lock() n = r.src.Uint64() r.lk.Unlock() return } func (r *lockedSource) Seed(seed int64) { r.lk.Lock() r.src.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.src.Seed(seed) *readPos = 0 r.lk.Unlock() } // 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.src.Int63, readVal, readPos) r.lk.Unlock() return }