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