...
Run Format

Source file src/math/rand/rand.go

Documentation: math/rand

  // Copyright 2009 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  // Package rand implements pseudo-random number generators.
  //
  // Random numbers are generated by a Source. Top-level functions, such as
  // Float64 and Int, use a default shared Source that produces a deterministic
  // sequence of values each time a program is run. Use the Seed function to
  // initialize the default Source if different behavior is required for each run.
  // The default Source is safe for concurrent use by multiple goroutines, but
  // Sources created by NewSource are not.
  //
  // For random numbers suitable for security-sensitive work, see the crypto/rand
  // package.
  package rand
  
  import "sync"
  
  // A Source represents a source of uniformly-distributed
  // pseudo-random int64 values in the range [0, 1<<63).
  type Source interface {
  	Int63() int64
  	Seed(seed int64)
  }
  
  // A Source64 is a Source that can also generate
  // uniformly-distributed pseudo-random uint64 values in
  // the range [0, 1<<64) directly.
  // If a Rand r's underlying Source s implements Source64,
  // then r.Uint64 returns the result of one call to s.Uint64
  // instead of making two calls to s.Int63.
  type Source64 interface {
  	Source
  	Uint64() uint64
  }
  
  // NewSource returns a new pseudo-random Source seeded with the given value.
  // Unlike the default Source used by top-level functions, this source is not
  // safe for concurrent use by multiple goroutines.
  func NewSource(seed int64) Source {
  	var rng rngSource
  	rng.Seed(seed)
  	return &rng
  }
  
  // A Rand is a source of random numbers.
  type Rand struct {
  	src Source
  	s64 Source64 // non-nil if src is source64
  
  	// readVal contains remainder of 63-bit integer used for bytes
  	// generation during most recent Read call.
  	// It is saved so next Read call can start where the previous
  	// one finished.
  	readVal int64
  	// readPos indicates the number of low-order bytes of readVal
  	// that are still valid.
  	readPos int8
  }
  
  // New returns a new Rand that uses random values from src
  // to generate other random values.
  func New(src Source) *Rand {
  	s64, _ := src.(Source64)
  	return &Rand{src: src, s64: s64}
  }
  
  // Seed uses the provided seed value to initialize the generator to a deterministic state.
  // Seed should not be called concurrently with any other Rand method.
  func (r *Rand) Seed(seed int64) {
  	if lk, ok := r.src.(*lockedSource); ok {
  		lk.seedPos(seed, &r.readPos)
  		return
  	}
  
  	r.src.Seed(seed)
  	r.readPos = 0
  }
  
  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
  func (r *Rand) Int63() int64 { return r.src.Int63() }
  
  // Uint32 returns a pseudo-random 32-bit value as a uint32.
  func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
  
  // Uint64 returns a pseudo-random 64-bit value as a uint64.
  func (r *Rand) Uint64() uint64 {
  	if r.s64 != nil {
  		return r.s64.Uint64()
  	}
  	return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
  }
  
  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
  func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
  
  // Int returns a non-negative pseudo-random int.
  func (r *Rand) Int() int {
  	u := uint(r.Int63())
  	return int(u << 1 >> 1) // clear sign bit if int == int32
  }
  
  // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n).
  // It panics if n <= 0.
  func (r *Rand) Int63n(n int64) int64 {
  	if n <= 0 {
  		panic("invalid argument to Int63n")
  	}
  	if n&(n-1) == 0 { // n is power of two, can mask
  		return r.Int63() & (n - 1)
  	}
  	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
  	v := r.Int63()
  	for v > max {
  		v = r.Int63()
  	}
  	return v % n
  }
  
  // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
  // It panics if n <= 0.
  func (r *Rand) Int31n(n int32) int32 {
  	if n <= 0 {
  		panic("invalid argument to Int31n")
  	}
  	if n&(n-1) == 0 { // n is power of two, can mask
  		return r.Int31() & (n - 1)
  	}
  	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
  	v := r.Int31()
  	for v > max {
  		v = r.Int31()
  	}
  	return v % n
  }
  
  // Intn returns, as an int, a non-negative pseudo-random number in [0,n).
  // It panics if n <= 0.
  func (r *Rand) Intn(n int) int {
  	if n <= 0 {
  		panic("invalid argument to Intn")
  	}
  	if n <= 1<<31-1 {
  		return int(r.Int31n(int32(n)))
  	}
  	return int(r.Int63n(int64(n)))
  }
  
  // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
  func (r *Rand) Float64() float64 {
  	// A clearer, simpler implementation would be:
  	//	return float64(r.Int63n(1<<53)) / (1<<53)
  	// However, Go 1 shipped with
  	//	return float64(r.Int63()) / (1 << 63)
  	// and we want to preserve that value stream.
  	//
  	// There is one bug in the value stream: r.Int63() may be so close
  	// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
  	// that the result is always less than 1.0.
  	//
  	// We tried to fix this by mapping 1.0 back to 0.0, but since float64
  	// values near 0 are much denser than near 1, mapping 1 to 0 caused
  	// a theoretically significant overshoot in the probability of returning 0.
  	// Instead of that, if we round up to 1, just try again.
  	// Getting 1 only happens 1/2⁵³ of the time, so most clients
  	// will not observe it anyway.
  again:
  	f := float64(r.Int63()) / (1 << 63)
  	if f == 1 {
  		goto again // resample; this branch is taken O(never)
  	}
  	return f
  }
  
  // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).
  func (r *Rand) Float32() float32 {
  	// Same rationale as in Float64: we want to preserve the Go 1 value
  	// stream except we want to fix it not to return 1.0
  	// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
  again:
  	f := float32(r.Float64())
  	if f == 1 {
  		goto again // resample; this branch is taken O(very rarely)
  	}
  	return f
  }
  
  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
  func (r *Rand) Perm(n int) []int {
  	m := make([]int, n)
  	// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
  	// A change to remove this useless iteration is to assign 1 to i in the init
  	// statement. But Perm also effects r. Making this change will affect
  	// the final state of r. So this change can't be made for compatibility
  	// reasons for Go 1.
  	for i := 0; i < n; i++ {
  		j := r.Intn(i + 1)
  		m[i] = m[j]
  		m[j] = i
  	}
  	return m
  }
  
  // Read generates len(p) random bytes and writes them into p. It
  // always returns len(p) and a nil error.
  // Read should not be called concurrently with any other Rand method.
  func (r *Rand) Read(p []byte) (n int, err error) {
  	if lk, ok := r.src.(*lockedSource); ok {
  		return lk.read(p, &r.readVal, &r.readPos)
  	}
  	return read(p, r.Int63, &r.readVal, &r.readPos)
  }
  
  func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, err error) {
  	pos := *readPos
  	val := *readVal
  	for n = 0; n < len(p); n++ {
  		if pos == 0 {
  			val = int63()
  			pos = 7
  		}
  		p[n] = byte(val)
  		val >>= 8
  		pos--
  	}
  	*readPos = pos
  	*readVal = val
  	return
  }
  
  /*
   * Top-level convenience functions
   */
  
  var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})
  
  // Seed uses the provided seed value to initialize the default Source to a
  // deterministic state. If Seed is not called, the generator behaves as
  // if seeded by Seed(1). Seed values that have the same remainder when
  // divided by 2^31-1 generate the same pseudo-random sequence.
  // Seed, unlike the Rand.Seed method, is safe for concurrent use.
  func Seed(seed int64) { globalRand.Seed(seed) }
  
  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
  // from the default Source.
  func Int63() int64 { return globalRand.Int63() }
  
  // Uint32 returns a pseudo-random 32-bit value as a uint32
  // from the default Source.
  func Uint32() uint32 { return globalRand.Uint32() }
  
  // Uint64 returns a pseudo-random 64-bit value as a uint64
  // from the default Source.
  func Uint64() uint64 { return globalRand.Uint64() }
  
  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
  // from the default Source.
  func Int31() int32 { return globalRand.Int31() }
  
  // Int returns a non-negative pseudo-random int from the default Source.
  func Int() int { return globalRand.Int() }
  
  // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n)
  // from the default Source.
  // It panics if n <= 0.
  func Int63n(n int64) int64 { return globalRand.Int63n(n) }
  
  // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n)
  // from the default Source.
  // It panics if n <= 0.
  func Int31n(n int32) int32 { return globalRand.Int31n(n) }
  
  // Intn returns, as an int, a non-negative pseudo-random number in [0,n)
  // from the default Source.
  // It panics if n <= 0.
  func Intn(n int) int { return globalRand.Intn(n) }
  
  // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0)
  // from the default Source.
  func Float64() float64 { return globalRand.Float64() }
  
  // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0)
  // from the default Source.
  func Float32() float32 { return globalRand.Float32() }
  
  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n)
  // from the default Source.
  func Perm(n int) []int { return globalRand.Perm(n) }
  
  // Read generates len(p) random bytes from the default Source and
  // writes them into p. It always returns len(p) and a nil error.
  // Read, unlike the Rand.Read method, is safe for concurrent use.
  func Read(p []byte) (n int, err error) { return globalRand.Read(p) }
  
  // NormFloat64 returns a normally distributed float64 in the range
  // [-math.MaxFloat64, +math.MaxFloat64] with
  // standard normal distribution (mean = 0, stddev = 1)
  // from the default Source.
  // To produce a different normal distribution, callers can
  // adjust the output using:
  //
  //  sample = NormFloat64() * desiredStdDev + desiredMean
  //
  func NormFloat64() float64 { return globalRand.NormFloat64() }
  
  // ExpFloat64 returns an exponentially distributed float64 in the range
  // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
  // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
  // To produce a distribution with a different rate parameter,
  // callers can adjust the output using:
  //
  //  sample = ExpFloat64() / desiredRateParameter
  //
  func ExpFloat64() float64 { return globalRand.ExpFloat64() }
  
  type lockedSource struct {
  	lk  sync.Mutex
  	src Source64
  }
  
  func (r *lockedSource) Int63() (n int64) {
  	r.lk.Lock()
  	n = r.src.Int63()
  	r.lk.Unlock()
  	return
  }
  
  func (r *lockedSource) Uint64() (n uint64) {
  	r.lk.Lock()
  	n = r.src.Uint64()
  	r.lk.Unlock()
  	return
  }
  
  func (r *lockedSource) Seed(seed int64) {
  	r.lk.Lock()
  	r.src.Seed(seed)
  	r.lk.Unlock()
  }
  
  // seedPos implements Seed for a lockedSource without a race condiiton.
  func (r *lockedSource) seedPos(seed int64, readPos *int8) {
  	r.lk.Lock()
  	r.src.Seed(seed)
  	*readPos = 0
  	r.lk.Unlock()
  }
  
  // read implements Read for a lockedSource without a race condition.
  func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
  	r.lk.Lock()
  	n, err = read(p, r.src.Int63, readVal, readPos)
  	r.lk.Unlock()
  	return
  }
  

View as plain text