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.
     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, but
    12  // Sources created by NewSource are not.
    13  //
    14  // Mathematical interval notation such as [0, n) is used throughout the
    15  // documentation for this package.
    16  //
    17  // For random numbers suitable for security-sensitive work, see the crypto/rand
    18  // package.
    19  package rand
    20  
    21  import "sync"
    22  
    23  // A Source represents a source of uniformly-distributed
    24  // pseudo-random int64 values in the range [0, 1<<63).
    25  type Source interface {
    26  	Int63() int64
    27  	Seed(seed int64)
    28  }
    29  
    30  // A Source64 is a Source that can also generate
    31  // uniformly-distributed pseudo-random uint64 values in
    32  // the range [0, 1<<64) directly.
    33  // If a Rand r's underlying Source s implements Source64,
    34  // then r.Uint64 returns the result of one call to s.Uint64
    35  // instead of making two calls to s.Int63.
    36  type Source64 interface {
    37  	Source
    38  	Uint64() uint64
    39  }
    40  
    41  // NewSource returns a new pseudo-random Source seeded with the given value.
    42  // Unlike the default Source used by top-level functions, this source is not
    43  // safe for concurrent use by multiple goroutines.
    44  func NewSource(seed int64) Source {
    45  	var rng rngSource
    46  	rng.Seed(seed)
    47  	return &rng
    48  }
    49  
    50  // A Rand is a source of random numbers.
    51  type Rand struct {
    52  	src Source
    53  	s64 Source64 // non-nil if src is source64
    54  
    55  	// readVal contains remainder of 63-bit integer used for bytes
    56  	// generation during most recent Read call.
    57  	// It is saved so next Read call can start where the previous
    58  	// one finished.
    59  	readVal int64
    60  	// readPos indicates the number of low-order bytes of readVal
    61  	// that are still valid.
    62  	readPos int8
    63  }
    64  
    65  // New returns a new Rand that uses random values from src
    66  // to generate other random values.
    67  func New(src Source) *Rand {
    68  	s64, _ := src.(Source64)
    69  	return &Rand{src: src, s64: s64}
    70  }
    71  
    72  // Seed uses the provided seed value to initialize the generator to a deterministic state.
    73  // Seed should not be called concurrently with any other Rand method.
    74  func (r *Rand) Seed(seed int64) {
    75  	if lk, ok := r.src.(*lockedSource); ok {
    76  		lk.seedPos(seed, &r.readPos)
    77  		return
    78  	}
    79  
    80  	r.src.Seed(seed)
    81  	r.readPos = 0
    82  }
    83  
    84  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
    85  func (r *Rand) Int63() int64 { return r.src.Int63() }
    86  
    87  // Uint32 returns a pseudo-random 32-bit value as a uint32.
    88  func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
    89  
    90  // Uint64 returns a pseudo-random 64-bit value as a uint64.
    91  func (r *Rand) Uint64() uint64 {
    92  	if r.s64 != nil {
    93  		return r.s64.Uint64()
    94  	}
    95  	return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
    96  }
    97  
    98  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
    99  func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
   100  
   101  // Int returns a non-negative pseudo-random int.
   102  func (r *Rand) Int() int {
   103  	u := uint(r.Int63())
   104  	return int(u << 1 >> 1) // clear sign bit if int == int32
   105  }
   106  
   107  // Int63n returns, as an int64, a non-negative pseudo-random number in [0,n).
   108  // It panics if n <= 0.
   109  func (r *Rand) Int63n(n int64) int64 {
   110  	if n <= 0 {
   111  		panic("invalid argument to Int63n")
   112  	}
   113  	if n&(n-1) == 0 { // n is power of two, can mask
   114  		return r.Int63() & (n - 1)
   115  	}
   116  	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
   117  	v := r.Int63()
   118  	for v > max {
   119  		v = r.Int63()
   120  	}
   121  	return v % n
   122  }
   123  
   124  // Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
   125  // It panics if n <= 0.
   126  func (r *Rand) Int31n(n int32) int32 {
   127  	if n <= 0 {
   128  		panic("invalid argument to Int31n")
   129  	}
   130  	if n&(n-1) == 0 { // n is power of two, can mask
   131  		return r.Int31() & (n - 1)
   132  	}
   133  	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
   134  	v := r.Int31()
   135  	for v > max {
   136  		v = r.Int31()
   137  	}
   138  	return v % n
   139  }
   140  
   141  // int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
   142  // n must be > 0, but int31n does not check this; the caller must ensure it.
   143  // int31n exists because Int31n is inefficient, but Go 1 compatibility
   144  // requires that the stream of values produced by math/rand remain unchanged.
   145  // int31n can thus only be used internally, by newly introduced APIs.
   146  //
   147  // For implementation details, see:
   148  // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
   149  // https://lemire.me/blog/2016/06/30/fast-random-shuffling
   150  func (r *Rand) int31n(n int32) int32 {
   151  	v := r.Uint32()
   152  	prod := uint64(v) * uint64(n)
   153  	low := uint32(prod)
   154  	if low < uint32(n) {
   155  		thresh := uint32(-n) % uint32(n)
   156  		for low < thresh {
   157  			v = r.Uint32()
   158  			prod = uint64(v) * uint64(n)
   159  			low = uint32(prod)
   160  		}
   161  	}
   162  	return int32(prod >> 32)
   163  }
   164  
   165  // Intn returns, as an int, a non-negative pseudo-random number in [0,n).
   166  // It panics if n <= 0.
   167  func (r *Rand) Intn(n int) int {
   168  	if n <= 0 {
   169  		panic("invalid argument to Intn")
   170  	}
   171  	if n <= 1<<31-1 {
   172  		return int(r.Int31n(int32(n)))
   173  	}
   174  	return int(r.Int63n(int64(n)))
   175  }
   176  
   177  // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
   178  func (r *Rand) Float64() float64 {
   179  	// A clearer, simpler implementation would be:
   180  	//	return float64(r.Int63n(1<<53)) / (1<<53)
   181  	// However, Go 1 shipped with
   182  	//	return float64(r.Int63()) / (1 << 63)
   183  	// and we want to preserve that value stream.
   184  	//
   185  	// There is one bug in the value stream: r.Int63() may be so close
   186  	// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
   187  	// that the result is always less than 1.0.
   188  	//
   189  	// We tried to fix this by mapping 1.0 back to 0.0, but since float64
   190  	// values near 0 are much denser than near 1, mapping 1 to 0 caused
   191  	// a theoretically significant overshoot in the probability of returning 0.
   192  	// Instead of that, if we round up to 1, just try again.
   193  	// Getting 1 only happens 1/2⁵³ of the time, so most clients
   194  	// will not observe it anyway.
   195  again:
   196  	f := float64(r.Int63()) / (1 << 63)
   197  	if f == 1 {
   198  		goto again // resample; this branch is taken O(never)
   199  	}
   200  	return f
   201  }
   202  
   203  // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).
   204  func (r *Rand) Float32() float32 {
   205  	// Same rationale as in Float64: we want to preserve the Go 1 value
   206  	// stream except we want to fix it not to return 1.0
   207  	// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
   208  again:
   209  	f := float32(r.Float64())
   210  	if f == 1 {
   211  		goto again // resample; this branch is taken O(very rarely)
   212  	}
   213  	return f
   214  }
   215  
   216  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [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 [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 [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 [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 [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 [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 [0,n)
   348  // 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