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.
5 // Package rand implements pseudo-random number generators.
7 // Random numbers are generated by a Source. Top-level functions, such as
8 // Float64 and Int, use a default shared Source that produces a deterministic
9 // sequence of values each time a program is run. Use the Seed function to
10 // initialize the default Source if different behavior is required for each run.
11 // The default Source is safe for concurrent use by multiple goroutines, but
12 // Sources created by NewSource are not.
14 // Mathematical interval notation such as [0, n) is used throughout the
15 // documentation for this package.
17 // For random numbers suitable for security-sensitive work, see the crypto/rand
23 // A Source represents a source of uniformly-distributed
24 // pseudo-random int64 values in the range [0, 1<<63).
25 type Source
interface {
30 // A Source64 is a Source that can also generate
31 // uniformly-distributed pseudo-random uint64 values in
32 // the range [0, 1<<64) directly.
33 // If a Rand r's underlying Source s implements Source64,
34 // then r.Uint64 returns the result of one call to s.Uint64
35 // instead of making two calls to s.Int63.
36 type Source64
interface {
41 // NewSource returns a new pseudo-random Source seeded with the given value.
42 // Unlike the default Source used by top-level functions, this source is not
43 // safe for concurrent use by multiple goroutines.
44 func NewSource(seed
int64) Source
{
50 // A Rand is a source of random numbers.
53 s64 Source64
// non-nil if src is source64
55 // readVal contains remainder of 63-bit integer used for bytes
56 // generation during most recent Read call.
57 // It is saved so next Read call can start where the previous
60 // readPos indicates the number of low-order bytes of readVal
61 // that are still valid.
65 // New returns a new Rand that uses random values from src
66 // to generate other random values.
67 func New(src Source
) *Rand
{
68 s64
, _
:= src
.(Source64
)
69 return &Rand
{src
: src
, s64
: s64
}
72 // Seed uses the provided seed value to initialize the generator to a deterministic state.
73 // Seed should not be called concurrently with any other Rand method.
74 func (r
*Rand
) Seed(seed
int64) {
75 if lk
, ok
:= r
.src
.(*lockedSource
); ok
{
76 lk
.seedPos(seed
, &r
.readPos
)
84 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
85 func (r
*Rand
) Int63() int64 { return r
.src
.Int63() }
87 // Uint32 returns a pseudo-random 32-bit value as a uint32.
88 func (r
*Rand
) Uint32() uint32 { return uint32(r
.Int63() >> 31) }
90 // Uint64 returns a pseudo-random 64-bit value as a uint64.
91 func (r
*Rand
) Uint64() uint64 {
95 return uint64(r
.Int63())>>31 |
uint64(r
.Int63())<<32
98 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
99 func (r
*Rand
) Int31() int32 { return int32(r
.Int63() >> 32) }
101 // Int returns a non-negative pseudo-random int.
102 func (r
*Rand
) Int() int {
104 return int(u
<< 1 >> 1) // clear sign bit if int == int32
107 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n).
108 // It panics if n <= 0.
109 func (r
*Rand
) Int63n(n
int64) int64 {
111 panic("invalid argument to Int63n")
113 if n
&(n
-1) == 0 { // n is power of two, can mask
114 return r
.Int63() & (n
- 1)
116 max
:= int64((1 << 63) - 1 - (1<<63)%uint
64(n
))
124 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
125 // It panics if n <= 0.
126 func (r
*Rand
) Int31n(n
int32) int32 {
128 panic("invalid argument to Int31n")
130 if n
&(n
-1) == 0 { // n is power of two, can mask
131 return r
.Int31() & (n
- 1)
133 max
:= int32((1 << 31) - 1 - (1<<31)%uint
32(n
))
141 // int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
142 // n must be > 0, but int31n does not check this; the caller must ensure it.
143 // int31n exists because Int31n is inefficient, but Go 1 compatibility
144 // requires that the stream of values produced by math/rand remain unchanged.
145 // int31n can thus only be used internally, by newly introduced APIs.
147 // For implementation details, see:
148 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
149 // https://lemire.me/blog/2016/06/30/fast-random-shuffling
150 func (r
*Rand
) int31n(n
int32) int32 {
152 prod
:= uint64(v
) * uint64(n
)
155 thresh
:= uint32(-n
) % uint32(n
)
158 prod
= uint64(v
) * uint64(n
)
162 return int32(prod
>> 32)
165 // Intn returns, as an int, a non-negative pseudo-random number in [0,n).
166 // It panics if n <= 0.
167 func (r
*Rand
) Intn(n
int) int {
169 panic("invalid argument to Intn")
172 return int(r
.Int31n(int32(n
)))
174 return int(r
.Int63n(int64(n
)))
177 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
178 func (r
*Rand
) Float64() float64 {
179 // A clearer, simpler implementation would be:
180 // return float64(r.Int63n(1<<53)) / (1<<53)
181 // However, Go 1 shipped with
182 // return float64(r.Int63()) / (1 << 63)
183 // and we want to preserve that value stream.
185 // There is one bug in the value stream: r.Int63() may be so close
186 // to 1<<63 that the division rounds up to 1.0, and we've guaranteed
187 // that the result is always less than 1.0.
189 // We tried to fix this by mapping 1.0 back to 0.0, but since float64
190 // values near 0 are much denser than near 1, mapping 1 to 0 caused
191 // a theoretically significant overshoot in the probability of returning 0.
192 // Instead of that, if we round up to 1, just try again.
193 // Getting 1 only happens 1/2⁵³ of the time, so most clients
194 // will not observe it anyway.
196 f
:= float64(r
.Int63()) / (1 << 63)
198 goto again
// resample; this branch is taken O(never)
203 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).
204 func (r
*Rand
) Float32() float32 {
205 // Same rationale as in Float64: we want to preserve the Go 1 value
206 // stream except we want to fix it not to return 1.0
207 // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
209 f
:= float32(r
.Float64())
211 goto again
// resample; this branch is taken O(very rarely)
216 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
217 func (r
*Rand
) Perm(n
int) []int {
219 // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
220 // A change to remove this useless iteration is to assign 1 to i in the init
221 // statement. But Perm also effects r. Making this change will affect
222 // the final state of r. So this change can't be made for compatibility
224 for i
:= 0; i
< n
; i
++ {
232 // Shuffle pseudo-randomizes the order of elements.
233 // n is the number of elements. Shuffle panics if n < 0.
234 // swap swaps the elements with indexes i and j.
235 func (r
*Rand
) Shuffle(n
int, swap
func(i
, j
int)) {
237 panic("invalid argument to Shuffle")
240 // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
241 // Shuffle really ought not be called with n that doesn't fit in 32 bits.
242 // Not only will it take a very long time, but with 2³¹! possible permutations,
243 // there's no way that any PRNG can have a big enough internal state to
244 // generate even a minuscule percentage of the possible permutations.
245 // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
247 for ; i
> 1<<31-1-1; i
-- {
248 j
:= int(r
.Int63n(int64(i
+ 1)))
252 j
:= int(r
.int31n(int32(i
+ 1)))
257 // Read generates len(p) random bytes and writes them into p. It
258 // always returns len(p) and a nil error.
259 // Read should not be called concurrently with any other Rand method.
260 func (r
*Rand
) Read(p
[]byte) (n
int, err error
) {
261 if lk
, ok
:= r
.src
.(*lockedSource
); ok
{
262 return lk
.read(p
, &r
.readVal
, &r
.readPos
)
264 return read(p
, r
.Int63
, &r
.readVal
, &r
.readPos
)
267 func read(p
[]byte, int63
func() int64, readVal
*int64, readPos
*int8) (n
int, err error
) {
270 for n
= 0; n
< len(p
); n
++ {
285 * Top-level convenience functions
288 var globalRand
= New(&lockedSource
{src
: NewSource(1).(Source64
)})
290 // Seed uses the provided seed value to initialize the default Source to a
291 // deterministic state. If Seed is not called, the generator behaves as
292 // if seeded by Seed(1). Seed values that have the same remainder when
293 // divided by 2^31-1 generate the same pseudo-random sequence.
294 // Seed, unlike the Rand.Seed method, is safe for concurrent use.
295 func Seed(seed
int64) { globalRand
.Seed(seed
) }
297 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
298 // from the default Source.
299 func Int63() int64 { return globalRand
.Int63() }
301 // Uint32 returns a pseudo-random 32-bit value as a uint32
302 // from the default Source.
303 func Uint32() uint32 { return globalRand
.Uint32() }
305 // Uint64 returns a pseudo-random 64-bit value as a uint64
306 // from the default Source.
307 func Uint64() uint64 { return globalRand
.Uint64() }
309 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
310 // from the default Source.
311 func Int31() int32 { return globalRand
.Int31() }
313 // Int returns a non-negative pseudo-random int from the default Source.
314 func Int() int { return globalRand
.Int() }
316 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n)
317 // from the default Source.
318 // It panics if n <= 0.
319 func Int63n(n
int64) int64 { return globalRand
.Int63n(n
) }
321 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n)
322 // from the default Source.
323 // It panics if n <= 0.
324 func Int31n(n
int32) int32 { return globalRand
.Int31n(n
) }
326 // Intn returns, as an int, a non-negative pseudo-random number in [0,n)
327 // from the default Source.
328 // It panics if n <= 0.
329 func Intn(n
int) int { return globalRand
.Intn(n
) }
331 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0)
332 // from the default Source.
333 func Float64() float64 { return globalRand
.Float64() }
335 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0)
336 // from the default Source.
337 func Float32() float32 { return globalRand
.Float32() }
339 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n)
340 // from the default Source.
341 func Perm(n
int) []int { return globalRand
.Perm(n
) }
343 // Shuffle pseudo-randomizes the order of elements using the default Source.
344 // n is the number of elements. Shuffle panics if n < 0.
345 // swap swaps the elements with indexes i and j.
346 func Shuffle(n
int, swap
func(i
, j
int)) { globalRand
.Shuffle(n
, swap
) }
348 // Read generates len(p) random bytes from the default Source and
349 // writes them into p. It always returns len(p) and a nil error.
350 // Read, unlike the Rand.Read method, is safe for concurrent use.
351 func Read(p
[]byte) (n
int, err error
) { return globalRand
.Read(p
) }
353 // NormFloat64 returns a normally distributed float64 in the range
354 // [-math.MaxFloat64, +math.MaxFloat64] with
355 // standard normal distribution (mean = 0, stddev = 1)
356 // from the default Source.
357 // To produce a different normal distribution, callers can
358 // adjust the output using:
360 // sample = NormFloat64() * desiredStdDev + desiredMean
362 func NormFloat64() float64 { return globalRand
.NormFloat64() }
364 // ExpFloat64 returns an exponentially distributed float64 in the range
365 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
366 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
367 // To produce a distribution with a different rate parameter,
368 // callers can adjust the output using:
370 // sample = ExpFloat64() / desiredRateParameter
372 func ExpFloat64() float64 { return globalRand
.ExpFloat64() }
374 type lockedSource
struct {
379 func (r
*lockedSource
) Int63() (n
int64) {
386 func (r
*lockedSource
) Uint64() (n
uint64) {
393 func (r
*lockedSource
) Seed(seed
int64) {
399 // seedPos implements Seed for a lockedSource without a race condition.
400 func (r
*lockedSource
) seedPos(seed
int64, readPos
*int8) {
407 // read implements Read for a lockedSource without a race condition.
408 func (r
*lockedSource
) read(p
[]byte, readVal
*int64, readPos
*int8) (n
int, err error
) {
410 n
, err
= read(p
, r
.src
.Int63
, readVal
, readPos
)