Daily bump.
[official-gcc.git] / libgo / go / math / rand / rand.go
blob13f20ca5efb28271d13f242a566ceaf5ff36be60
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 unsuitable for
6 // security-sensitive work.
7 //
8 // Random numbers are generated by a Source. Top-level functions, such as
9 // Float64 and Int, use a default shared Source that produces a deterministic
10 // sequence of values each time a program is run. Use the Seed function to
11 // initialize the default Source if different behavior is required for each run.
12 // The default Source is safe for concurrent use by multiple goroutines, but
13 // Sources created by NewSource are not.
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
20 import "sync"
22 // A Source represents a source of uniformly-distributed
23 // pseudo-random int64 values in the range [0, 1<<63).
24 type Source interface {
25 Int63() int64
26 Seed(seed int64)
29 // A Source64 is a Source that can also generate
30 // uniformly-distributed pseudo-random uint64 values in
31 // the range [0, 1<<64) directly.
32 // If a Rand r's underlying Source s implements Source64,
33 // then r.Uint64 returns the result of one call to s.Uint64
34 // instead of making two calls to s.Int63.
35 type Source64 interface {
36 Source
37 Uint64() uint64
40 // NewSource returns a new pseudo-random Source seeded with the given value.
41 // Unlike the default Source used by top-level functions, this source is not
42 // safe for concurrent use by multiple goroutines.
43 func NewSource(seed int64) Source {
44 var rng rngSource
45 rng.Seed(seed)
46 return &rng
49 // A Rand is a source of random numbers.
50 type Rand struct {
51 src Source
52 s64 Source64 // non-nil if src is source64
54 // readVal contains remainder of 63-bit integer used for bytes
55 // generation during most recent Read call.
56 // It is saved so next Read call can start where the previous
57 // one finished.
58 readVal int64
59 // readPos indicates the number of low-order bytes of readVal
60 // that are still valid.
61 readPos int8
64 // New returns a new Rand that uses random values from src
65 // to generate other random values.
66 func New(src Source) *Rand {
67 s64, _ := src.(Source64)
68 return &Rand{src: src, s64: s64}
71 // Seed uses the provided seed value to initialize the generator to a deterministic state.
72 // Seed should not be called concurrently with any other Rand method.
73 func (r *Rand) Seed(seed int64) {
74 if lk, ok := r.src.(*lockedSource); ok {
75 lk.seedPos(seed, &r.readPos)
76 return
79 r.src.Seed(seed)
80 r.readPos = 0
83 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
84 func (r *Rand) Int63() int64 { return r.src.Int63() }
86 // Uint32 returns a pseudo-random 32-bit value as a uint32.
87 func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
89 // Uint64 returns a pseudo-random 64-bit value as a uint64.
90 func (r *Rand) Uint64() uint64 {
91 if r.s64 != nil {
92 return r.s64.Uint64()
94 return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
97 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
98 func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
100 // Int returns a non-negative pseudo-random int.
101 func (r *Rand) Int() int {
102 u := uint(r.Int63())
103 return int(u << 1 >> 1) // clear sign bit if int == int32
106 // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
107 // It panics if n <= 0.
108 func (r *Rand) Int63n(n int64) int64 {
109 if n <= 0 {
110 panic("invalid argument to Int63n")
112 if n&(n-1) == 0 { // n is power of two, can mask
113 return r.Int63() & (n - 1)
115 max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
116 v := r.Int63()
117 for v > max {
118 v = r.Int63()
120 return v % n
123 // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
124 // It panics if n <= 0.
125 func (r *Rand) Int31n(n int32) int32 {
126 if n <= 0 {
127 panic("invalid argument to Int31n")
129 if n&(n-1) == 0 { // n is power of two, can mask
130 return r.Int31() & (n - 1)
132 max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
133 v := r.Int31()
134 for v > max {
135 v = r.Int31()
137 return v % n
140 // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
141 // n must be > 0, but int31n does not check this; the caller must ensure it.
142 // int31n exists because Int31n is inefficient, but Go 1 compatibility
143 // requires that the stream of values produced by math/rand remain unchanged.
144 // int31n can thus only be used internally, by newly introduced APIs.
146 // For implementation details, see:
147 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
148 // https://lemire.me/blog/2016/06/30/fast-random-shuffling
149 func (r *Rand) int31n(n int32) int32 {
150 v := r.Uint32()
151 prod := uint64(v) * uint64(n)
152 low := uint32(prod)
153 if low < uint32(n) {
154 thresh := uint32(-n) % uint32(n)
155 for low < thresh {
156 v = r.Uint32()
157 prod = uint64(v) * uint64(n)
158 low = uint32(prod)
161 return int32(prod >> 32)
164 // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
165 // It panics if n <= 0.
166 func (r *Rand) Intn(n int) int {
167 if n <= 0 {
168 panic("invalid argument to Intn")
170 if n <= 1<<31-1 {
171 return int(r.Int31n(int32(n)))
173 return int(r.Int63n(int64(n)))
176 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
177 func (r *Rand) Float64() float64 {
178 // A clearer, simpler implementation would be:
179 // return float64(r.Int63n(1<<53)) / (1<<53)
180 // However, Go 1 shipped with
181 // return float64(r.Int63()) / (1 << 63)
182 // and we want to preserve that value stream.
184 // There is one bug in the value stream: r.Int63() may be so close
185 // to 1<<63 that the division rounds up to 1.0, and we've guaranteed
186 // that the result is always less than 1.0.
188 // We tried to fix this by mapping 1.0 back to 0.0, but since float64
189 // values near 0 are much denser than near 1, mapping 1 to 0 caused
190 // a theoretically significant overshoot in the probability of returning 0.
191 // Instead of that, if we round up to 1, just try again.
192 // Getting 1 only happens 1/2⁵³ of the time, so most clients
193 // will not observe it anyway.
194 again:
195 f := float64(r.Int63()) / (1 << 63)
196 if f == 1 {
197 goto again // resample; this branch is taken O(never)
199 return f
202 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
203 func (r *Rand) Float32() float32 {
204 // Same rationale as in Float64: we want to preserve the Go 1 value
205 // stream except we want to fix it not to return 1.0
206 // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
207 again:
208 f := float32(r.Float64())
209 if f == 1 {
210 goto again // resample; this branch is taken O(very rarely)
212 return f
215 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
216 // in the half-open interval [0,n).
217 func (r *Rand) Perm(n int) []int {
218 m := make([]int, n)
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
223 // reasons for Go 1.
224 for i := 0; i < n; i++ {
225 j := r.Intn(i + 1)
226 m[i] = m[j]
227 m[j] = i
229 return m
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)) {
236 if n < 0 {
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.
246 i := n - 1
247 for ; i > 1<<31-1-1; i-- {
248 j := int(r.Int63n(int64(i + 1)))
249 swap(i, j)
251 for ; i > 0; i-- {
252 j := int(r.int31n(int32(i + 1)))
253 swap(i, j)
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.src, &r.readVal, &r.readPos)
267 func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
268 pos := *readPos
269 val := *readVal
270 rng, _ := src.(*rngSource)
271 for n = 0; n < len(p); n++ {
272 if pos == 0 {
273 if rng != nil {
274 val = rng.Int63()
275 } else {
276 val = src.Int63()
278 pos = 7
280 p[n] = byte(val)
281 val >>= 8
282 pos--
284 *readPos = pos
285 *readVal = val
286 return
290 * Top-level convenience functions
293 var globalRand = New(&lockedSource{src: NewSource(1).(*rngSource)})
295 // Type assert that globalRand's source is a lockedSource whose src is a *rngSource.
296 var _ *rngSource = globalRand.src.(*lockedSource).src
298 // Seed uses the provided seed value to initialize the default Source to a
299 // deterministic state. If Seed is not called, the generator behaves as
300 // if seeded by Seed(1). Seed values that have the same remainder when
301 // divided by 2³¹-1 generate the same pseudo-random sequence.
302 // Seed, unlike the Rand.Seed method, is safe for concurrent use.
303 func Seed(seed int64) { globalRand.Seed(seed) }
305 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
306 // from the default Source.
307 func Int63() int64 { return globalRand.Int63() }
309 // Uint32 returns a pseudo-random 32-bit value as a uint32
310 // from the default Source.
311 func Uint32() uint32 { return globalRand.Uint32() }
313 // Uint64 returns a pseudo-random 64-bit value as a uint64
314 // from the default Source.
315 func Uint64() uint64 { return globalRand.Uint64() }
317 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
318 // from the default Source.
319 func Int31() int32 { return globalRand.Int31() }
321 // Int returns a non-negative pseudo-random int from the default Source.
322 func Int() int { return globalRand.Int() }
324 // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
325 // from the default Source.
326 // It panics if n <= 0.
327 func Int63n(n int64) int64 { return globalRand.Int63n(n) }
329 // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
330 // from the default Source.
331 // It panics if n <= 0.
332 func Int31n(n int32) int32 { return globalRand.Int31n(n) }
334 // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
335 // from the default Source.
336 // It panics if n <= 0.
337 func Intn(n int) int { return globalRand.Intn(n) }
339 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
340 // from the default Source.
341 func Float64() float64 { return globalRand.Float64() }
343 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
344 // from the default Source.
345 func Float32() float32 { return globalRand.Float32() }
347 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
348 // in the half-open interval [0,n) from the default Source.
349 func Perm(n int) []int { return globalRand.Perm(n) }
351 // Shuffle pseudo-randomizes the order of elements using the default Source.
352 // n is the number of elements. Shuffle panics if n < 0.
353 // swap swaps the elements with indexes i and j.
354 func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }
356 // Read generates len(p) random bytes from the default Source and
357 // writes them into p. It always returns len(p) and a nil error.
358 // Read, unlike the Rand.Read method, is safe for concurrent use.
359 func Read(p []byte) (n int, err error) { return globalRand.Read(p) }
361 // NormFloat64 returns a normally distributed float64 in the range
362 // [-math.MaxFloat64, +math.MaxFloat64] with
363 // standard normal distribution (mean = 0, stddev = 1)
364 // from the default Source.
365 // To produce a different normal distribution, callers can
366 // adjust the output using:
368 // sample = NormFloat64() * desiredStdDev + desiredMean
370 func NormFloat64() float64 { return globalRand.NormFloat64() }
372 // ExpFloat64 returns an exponentially distributed float64 in the range
373 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
374 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
375 // To produce a distribution with a different rate parameter,
376 // callers can adjust the output using:
378 // sample = ExpFloat64() / desiredRateParameter
380 func ExpFloat64() float64 { return globalRand.ExpFloat64() }
382 type lockedSource struct {
383 lk sync.Mutex
384 src *rngSource
387 func (r *lockedSource) Int63() (n int64) {
388 r.lk.Lock()
389 n = r.src.Int63()
390 r.lk.Unlock()
391 return
394 func (r *lockedSource) Uint64() (n uint64) {
395 r.lk.Lock()
396 n = r.src.Uint64()
397 r.lk.Unlock()
398 return
401 func (r *lockedSource) Seed(seed int64) {
402 r.lk.Lock()
403 r.src.Seed(seed)
404 r.lk.Unlock()
407 // seedPos implements Seed for a lockedSource without a race condition.
408 func (r *lockedSource) seedPos(seed int64, readPos *int8) {
409 r.lk.Lock()
410 r.src.Seed(seed)
411 *readPos = 0
412 r.lk.Unlock()
415 // read implements Read for a lockedSource without a race condition.
416 func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
417 r.lk.Lock()
418 n, err = read(p, r.src, readVal, readPos)
419 r.lk.Unlock()
420 return