...

Source file src/math/rand/rand.go

Documentation: math/rand

		 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 unsuitable for
		 6  // security-sensitive work.
		 7  //
		 8  // Random numbers are generated by a Source. Top-level functions, such as
		 9  // Float64 and Int, use a default shared Source that produces a deterministic
		10  // sequence of values each time a program is run. Use the Seed function to
		11  // initialize the default Source if different behavior is required for each run.
		12  // The default Source is safe for concurrent use by multiple goroutines, but
		13  // Sources created by NewSource are not.
		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 "sync"
		21  
		22  // A Source represents a source of uniformly-distributed
		23  // pseudo-random int64 values in the range [0, 1<<63).
		24  type Source interface {
		25  	Int63() int64
		26  	Seed(seed int64)
		27  }
		28  
		29  // A Source64 is a Source that can also generate
		30  // uniformly-distributed pseudo-random uint64 values in
		31  // the range [0, 1<<64) directly.
		32  // If a Rand r's underlying Source s implements Source64,
		33  // then r.Uint64 returns the result of one call to s.Uint64
		34  // instead of making two calls to s.Int63.
		35  type Source64 interface {
		36  	Source
		37  	Uint64() uint64
		38  }
		39  
		40  // NewSource returns a new pseudo-random Source seeded with the given value.
		41  // Unlike the default Source used by top-level functions, this source is not
		42  // safe for concurrent use by multiple goroutines.
		43  func NewSource(seed int64) Source {
		44  	var rng rngSource
		45  	rng.Seed(seed)
		46  	return &rng
		47  }
		48  
		49  // A Rand is a source of random numbers.
		50  type Rand struct {
		51  	src Source
		52  	s64 Source64 // non-nil if src is source64
		53  
		54  	// readVal contains remainder of 63-bit integer used for bytes
		55  	// generation during most recent Read call.
		56  	// It is saved so next Read call can start where the previous
		57  	// one finished.
		58  	readVal int64
		59  	// readPos indicates the number of low-order bytes of readVal
		60  	// that are still valid.
		61  	readPos int8
		62  }
		63  
		64  // New returns a new Rand that uses random values from src
		65  // to generate other random values.
		66  func New(src Source) *Rand {
		67  	s64, _ := src.(Source64)
		68  	return &Rand{src: src, s64: s64}
		69  }
		70  
		71  // Seed uses the provided seed value to initialize the generator to a deterministic state.
		72  // Seed should not be called concurrently with any other Rand method.
		73  func (r *Rand) Seed(seed int64) {
		74  	if lk, ok := r.src.(*lockedSource); ok {
		75  		lk.seedPos(seed, &r.readPos)
		76  		return
		77  	}
		78  
		79  	r.src.Seed(seed)
		80  	r.readPos = 0
		81  }
		82  
		83  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
		84  func (r *Rand) Int63() int64 { return r.src.Int63() }
		85  
		86  // Uint32 returns a pseudo-random 32-bit value as a uint32.
		87  func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
		88  
		89  // Uint64 returns a pseudo-random 64-bit value as a uint64.
		90  func (r *Rand) Uint64() uint64 {
		91  	if r.s64 != nil {
		92  		return r.s64.Uint64()
		93  	}
		94  	return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
		95  }
		96  
		97  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
		98  func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
		99  
	 100  // Int returns a non-negative pseudo-random int.
	 101  func (r *Rand) Int() int {
	 102  	u := uint(r.Int63())
	 103  	return int(u << 1 >> 1) // clear sign bit if int == int32
	 104  }
	 105  
	 106  // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
	 107  // It panics if n <= 0.
	 108  func (r *Rand) Int63n(n int64) int64 {
	 109  	if n <= 0 {
	 110  		panic("invalid argument to Int63n")
	 111  	}
	 112  	if n&(n-1) == 0 { // n is power of two, can mask
	 113  		return r.Int63() & (n - 1)
	 114  	}
	 115  	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
	 116  	v := r.Int63()
	 117  	for v > max {
	 118  		v = r.Int63()
	 119  	}
	 120  	return v % n
	 121  }
	 122  
	 123  // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
	 124  // It panics if n <= 0.
	 125  func (r *Rand) Int31n(n int32) int32 {
	 126  	if n <= 0 {
	 127  		panic("invalid argument to Int31n")
	 128  	}
	 129  	if n&(n-1) == 0 { // n is power of two, can mask
	 130  		return r.Int31() & (n - 1)
	 131  	}
	 132  	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
	 133  	v := r.Int31()
	 134  	for v > max {
	 135  		v = r.Int31()
	 136  	}
	 137  	return v % n
	 138  }
	 139  
	 140  // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
	 141  // n must be > 0, but int31n does not check this; the caller must ensure it.
	 142  // int31n exists because Int31n is inefficient, but Go 1 compatibility
	 143  // requires that the stream of values produced by math/rand remain unchanged.
	 144  // int31n can thus only be used internally, by newly introduced APIs.
	 145  //
	 146  // For implementation details, see:
	 147  // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
	 148  // https://lemire.me/blog/2016/06/30/fast-random-shuffling
	 149  func (r *Rand) int31n(n int32) int32 {
	 150  	v := r.Uint32()
	 151  	prod := uint64(v) * uint64(n)
	 152  	low := uint32(prod)
	 153  	if low < uint32(n) {
	 154  		thresh := uint32(-n) % uint32(n)
	 155  		for low < thresh {
	 156  			v = r.Uint32()
	 157  			prod = uint64(v) * uint64(n)
	 158  			low = uint32(prod)
	 159  		}
	 160  	}
	 161  	return int32(prod >> 32)
	 162  }
	 163  
	 164  // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
	 165  // It panics if n <= 0.
	 166  func (r *Rand) Intn(n int) int {
	 167  	if n <= 0 {
	 168  		panic("invalid argument to Intn")
	 169  	}
	 170  	if n <= 1<<31-1 {
	 171  		return int(r.Int31n(int32(n)))
	 172  	}
	 173  	return int(r.Int63n(int64(n)))
	 174  }
	 175  
	 176  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
	 177  func (r *Rand) Float64() float64 {
	 178  	// A clearer, simpler implementation would be:
	 179  	//	return float64(r.Int63n(1<<53)) / (1<<53)
	 180  	// However, Go 1 shipped with
	 181  	//	return float64(r.Int63()) / (1 << 63)
	 182  	// and we want to preserve that value stream.
	 183  	//
	 184  	// There is one bug in the value stream: r.Int63() may be so close
	 185  	// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
	 186  	// that the result is always less than 1.0.
	 187  	//
	 188  	// We tried to fix this by mapping 1.0 back to 0.0, but since float64
	 189  	// values near 0 are much denser than near 1, mapping 1 to 0 caused
	 190  	// a theoretically significant overshoot in the probability of returning 0.
	 191  	// Instead of that, if we round up to 1, just try again.
	 192  	// Getting 1 only happens 1/2⁵³ of the time, so most clients
	 193  	// will not observe it anyway.
	 194  again:
	 195  	f := float64(r.Int63()) / (1 << 63)
	 196  	if f == 1 {
	 197  		goto again // resample; this branch is taken O(never)
	 198  	}
	 199  	return f
	 200  }
	 201  
	 202  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
	 203  func (r *Rand) Float32() float32 {
	 204  	// Same rationale as in Float64: we want to preserve the Go 1 value
	 205  	// stream except we want to fix it not to return 1.0
	 206  	// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
	 207  again:
	 208  	f := float32(r.Float64())
	 209  	if f == 1 {
	 210  		goto again // resample; this branch is taken O(very rarely)
	 211  	}
	 212  	return f
	 213  }
	 214  
	 215  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
	 216  // in the half-open interval [0,n).
	 217  func (r *Rand) Perm(n int) []int {
	 218  	m := make([]int, n)
	 219  	// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
	 220  	// A change to remove this useless iteration is to assign 1 to i in the init
	 221  	// statement. But Perm also effects r. Making this change will affect
	 222  	// the final state of r. So this change can't be made for compatibility
	 223  	// reasons for Go 1.
	 224  	for i := 0; i < n; i++ {
	 225  		j := r.Intn(i + 1)
	 226  		m[i] = m[j]
	 227  		m[j] = i
	 228  	}
	 229  	return m
	 230  }
	 231  
	 232  // Shuffle pseudo-randomizes the order of elements.
	 233  // n is the number of elements. Shuffle panics if n < 0.
	 234  // swap swaps the elements with indexes i and j.
	 235  func (r *Rand) Shuffle(n int, swap func(i, j int)) {
	 236  	if n < 0 {
	 237  		panic("invalid argument to Shuffle")
	 238  	}
	 239  
	 240  	// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
	 241  	// Shuffle really ought not be called with n that doesn't fit in 32 bits.
	 242  	// Not only will it take a very long time, but with 2³¹! possible permutations,
	 243  	// there's no way that any PRNG can have a big enough internal state to
	 244  	// generate even a minuscule percentage of the possible permutations.
	 245  	// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
	 246  	i := n - 1
	 247  	for ; i > 1<<31-1-1; i-- {
	 248  		j := int(r.Int63n(int64(i + 1)))
	 249  		swap(i, j)
	 250  	}
	 251  	for ; i > 0; i-- {
	 252  		j := int(r.int31n(int32(i + 1)))
	 253  		swap(i, j)
	 254  	}
	 255  }
	 256  
	 257  // Read generates len(p) random bytes and writes them into p. It
	 258  // always returns len(p) and a nil error.
	 259  // Read should not be called concurrently with any other Rand method.
	 260  func (r *Rand) Read(p []byte) (n int, err error) {
	 261  	if lk, ok := r.src.(*lockedSource); ok {
	 262  		return lk.read(p, &r.readVal, &r.readPos)
	 263  	}
	 264  	return read(p, r.src, &r.readVal, &r.readPos)
	 265  }
	 266  
	 267  func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
	 268  	pos := *readPos
	 269  	val := *readVal
	 270  	rng, _ := src.(*rngSource)
	 271  	for n = 0; n < len(p); n++ {
	 272  		if pos == 0 {
	 273  			if rng != nil {
	 274  				val = rng.Int63()
	 275  			} else {
	 276  				val = src.Int63()
	 277  			}
	 278  			pos = 7
	 279  		}
	 280  		p[n] = byte(val)
	 281  		val >>= 8
	 282  		pos--
	 283  	}
	 284  	*readPos = pos
	 285  	*readVal = val
	 286  	return
	 287  }
	 288  
	 289  /*
	 290   * Top-level convenience functions
	 291   */
	 292  
	 293  var globalRand = New(&lockedSource{src: NewSource(1).(*rngSource)})
	 294  
	 295  // Type assert that globalRand's source is a lockedSource whose src is a *rngSource.
	 296  var _ *rngSource = globalRand.src.(*lockedSource).src
	 297  
	 298  // Seed uses the provided seed value to initialize the default Source to a
	 299  // deterministic state. If Seed is not called, the generator behaves as
	 300  // if seeded by Seed(1). Seed values that have the same remainder when
	 301  // divided by 2³¹-1 generate the same pseudo-random sequence.
	 302  // Seed, unlike the Rand.Seed method, is safe for concurrent use.
	 303  func Seed(seed int64) { globalRand.Seed(seed) }
	 304  
	 305  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
	 306  // from the default Source.
	 307  func Int63() int64 { return globalRand.Int63() }
	 308  
	 309  // Uint32 returns a pseudo-random 32-bit value as a uint32
	 310  // from the default Source.
	 311  func Uint32() uint32 { return globalRand.Uint32() }
	 312  
	 313  // Uint64 returns a pseudo-random 64-bit value as a uint64
	 314  // from the default Source.
	 315  func Uint64() uint64 { return globalRand.Uint64() }
	 316  
	 317  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
	 318  // from the default Source.
	 319  func Int31() int32 { return globalRand.Int31() }
	 320  
	 321  // Int returns a non-negative pseudo-random int from the default Source.
	 322  func Int() int { return globalRand.Int() }
	 323  
	 324  // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
	 325  // from the default Source.
	 326  // It panics if n <= 0.
	 327  func Int63n(n int64) int64 { return globalRand.Int63n(n) }
	 328  
	 329  // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
	 330  // from the default Source.
	 331  // It panics if n <= 0.
	 332  func Int31n(n int32) int32 { return globalRand.Int31n(n) }
	 333  
	 334  // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
	 335  // from the default Source.
	 336  // It panics if n <= 0.
	 337  func Intn(n int) int { return globalRand.Intn(n) }
	 338  
	 339  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
	 340  // from the default Source.
	 341  func Float64() float64 { return globalRand.Float64() }
	 342  
	 343  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
	 344  // from the default Source.
	 345  func Float32() float32 { return globalRand.Float32() }
	 346  
	 347  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
	 348  // in the half-open interval [0,n) from the default Source.
	 349  func Perm(n int) []int { return globalRand.Perm(n) }
	 350  
	 351  // Shuffle pseudo-randomizes the order of elements using the default Source.
	 352  // n is the number of elements. Shuffle panics if n < 0.
	 353  // swap swaps the elements with indexes i and j.
	 354  func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }
	 355  
	 356  // Read generates len(p) random bytes from the default Source and
	 357  // writes them into p. It always returns len(p) and a nil error.
	 358  // Read, unlike the Rand.Read method, is safe for concurrent use.
	 359  func Read(p []byte) (n int, err error) { return globalRand.Read(p) }
	 360  
	 361  // NormFloat64 returns a normally distributed float64 in the range
	 362  // [-math.MaxFloat64, +math.MaxFloat64] with
	 363  // standard normal distribution (mean = 0, stddev = 1)
	 364  // from the default Source.
	 365  // To produce a different normal distribution, callers can
	 366  // adjust the output using:
	 367  //
	 368  //	sample = NormFloat64() * desiredStdDev + desiredMean
	 369  //
	 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  //
	 380  func ExpFloat64() float64 { return globalRand.ExpFloat64() }
	 381  
	 382  type lockedSource struct {
	 383  	lk	sync.Mutex
	 384  	src *rngSource
	 385  }
	 386  
	 387  func (r *lockedSource) Int63() (n int64) {
	 388  	r.lk.Lock()
	 389  	n = r.src.Int63()
	 390  	r.lk.Unlock()
	 391  	return
	 392  }
	 393  
	 394  func (r *lockedSource) Uint64() (n uint64) {
	 395  	r.lk.Lock()
	 396  	n = r.src.Uint64()
	 397  	r.lk.Unlock()
	 398  	return
	 399  }
	 400  
	 401  func (r *lockedSource) Seed(seed int64) {
	 402  	r.lk.Lock()
	 403  	r.src.Seed(seed)
	 404  	r.lk.Unlock()
	 405  }
	 406  
	 407  // seedPos implements Seed for a lockedSource without a race condition.
	 408  func (r *lockedSource) seedPos(seed int64, readPos *int8) {
	 409  	r.lk.Lock()
	 410  	r.src.Seed(seed)
	 411  	*readPos = 0
	 412  	r.lk.Unlock()
	 413  }
	 414  
	 415  // read implements Read for a lockedSource without a race condition.
	 416  func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
	 417  	r.lk.Lock()
	 418  	n, err = read(p, r.src, readVal, readPos)
	 419  	r.lk.Unlock()
	 420  	return
	 421  }
	 422  

View as plain text