src/math/rand/v2/rand.go

   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         _ "unsafe" // for go:linkname
  22 )
  23
  24 // A Source represents a source of uniformly-distributed
  25 // pseudo-random int64 values in the range [0, 1<<63).
  26 //
  27 // A Source is not safe for concurrent use by multiple goroutines.
  28 type Source interface {
  29         Int64() int64
  30 }
  31
  32 // A Source64 is a Source that can also generate
  33 // uniformly-distributed pseudo-random uint64 values in
  34 // the range [0, 1<<64) directly.
  35 // If a Rand r's underlying Source s implements Source64,
  36 // then r.Uint64 returns the result of one call to s.Uint64
  37 // instead of making two calls to s.Int64.
  38 type Source64 interface {
  39         Source
  40         Uint64() uint64
  41 }
  42
  43 // NewSource returns a new pseudo-random Source seeded with the given value.
  44 // Unlike the default Source used by top-level functions, this source is not
  45 // safe for concurrent use by multiple goroutines.
  46 // The returned Source implements Source64.
  47 func NewSource(seed int64) Source {
  48         return newSource(seed)
  49 }
  50
  51 func newSource(seed int64) *rngSource {
  52         var rng rngSource
  53         rng.Seed(seed)
  54         return &rng
  55 }
  56
  57 // A Rand is a source of random numbers.
  58 type Rand struct {
  59         src Source
  60         s64 Source64 // non-nil if src is source64
  61 }
  62
  63 // New returns a new Rand that uses random values from src
  64 // to generate other random values.
  65 func New(src Source) *Rand {
  66         s64, _ := src.(Source64)
  67         return &Rand{src: src, s64: s64}
  68 }
  69
  70 // Int64 returns a non-negative pseudo-random 63-bit integer as an int64.
  71 func (r *Rand) Int64() int64 { return r.src.Int64() }
  72
  73 // Uint32 returns a pseudo-random 32-bit value as a uint32.
  74 func (r *Rand) Uint32() uint32 { return uint32(r.Int64() >> 31) }
  75
  76 // Uint64 returns a pseudo-random 64-bit value as a uint64.
  77 func (r *Rand) Uint64() uint64 {
  78         if r.s64 != nil {
  79                 return r.s64.Uint64()
  80         }
  81         return uint64(r.Int64())>>31 | uint64(r.Int64())<<32
  82 }
  83
  84 // Int32 returns a non-negative pseudo-random 31-bit integer as an int32.
  85 func (r *Rand) Int32() int32 { return int32(r.Int64() >> 32) }
  86
  87 // Int returns a non-negative pseudo-random int.
  88 func (r *Rand) Int() int {
  89         u := uint(r.Int64())
  90         return int(u << 1 >> 1) // clear sign bit if int == int32
  91 }
  92
  93 // Int64N returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
  94 // It panics if n <= 0.
  95 func (r *Rand) Int64N(n int64) int64 {
  96         if n <= 0 {
  97                 panic("invalid argument to Int64N")
  98         }
  99         if n&(n-1) == 0 { // n is power of two, can mask
 100                 return r.Int64() & (n - 1)
 101         }
 102         max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
 103         v := r.Int64()
 104         for v > max {
 105                 v = r.Int64()
 106         }
 107         return v % n
 108 }
 109
 110 // Int32N returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
 111 // It panics if n <= 0.
 112 func (r *Rand) Int32N(n int32) int32 {
 113         if n <= 0 {
 114                 panic("invalid argument to Int32N")
 115         }
 116         if n&(n-1) == 0 { // n is power of two, can mask
 117                 return r.Int32() & (n - 1)
 118         }
 119         max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
 120         v := r.Int32()
 121         for v > max {
 122                 v = r.Int32()
 123         }
 124         return v % n
 125 }
 126
 127 // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
 128 // n must be > 0, but int31n does not check this; the caller must ensure it.
 129 // int31n exists because Int32N is inefficient, but Go 1 compatibility
 130 // requires that the stream of values produced by math/rand/v2 remain unchanged.
 131 // int31n can thus only be used internally, by newly introduced APIs.
 132 //
 133 // For implementation details, see:
 134 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
 135 // https://lemire.me/blog/2016/06/30/fast-random-shuffling
 136 func (r *Rand) int31n(n int32) int32 {
 137         v := r.Uint32()
 138         prod := uint64(v) * uint64(n)
 139         low := uint32(prod)
 140         if low < uint32(n) {
 141                 thresh := uint32(-n) % uint32(n)
 142                 for low < thresh {
 143                         v = r.Uint32()
 144                         prod = uint64(v) * uint64(n)
 145                         low = uint32(prod)
 146                 }
 147         }
 148         return int32(prod >> 32)
 149 }
 150
 151 // IntN returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
 152 // It panics if n <= 0.
 153 func (r *Rand) IntN(n int) int {
 154         if n <= 0 {
 155                 panic("invalid argument to IntN")
 156         }
 157         if n <= 1<<31-1 {
 158                 return int(r.Int32N(int32(n)))
 159         }
 160         return int(r.Int64N(int64(n)))
 161 }
 162
 163 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
 164 func (r *Rand) Float64() float64 {
 165         // A clearer, simpler implementation would be:
 166         //      return float64(r.Int64N(1<<53)) / (1<<53)
 167         // However, Go 1 shipped with
 168         //      return float64(r.Int64()) / (1 << 63)
 169         // and we want to preserve that value stream.
 170         //
 171         // There is one bug in the value stream: r.Int64() may be so close
 172         // to 1<<63 that the division rounds up to 1.0, and we've guaranteed
 173         // that the result is always less than 1.0.
 174         //
 175         // We tried to fix this by mapping 1.0 back to 0.0, but since float64
 176         // values near 0 are much denser than near 1, mapping 1 to 0 caused
 177         // a theoretically significant overshoot in the probability of returning 0.
 178         // Instead of that, if we round up to 1, just try again.
 179         // Getting 1 only happens 1/2⁵³ of the time, so most clients
 180         // will not observe it anyway.
 181 again:
 182         f := float64(r.Int64()) / (1 << 63)
 183         if f == 1 {
 184                 goto again // resample; this branch is taken O(never)
 185         }
 186         return f
 187 }
 188
 189 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
 190 func (r *Rand) Float32() float32 {
 191         // Same rationale as in Float64: we want to preserve the Go 1 value
 192         // stream except we want to fix it not to return 1.0
 193         // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
 194 again:
 195         f := float32(r.Float64())
 196         if f == 1 {
 197                 goto again // resample; this branch is taken O(very rarely)
 198         }
 199         return f
 200 }
 201
 202 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
 203 // in the half-open interval [0,n).
 204 func (r *Rand) Perm(n int) []int {
 205         m := make([]int, n)
 206         // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
 207         // A change to remove this useless iteration is to assign 1 to i in the init
 208         // statement. But Perm also effects r. Making this change will affect
 209         // the final state of r. So this change can't be made for compatibility
 210         // reasons for Go 1.
 211         for i := 0; i < n; i++ {
 212                 j := r.IntN(i + 1)
 213                 m[i] = m[j]
 214                 m[j] = i
 215         }
 216         return m
 217 }
 218
 219 // Shuffle pseudo-randomizes the order of elements.
 220 // n is the number of elements. Shuffle panics if n < 0.
 221 // swap swaps the elements with indexes i and j.
 222 func (r *Rand) Shuffle(n int, swap func(i, j int)) {
 223         if n < 0 {
 224                 panic("invalid argument to Shuffle")
 225         }
 226
 227         // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
 228         // Shuffle really ought not be called with n that doesn't fit in 32 bits.
 229         // Not only will it take a very long time, but with 2³¹! possible permutations,
 230         // there's no way that any PRNG can have a big enough internal state to
 231         // generate even a minuscule percentage of the possible permutations.
 232         // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
 233         i := n - 1
 234         for ; i > 1<<31-1-1; i-- {
 235                 j := int(r.Int64N(int64(i + 1)))
 236                 swap(i, j)
 237         }
 238         for ; i > 0; i-- {
 239                 j := int(r.int31n(int32(i + 1)))
 240                 swap(i, j)
 241         }
 242 }
 243
 244 /*
 245  * Top-level convenience functions
 246  */
 247
 248 // globalRand is the source of random numbers for the top-level
 249 // convenience functions.
 250 var globalRand = &Rand{src: &fastSource{}}
 251
 252 //go:linkname fastrand64
 253 func fastrand64() uint64
 254
 255 // fastSource is a Source that uses the runtime fastrand functions.
 256 type fastSource struct{}
 257
 258 func (*fastSource) Int64() int64 {
 259         return int64(fastrand64() & rngMask)
 260 }
 261
 262 func (*fastSource) Uint64() uint64 {
 263         return fastrand64()
 264 }
 265
 266 // Int64 returns a non-negative pseudo-random 63-bit integer as an int64
 267 // from the default Source.
 268 func Int64() int64 { return globalRand.Int64() }
 269
 270 // Uint32 returns a pseudo-random 32-bit value as a uint32
 271 // from the default Source.
 272 func Uint32() uint32 { return globalRand.Uint32() }
 273
 274 // Uint64 returns a pseudo-random 64-bit value as a uint64
 275 // from the default Source.
 276 func Uint64() uint64 { return globalRand.Uint64() }
 277
 278 // Int32 returns a non-negative pseudo-random 31-bit integer as an int32
 279 // from the default Source.
 280 func Int32() int32 { return globalRand.Int32() }
 281
 282 // Int returns a non-negative pseudo-random int from the default Source.
 283 func Int() int { return globalRand.Int() }
 284
 285 // Int64N returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
 286 // from the default Source.
 287 // It panics if n <= 0.
 288 func Int64N(n int64) int64 { return globalRand.Int64N(n) }
 289
 290 // Int32N returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
 291 // from the default Source.
 292 // It panics if n <= 0.
 293 func Int32N(n int32) int32 { return globalRand.Int32N(n) }
 294
 295 // IntN returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
 296 // from the default Source.
 297 // It panics if n <= 0.
 298 func IntN(n int) int { return globalRand.IntN(n) }
 299
 300 // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
 301 // from the default Source.
 302 func Float64() float64 { return globalRand.Float64() }
 303
 304 // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
 305 // from the default Source.
 306 func Float32() float32 { return globalRand.Float32() }
 307
 308 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
 309 // in the half-open interval [0,n) from the default Source.
 310 func Perm(n int) []int { return globalRand.Perm(n) }
 311
 312 // Shuffle pseudo-randomizes the order of elements using the default Source.
 313 // n is the number of elements. Shuffle panics if n < 0.
 314 // swap swaps the elements with indexes i and j.
 315 func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }
 316
 317 // NormFloat64 returns a normally distributed float64 in the range
 318 // [-math.MaxFloat64, +math.MaxFloat64] with
 319 // standard normal distribution (mean = 0, stddev = 1)
 320 // from the default Source.
 321 // To produce a different normal distribution, callers can
 322 // adjust the output using:
 323 //
 324 //      sample = NormFloat64() * desiredStdDev + desiredMean
 325 func NormFloat64() float64 { return globalRand.NormFloat64() }
 326
 327 // ExpFloat64 returns an exponentially distributed float64 in the range
 328 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
 329 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
 330 // To produce a distribution with a different rate parameter,
 331 // callers can adjust the output using:
 332 //
 333 //      sample = ExpFloat64() / desiredRateParameter
 334 func ExpFloat64() float64 { return globalRand.ExpFloat64() }