| // 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, a LockedSource, is safe for concurrent use by multiple |
| // goroutines, but Sources created by NewSource are not. However, Sources are small |
| // and it is reasonable to have a separate Source for each goroutine, seeded |
| // differently, to avoid locking. |
| // |
| // 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<<64). |
| type Source interface { |
| Uint64() uint64 |
| Seed(seed uint64) |
| } |
| |
| // NewSource returns a new pseudo-random Source seeded with the given value. |
| func NewSource(seed uint64) Source { |
| var rng PCGSource |
| rng.Seed(seed) |
| return &rng |
| } |
| |
| // A Rand is a source of random numbers. |
| type Rand struct { |
| src Source |
| |
| // readVal contains remainder of 64-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 uint64 |
| // 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 { |
| return &Rand{src: src} |
| } |
| |
| // 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 uint64) { |
| if lk, ok := r.src.(*LockedSource); ok { |
| lk.seedPos(seed, &r.readPos) |
| return |
| } |
| |
| r.src.Seed(seed) |
| r.readPos = 0 |
| } |
| |
| // Uint64 returns a pseudo-random 64-bit integer as a uint64. |
| func (r *Rand) Uint64() uint64 { return r.src.Uint64() } |
| |
| // Int63 returns a non-negative pseudo-random 63-bit integer as an int64. |
| func (r *Rand) Int63() int64 { return int64(r.src.Uint64() &^ (1 << 63)) } |
| |
| // Uint32 returns a pseudo-random 32-bit value as a uint32. |
| func (r *Rand) Uint32() uint32 { return uint32(r.Uint64() >> 32) } |
| |
| // Int31 returns a non-negative pseudo-random 31-bit integer as an int32. |
| func (r *Rand) Int31() int32 { return int32(r.Uint64() >> 33) } |
| |
| // Int returns a non-negative pseudo-random int. |
| func (r *Rand) Int() int { |
| u := uint(r.Uint64()) |
| return int(u << 1 >> 1) // clear sign bit. |
| } |
| |
| const maxUint64 = (1 << 64) - 1 |
| |
| // Uint64n returns, as a uint64, a pseudo-random number in [0,n). |
| // It is guaranteed more uniform than taking a Source value mod n |
| // for any n that is not a power of 2. |
| func (r *Rand) Uint64n(n uint64) uint64 { |
| if n&(n-1) == 0 { // n is power of two, can mask |
| if n == 0 { |
| panic("invalid argument to Uint64n") |
| } |
| return r.Uint64() & (n - 1) |
| } |
| // If n does not divide v, to avoid bias we must not use |
| // a v that is within maxUint64%n of the top of the range. |
| v := r.Uint64() |
| if v > maxUint64-n { // Fast check. |
| ceiling := maxUint64 - maxUint64%n |
| for v >= ceiling { |
| v = r.Uint64() |
| } |
| } |
| |
| return v % n |
| } |
| |
| // 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") |
| } |
| return int64(r.Uint64n(uint64(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") |
| } |
| // TODO: Avoid some 64-bit ops to make it more efficient on 32-bit machines. |
| return int32(r.Uint64n(uint64(n))) |
| } |
| |
| // 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") |
| } |
| // TODO: Avoid some 64-bit ops to make it more efficient on 32-bit machines. |
| return int(r.Uint64n(uint64(n))) |
| } |
| |
| // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0). |
| func (r *Rand) Float64() float64 { |
| // 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.Uint64n(1<<53)) / (1 << 53) |
| if f == 1.0 { |
| 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 { |
| // We do not want 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 unless |
| // the underlying source is a LockedSource. |
| 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.src, &r.readVal, &r.readPos) |
| } |
| |
| func read(p []byte, src Source, readVal *uint64, readPos *int8) (n int, err error) { |
| pos := *readPos |
| val := *readVal |
| rng, _ := src.(*PCGSource) |
| for n = 0; n < len(p); n++ { |
| if pos == 0 { |
| if rng != nil { |
| val = rng.Uint64() |
| } else { |
| val = src.Uint64() |
| } |
| pos = 8 |
| } |
| p[n] = byte(val) |
| val >>= 8 |
| pos-- |
| } |
| *readPos = pos |
| *readVal = val |
| return |
| } |
| |
| /* |
| * Top-level convenience functions |
| */ |
| |
| var globalRand = New(&LockedSource{src: *NewSource(1).(*PCGSource)}) |
| |
| // Type assert that globalRand's source is a LockedSource whose src is a PCGSource. |
| var _ PCGSource = globalRand.src.(*LockedSource).src |
| |
| // 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, unlike the Rand.Seed method, is safe for concurrent use. |
| func Seed(seed uint64) { 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() } |
| |
| // LockedSource is an implementation of Source that is concurrency-safe. |
| // A Rand using a LockedSource is safe for concurrent use. |
| // |
| // The zero value of LockedSource is valid, but should be seeded before use. |
| type LockedSource struct { |
| lk sync.Mutex |
| src PCGSource |
| } |
| |
| func (s *LockedSource) Uint64() (n uint64) { |
| s.lk.Lock() |
| n = s.src.Uint64() |
| s.lk.Unlock() |
| return |
| } |
| |
| func (s *LockedSource) Seed(seed uint64) { |
| s.lk.Lock() |
| s.src.Seed(seed) |
| s.lk.Unlock() |
| } |
| |
| // seedPos implements Seed for a LockedSource without a race condiiton. |
| func (s *LockedSource) seedPos(seed uint64, readPos *int8) { |
| s.lk.Lock() |
| s.src.Seed(seed) |
| *readPos = 0 |
| s.lk.Unlock() |
| } |
| |
| // Read implements Read for a LockedSource. |
| func (s *LockedSource) Read(p []byte, readVal *uint64, readPos *int8) (n int, err error) { |
| s.lk.Lock() |
| n, err = read(p, &s.src, readVal, readPos) |
| s.lk.Unlock() |
| return |
| } |