libgo/go/math/rand/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.
   6 //
   7 // Random numbers are generated by a Source. Top-level functions, such as
   8 // Float64 and Int, use a default shared Source that produces a deterministic
   9 // sequence of values each time a program is run. Use the Seed function to
  10 // initialize the default Source if different behavior is required for each run.
  11 // The default Source is safe for concurrent use by multiple goroutines.
  12 package rand
  13
  14 import "sync"
  15
  16 // A Source represents a source of uniformly-distributed
  17 // pseudo-random int64 values in the range [0, 1<<63).
  18 type Source interface {
  19         Int63() int64
  20         Seed(seed int64)
  21 }
  22
  23 // NewSource returns a new pseudo-random Source seeded with the given value.
  24 func NewSource(seed int64) Source {
  25         var rng rngSource
  26         rng.Seed(seed)
  27         return &rng
  28 }
  29
  30 // A Rand is a source of random numbers.
  31 type Rand struct {
  32         src Source
  33 }
  34
  35 // New returns a new Rand that uses random values from src
  36 // to generate other random values.
  37 func New(src Source) *Rand { return &Rand{src} }
  38
  39 // Seed uses the provided seed value to initialize the generator to a deterministic state.
  40 func (r *Rand) Seed(seed int64) { r.src.Seed(seed) }
  41
  42 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
  43 func (r *Rand) Int63() int64 { return r.src.Int63() }
  44
  45 // Uint32 returns a pseudo-random 32-bit value as a uint32.
  46 func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
  47
  48 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
  49 func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
  50
  51 // Int returns a non-negative pseudo-random int.
  52 func (r *Rand) Int() int {
  53         u := uint(r.Int63())
  54         return int(u << 1 >> 1) // clear sign bit if int == int32
  55 }
  56
  57 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n).
  58 // It panics if n <= 0.
  59 func (r *Rand) Int63n(n int64) int64 {
  60         if n <= 0 {
  61                 panic("invalid argument to Int63n")
  62         }
  63         if n&(n-1) == 0 { // n is power of two, can mask
  64                 return r.Int63() & (n - 1)
  65         }
  66         max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
  67         v := r.Int63()
  68         for v > max {
  69                 v = r.Int63()
  70         }
  71         return v % n
  72 }
  73
  74 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
  75 // It panics if n <= 0.
  76 func (r *Rand) Int31n(n int32) int32 {
  77         if n <= 0 {
  78                 panic("invalid argument to Int31n")
  79         }
  80         if n&(n-1) == 0 { // n is power of two, can mask
  81                 return r.Int31() & (n - 1)
  82         }
  83         max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
  84         v := r.Int31()
  85         for v > max {
  86                 v = r.Int31()
  87         }
  88         return v % n
  89 }
  90
  91 // Intn returns, as an int, a non-negative pseudo-random number in [0,n).
  92 // It panics if n <= 0.
  93 func (r *Rand) Intn(n int) int {
  94         if n <= 0 {
  95                 panic("invalid argument to Intn")
  96         }
  97         if n <= 1<<31-1 {
  98                 return int(r.Int31n(int32(n)))
  99         }
 100         return int(r.Int63n(int64(n)))
 101 }
 102
 103 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
 104 func (r *Rand) Float64() float64 {
 105         // A clearer, simpler implementation would be:
 106         //      return float64(r.Int63n(1<<53)) / (1<<53)
 107         // However, Go 1 shipped with
 108         //      return float64(r.Int63()) / (1 << 63)
 109         // and we want to preserve that value stream.
 110         //
 111         // There is one bug in the value stream: r.Int63() may be so close
 112         // to 1<<63 that the division rounds up to 1.0, and we've guaranteed
 113         // that the result is always less than 1.0. To fix that, we treat the
 114         // range as cyclic and map 1 back to 0. This is justified by observing
 115         // that while some of the values rounded down to 0, nothing was
 116         // rounding up to 0, so 0 was underrepresented in the results.
 117         // Mapping 1 back to zero restores some balance.
 118         // (The balance is not perfect because the implementation
 119         // returns denormalized numbers for very small r.Int63(),
 120         // and those steal from what would normally be 0 results.)
 121         // The remapping only happens 1/2⁵³ of the time, so most clients
 122         // will not observe it anyway.
 123         f := float64(r.Int63()) / (1 << 63)
 124         if f == 1 {
 125                 f = 0
 126         }
 127         return f
 128 }
 129
 130 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).
 131 func (r *Rand) Float32() float32 {
 132         // Same rationale as in Float64: we want to preserve the Go 1 value
 133         // stream except we want to fix it not to return 1.0
 134         // There is a double rounding going on here, but the argument for
 135         // mapping 1 to 0 still applies: 0 was underrepresented before,
 136         // so mapping 1 to 0 doesn't cause too many 0s.
 137         // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
 138         f := float32(r.Float64())
 139         if f == 1 {
 140                 f = 0
 141         }
 142         return f
 143 }
 144
 145 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
 146 func (r *Rand) Perm(n int) []int {
 147         m := make([]int, n)
 148         for i := 0; i < n; i++ {
 149                 j := r.Intn(i + 1)
 150                 m[i] = m[j]
 151                 m[j] = i
 152         }
 153         return m
 154 }
 155
 156 /*
 157  * Top-level convenience functions
 158  */
 159
 160 var globalRand = New(&lockedSource{src: NewSource(1)})
 161
 162 // Seed uses the provided seed value to initialize the default Source to a
 163 // deterministic state. If Seed is not called, the generator behaves as
 164 // if seeded by Seed(1).
 165 func Seed(seed int64) { globalRand.Seed(seed) }
 166
 167 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
 168 // from the default Source.
 169 func Int63() int64 { return globalRand.Int63() }
 170
 171 // Uint32 returns a pseudo-random 32-bit value as a uint32
 172 // from the default Source.
 173 func Uint32() uint32 { return globalRand.Uint32() }
 174
 175 // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
 176 // from the default Source.
 177 func Int31() int32 { return globalRand.Int31() }
 178
 179 // Int returns a non-negative pseudo-random int from the default Source.
 180 func Int() int { return globalRand.Int() }
 181
 182 // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n)
 183 // from the default Source.
 184 // It panics if n <= 0.
 185 func Int63n(n int64) int64 { return globalRand.Int63n(n) }
 186
 187 // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n)
 188 // from the default Source.
 189 // It panics if n <= 0.
 190 func Int31n(n int32) int32 { return globalRand.Int31n(n) }
 191
 192 // Intn returns, as an int, a non-negative pseudo-random number in [0,n)
 193 // from the default Source.
 194 // It panics if n <= 0.
 195 func Intn(n int) int { return globalRand.Intn(n) }
 196
 197 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0)
 198 // from the default Source.
 199 func Float64() float64 { return globalRand.Float64() }
 200
 201 // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0)
 202 // from the default Source.
 203 func Float32() float32 { return globalRand.Float32() }
 204
 205 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n)
 206 // from the default Source.
 207 func Perm(n int) []int { return globalRand.Perm(n) }
 208
 209 // NormFloat64 returns a normally distributed float64 in the range
 210 // [-math.MaxFloat64, +math.MaxFloat64] with
 211 // standard normal distribution (mean = 0, stddev = 1)
 212 // from the default Source.
 213 // To produce a different normal distribution, callers can
 214 // adjust the output using:
 215 //
 216 //  sample = NormFloat64() * desiredStdDev + desiredMean
 217 //
 218 func NormFloat64() float64 { return globalRand.NormFloat64() }
 219
 220 // ExpFloat64 returns an exponentially distributed float64 in the range
 221 // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
 222 // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
 223 // To produce a distribution with a different rate parameter,
 224 // callers can adjust the output using:
 225 //
 226 //  sample = ExpFloat64() / desiredRateParameter
 227 //
 228 func ExpFloat64() float64 { return globalRand.ExpFloat64() }
 229
 230 type lockedSource struct {
 231         lk  sync.Mutex
 232         src Source
 233 }
 234
 235 func (r *lockedSource) Int63() (n int64) {
 236         r.lk.Lock()
 237         n = r.src.Int63()
 238         r.lk.Unlock()
 239         return
 240 }
 241
 242 func (r *lockedSource) Seed(seed int64) {
 243         r.lk.Lock()
 244         r.src.Seed(seed)
 245         r.lk.Unlock()
 246 }