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.
4 5 // Package rand implements pseudo-random number generators suitable for tasks
6 // such as simulation, but it should not be used for security-sensitive work.
7 //
8 // Random numbers are generated by a [Source], usually wrapped in a [Rand].
9 // Both types should be used by a single goroutine at a time: sharing among
10 // multiple goroutines requires some kind of synchronization.
11 //
12 // Top-level functions, such as [Float64] and [Int],
13 // are safe for concurrent use by multiple goroutines.
14 //
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
19 20 import (
21 "math/bits"
22 _ "unsafe" // for go:linkname
23 )
24 25 // A Source is a source of uniformly-distributed
26 // pseudo-random uint64 values in the range [0, 1<<64).
27 //
28 // A Source is not safe for concurrent use by multiple goroutines.
29 type Source interface {
30 Uint64() uint64
31 }
32 33 // A Rand is a source of random numbers.
34 type Rand struct {
35 src Source
36 }
37 38 // New returns a new Rand that uses random values from src
39 // to generate other random values.
40 func New(src Source) *Rand {
41 return &Rand{src: src}
42 }
43 44 // Int64 returns a non-negative pseudo-random 63-bit integer as an int64.
45 func (r *Rand) Int64() int64 { return int64(r.src.Uint64() &^ (1 << 63)) }
46 47 // Uint32 returns a pseudo-random 32-bit value as a uint32.
48 func (r *Rand) Uint32() uint32 { return uint32(r.src.Uint64() >> 32) }
49 50 // Uint64 returns a pseudo-random 64-bit value as a uint64.
51 func (r *Rand) Uint64() uint64 { return r.src.Uint64() }
52 53 // Int32 returns a non-negative pseudo-random 31-bit integer as an int32.
54 func (r *Rand) Int32() int32 { return int32(r.src.Uint64() >> 33) }
55 56 // Int returns a non-negative pseudo-random int.
57 func (r *Rand) Int() int { return int(uint(r.src.Uint64()) << 1 >> 1) }
58 59 // Uint returns a pseudo-random uint.
60 func (r *Rand) Uint() uint { return uint(r.src.Uint64()) }
61 62 // Int64N returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
63 // It panics if n <= 0.
64 func (r *Rand) Int64N(n int64) int64 {
65 if n <= 0 {
66 panic("invalid argument to Int64N")
67 }
68 return int64(r.uint64n(uint64(n)))
69 }
70 71 // Uint64N returns, as a uint64, a non-negative pseudo-random number in the half-open interval [0,n).
72 // It panics if n == 0.
73 func (r *Rand) Uint64N(n uint64) uint64 {
74 if n == 0 {
75 panic("invalid argument to Uint64N")
76 }
77 return r.uint64n(n)
78 }
79 80 // uint64n is the no-bounds-checks version of Uint64N.
81 func (r *Rand) uint64n(n uint64) uint64 {
82 if is32bit && uint64(uint32(n)) == n {
83 return uint64(r.uint32n(uint32(n)))
84 }
85 if n&(n-1) == 0 { // n is power of two, can mask
86 return r.Uint64() & (n - 1)
87 }
88 89 // Suppose we have a uint64 x uniform in the range [0,2⁶⁴)
90 // and want to reduce it to the range [0,n) preserving exact uniformity.
91 // We can simulate a scaling arbitrary precision x * (n/2⁶⁴) by
92 // the high bits of a double-width multiply of x*n, meaning (x*n)/2⁶⁴.
93 // Since there are 2⁶⁴ possible inputs x and only n possible outputs,
94 // the output is necessarily biased if n does not divide 2⁶⁴.
95 // In general (x*n)/2⁶⁴ = k for x*n in [k*2⁶⁴,(k+1)*2⁶⁴).
96 // There are either floor(2⁶⁴/n) or ceil(2⁶⁴/n) possible products
97 // in that range, depending on k.
98 // But suppose we reject the sample and try again when
99 // x*n is in [k*2⁶⁴, k*2⁶⁴+(2⁶⁴%n)), meaning rejecting fewer than n possible
100 // outcomes out of the 2⁶⁴.
101 // Now there are exactly floor(2⁶⁴/n) possible ways to produce
102 // each output value k, so we've restored uniformity.
103 // To get valid uint64 math, 2⁶⁴ % n = (2⁶⁴ - n) % n = -n % n,
104 // so the direct implementation of this algorithm would be:
105 //
106 // hi, lo := bits.Mul64(r.Uint64(), n)
107 // thresh := -n % n
108 // for lo < thresh {
109 // hi, lo = bits.Mul64(r.Uint64(), n)
110 // }
111 //
112 // That still leaves an expensive 64-bit division that we would rather avoid.
113 // We know that thresh < n, and n is usually much less than 2⁶⁴, so we can
114 // avoid the last four lines unless lo < n.
115 //
116 // See also:
117 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
118 // https://lemire.me/blog/2016/06/30/fast-random-shuffling
119 hi, lo := bits.Mul64(r.Uint64(), n)
120 if lo < n {
121 thresh := -n % n
122 for lo < thresh {
123 hi, lo = bits.Mul64(r.Uint64(), n)
124 }
125 }
126 return hi
127 }
128 129 // uint32n is an identical computation to uint64n
130 // but optimized for 32-bit systems.
131 func (r *Rand) uint32n(n uint32) uint32 {
132 if n&(n-1) == 0 { // n is power of two, can mask
133 return uint32(r.Uint64()) & (n - 1)
134 }
135 // On 64-bit systems we still use the uint64 code below because
136 // the probability of a random uint64 lo being < a uint32 n is near zero,
137 // meaning the unbiasing loop almost never runs.
138 // On 32-bit systems, here we need to implement that same logic in 32-bit math,
139 // both to preserve the exact output sequence observed on 64-bit machines
140 // and to preserve the optimization that the unbiasing loop almost never runs.
141 //
142 // We want to compute
143 // hi, lo := bits.Mul64(r.Uint64(), n)
144 // In terms of 32-bit halves, this is:
145 // x1:x0 := r.Uint64()
146 // 0:hi, lo1:lo0 := bits.Mul64(x1:x0, 0:n)
147 // Writing out the multiplication in terms of bits.Mul32 allows
148 // using direct hardware instructions and avoiding
149 // the computations involving these zeros.
150 x := r.Uint64()
151 lo1a, lo0 := bits.Mul32(uint32(x), n)
152 hi, lo1b := bits.Mul32(uint32(x>>32), n)
153 lo1, c := bits.Add32(lo1a, lo1b, 0)
154 hi += c
155 if lo1 == 0 && lo0 < uint32(n) {
156 n64 := uint64(n)
157 thresh := uint32(-n64 % n64)
158 for lo1 == 0 && lo0 < thresh {
159 x := r.Uint64()
160 lo1a, lo0 = bits.Mul32(uint32(x), n)
161 hi, lo1b = bits.Mul32(uint32(x>>32), n)
162 lo1, c = bits.Add32(lo1a, lo1b, 0)
163 hi += c
164 }
165 }
166 return hi
167 }
168 169 // Int32N returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
170 // It panics if n <= 0.
171 func (r *Rand) Int32N(n int32) int32 {
172 if n <= 0 {
173 panic("invalid argument to Int32N")
174 }
175 return int32(r.uint64n(uint64(n)))
176 }
177 178 // Uint32N returns, as a uint32, a non-negative pseudo-random number in the half-open interval [0,n).
179 // It panics if n == 0.
180 func (r *Rand) Uint32N(n uint32) uint32 {
181 if n == 0 {
182 panic("invalid argument to Uint32N")
183 }
184 return uint32(r.uint64n(uint64(n)))
185 }
186 187 const is32bit = ^uint(0)>>32 == 0
188 189 // IntN returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
190 // It panics if n <= 0.
191 func (r *Rand) IntN(n int) int {
192 if n <= 0 {
193 panic("invalid argument to IntN")
194 }
195 return int(r.uint64n(uint64(n)))
196 }
197 198 // UintN returns, as a uint, a non-negative pseudo-random number in the half-open interval [0,n).
199 // It panics if n == 0.
200 func (r *Rand) UintN(n uint) uint {
201 if n == 0 {
202 panic("invalid argument to UintN")
203 }
204 return uint(r.uint64n(uint64(n)))
205 }
206 207 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
208 func (r *Rand) Float64() float64 {
209 // There are exactly 1<<53 float64s in [0,1). Use Intn(1<<53) / (1<<53).
210 return float64(r.Uint64()<<11>>11) / (1 << 53)
211 }
212 213 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
214 func (r *Rand) Float32() float32 {
215 // There are exactly 1<<24 float32s in [0,1). Use Intn(1<<24) / (1<<24).
216 return float32(r.Uint32()<<8>>8) / (1 << 24)
217 }
218 219 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
220 // in the half-open interval [0,n).
221 func (r *Rand) Perm(n int) []int {
222 p := []int{:n}
223 for i := range p {
224 p[i] = i
225 }
226 r.Shuffle(len(p), func(i, j int) { p[i], p[j] = p[j], p[i] })
227 return p
228 }
229 230 // Shuffle pseudo-randomizes the order of elements.
231 // n is the number of elements. Shuffle panics if n < 0.
232 // swap swaps the elements with indexes i and j.
233 func (r *Rand) Shuffle(n int, swap func(i, j int)) {
234 if n < 0 {
235 panic("invalid argument to Shuffle")
236 }
237 238 // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
239 // Shuffle really ought not be called with n that doesn't fit in 32 bits.
240 // Not only will it take a very long time, but with 2³¹! possible permutations,
241 // there's no way that any PRNG can have a big enough internal state to
242 // generate even a minuscule percentage of the possible permutations.
243 // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
244 for i := n - 1; i > 0; i-- {
245 j := int(r.uint64n(uint64(i + 1)))
246 swap(i, j)
247 }
248 }
249 250 /*
251 * Top-level convenience functions
252 */
253 254 // globalRand is the source of random numbers for the top-level
255 // convenience functions.
256 var globalRand = &Rand{src: runtimeSource{}}
257 258 //go:linkname runtime_rand runtime.rand
259 func runtime_rand() uint64
260 261 // runtimeSource is a Source that uses the runtime fastrand functions.
262 type runtimeSource struct{}
263 264 func (runtimeSource) Uint64() uint64 {
265 return runtime_rand()
266 }
267 268 // Int64 returns a non-negative pseudo-random 63-bit integer as an int64
269 // from the default Source.
270 func Int64() int64 { return globalRand.Int64() }
271 272 // Uint32 returns a pseudo-random 32-bit value as a uint32
273 // from the default Source.
274 func Uint32() uint32 { return globalRand.Uint32() }
275 276 // Uint64N returns, as a uint64, a pseudo-random number in the half-open interval [0,n)
277 // from the default Source.
278 // It panics if n == 0.
279 func Uint64N(n uint64) uint64 { return globalRand.Uint64N(n) }
280 281 // Uint32N returns, as a uint32, a pseudo-random number in the half-open interval [0,n)
282 // from the default Source.
283 // It panics if n == 0.
284 func Uint32N(n uint32) uint32 { return globalRand.Uint32N(n) }
285 286 // Uint64 returns a pseudo-random 64-bit value as a uint64
287 // from the default Source.
288 func Uint64() uint64 { return globalRand.Uint64() }
289 290 // Int32 returns a non-negative pseudo-random 31-bit integer as an int32
291 // from the default Source.
292 func Int32() int32 { return globalRand.Int32() }
293 294 // Int returns a non-negative pseudo-random int from the default Source.
295 func Int() int { return globalRand.Int() }
296 297 // Uint returns a pseudo-random uint from the default Source.
298 func Uint() uint { return globalRand.Uint() }
299 300 // Int64N returns, as an int64, a pseudo-random number in the half-open interval [0,n)
301 // from the default Source.
302 // It panics if n <= 0.
303 func Int64N(n int64) int64 { return globalRand.Int64N(n) }
304 305 // Int32N returns, as an int32, a pseudo-random number in the half-open interval [0,n)
306 // from the default Source.
307 // It panics if n <= 0.
308 func Int32N(n int32) int32 { return globalRand.Int32N(n) }
309 310 // IntN returns, as an int, a pseudo-random number in the half-open interval [0,n)
311 // from the default Source.
312 // It panics if n <= 0.
313 func IntN(n int) int { return globalRand.IntN(n) }
314 315 // UintN returns, as a uint, a pseudo-random number in the half-open interval [0,n)
316 // from the default Source.
317 // It panics if n == 0.
318 func UintN(n uint) uint { return globalRand.UintN(n) }
319 320 // N returns a pseudo-random number in the half-open interval [0,n) from the default Source.
321 // The type parameter Int can be any integer type.
322 // It panics if n <= 0.
323 func N[Int intType](n Int) Int {
324 if n <= 0 {
325 panic("invalid argument to N")
326 }
327 return Int(globalRand.uint64n(uint64(n)))
328 }
329 330 type intType interface {
331 ~int | ~int8 | ~int16 | ~int64 |
332 ~uint | ~uint8 | ~uint16 | ~uint64 | ~uintptr
333 }
334 335 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
336 // from the default Source.
337 func Float64() float64 { return globalRand.Float64() }
338 339 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
340 // from the default Source.
341 func Float32() float32 { return globalRand.Float32() }
342 343 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
344 // in the half-open interval [0,n) from the default Source.
345 func Perm(n int) []int { return globalRand.Perm(n) }
346 347 // Shuffle pseudo-randomizes the order of elements using the default Source.
348 // n is the number of elements. Shuffle panics if n < 0.
349 // swap swaps the elements with indexes i and j.
350 func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }
351 352 // NormFloat64 returns a normally distributed float64 in the range
353 // [-math.MaxFloat64, +math.MaxFloat64] with
354 // standard normal distribution (mean = 0, stddev = 1)
355 // from the default Source.
356 // To produce a different normal distribution, callers can
357 // adjust the output using:
358 //
359 // sample = NormFloat64() * desiredStdDev + desiredMean
360 func NormFloat64() float64 { return globalRand.NormFloat64() }
361 362 // ExpFloat64 returns an exponentially distributed float64 in the range
363 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
364 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
365 // To produce a distribution with a different rate parameter,
366 // callers can adjust the output using:
367 //
368 // sample = ExpFloat64() / desiredRateParameter
369 func ExpFloat64() float64 { return globalRand.ExpFloat64() }
370