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