Source file src/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 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  	"internal/godebug"
    22  	"sync"
    23  	"sync/atomic"
    24  	_ "unsafe" // for go:linkname
    25  )
    26  
    27  // A Source represents a source of uniformly-distributed
    28  // pseudo-random int64 values in the range [0, 1<<63).
    29  //
    30  // A Source is not safe for concurrent use by multiple goroutines.
    31  type Source interface {
    32  	Int63() int64
    33  	Seed(seed int64)
    34  }
    35  
    36  // A Source64 is a [Source] that can also generate
    37  // uniformly-distributed pseudo-random uint64 values in
    38  // the range [0, 1<<64) directly.
    39  // If a [Rand] r's underlying [Source] s implements Source64,
    40  // then r.Uint64 returns the result of one call to s.Uint64
    41  // instead of making two calls to s.Int63.
    42  type Source64 interface {
    43  	Source
    44  	Uint64() uint64
    45  }
    46  
    47  // NewSource returns a new pseudo-random [Source] seeded with the given value.
    48  // Unlike the default [Source] used by top-level functions, this source is not
    49  // safe for concurrent use by multiple goroutines.
    50  // The returned [Source] implements [Source64].
    51  func NewSource(seed int64) Source {
    52  	return newSource(seed)
    53  }
    54  
    55  func newSource(seed int64) *rngSource {
    56  	var rng rngSource
    57  	rng.Seed(seed)
    58  	return &rng
    59  }
    60  
    61  // A Rand is a source of random numbers.
    62  type Rand struct {
    63  	src Source
    64  	s64 Source64 // non-nil if src is source64
    65  
    66  	// readVal contains remainder of 63-bit integer used for bytes
    67  	// generation during most recent Read call.
    68  	// It is saved so next Read call can start where the previous
    69  	// one finished.
    70  	readVal int64
    71  	// readPos indicates the number of low-order bytes of readVal
    72  	// that are still valid.
    73  	readPos int8
    74  }
    75  
    76  // New returns a new [Rand] that uses random values from src
    77  // to generate other random values.
    78  func New(src Source) *Rand {
    79  	s64, _ := src.(Source64)
    80  	return &Rand{src: src, s64: s64}
    81  }
    82  
    83  // Seed uses the provided seed value to initialize the generator to a deterministic state.
    84  // Seed should not be called concurrently with any other [Rand] method.
    85  func (r *Rand) Seed(seed int64) {
    86  	if lk, ok := r.src.(*lockedSource); ok {
    87  		lk.seedPos(seed, &r.readPos)
    88  		return
    89  	}
    90  
    91  	r.src.Seed(seed)
    92  	r.readPos = 0
    93  }
    94  
    95  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
    96  func (r *Rand) Int63() int64 { return r.src.Int63() }
    97  
    98  // Uint32 returns a pseudo-random 32-bit value as a uint32.
    99  func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
   100  
   101  // Uint64 returns a pseudo-random 64-bit value as a uint64.
   102  func (r *Rand) Uint64() uint64 {
   103  	if r.s64 != nil {
   104  		return r.s64.Uint64()
   105  	}
   106  	return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
   107  }
   108  
   109  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
   110  func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
   111  
   112  // Int returns a non-negative pseudo-random int.
   113  func (r *Rand) Int() int {
   114  	u := uint(r.Int63())
   115  	return int(u << 1 >> 1) // clear sign bit if int == int32
   116  }
   117  
   118  // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
   119  // It panics if n <= 0.
   120  func (r *Rand) Int63n(n int64) int64 {
   121  	if n <= 0 {
   122  		panic("invalid argument to Int63n")
   123  	}
   124  	if n&(n-1) == 0 { // n is power of two, can mask
   125  		return r.Int63() & (n - 1)
   126  	}
   127  	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
   128  	v := r.Int63()
   129  	for v > max {
   130  		v = r.Int63()
   131  	}
   132  	return v % n
   133  }
   134  
   135  // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
   136  // It panics if n <= 0.
   137  func (r *Rand) Int31n(n int32) int32 {
   138  	if n <= 0 {
   139  		panic("invalid argument to Int31n")
   140  	}
   141  	if n&(n-1) == 0 { // n is power of two, can mask
   142  		return r.Int31() & (n - 1)
   143  	}
   144  	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
   145  	v := r.Int31()
   146  	for v > max {
   147  		v = r.Int31()
   148  	}
   149  	return v % n
   150  }
   151  
   152  // int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
   153  // n must be > 0, but int31n does not check this; the caller must ensure it.
   154  // int31n exists because Int31n is inefficient, but Go 1 compatibility
   155  // requires that the stream of values produced by math/rand remain unchanged.
   156  // int31n can thus only be used internally, by newly introduced APIs.
   157  //
   158  // For implementation details, see:
   159  // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
   160  // https://lemire.me/blog/2016/06/30/fast-random-shuffling
   161  func (r *Rand) int31n(n int32) int32 {
   162  	v := r.Uint32()
   163  	prod := uint64(v) * uint64(n)
   164  	low := uint32(prod)
   165  	if low < uint32(n) {
   166  		thresh := uint32(-n) % uint32(n)
   167  		for low < thresh {
   168  			v = r.Uint32()
   169  			prod = uint64(v) * uint64(n)
   170  			low = uint32(prod)
   171  		}
   172  	}
   173  	return int32(prod >> 32)
   174  }
   175  
   176  // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
   177  // It panics if n <= 0.
   178  func (r *Rand) Intn(n int) int {
   179  	if n <= 0 {
   180  		panic("invalid argument to Intn")
   181  	}
   182  	if n <= 1<<31-1 {
   183  		return int(r.Int31n(int32(n)))
   184  	}
   185  	return int(r.Int63n(int64(n)))
   186  }
   187  
   188  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
   189  func (r *Rand) Float64() float64 {
   190  	// A clearer, simpler implementation would be:
   191  	//	return float64(r.Int63n(1<<53)) / (1<<53)
   192  	// However, Go 1 shipped with
   193  	//	return float64(r.Int63()) / (1 << 63)
   194  	// and we want to preserve that value stream.
   195  	//
   196  	// There is one bug in the value stream: r.Int63() may be so close
   197  	// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
   198  	// that the result is always less than 1.0.
   199  	//
   200  	// We tried to fix this by mapping 1.0 back to 0.0, but since float64
   201  	// values near 0 are much denser than near 1, mapping 1 to 0 caused
   202  	// a theoretically significant overshoot in the probability of returning 0.
   203  	// Instead of that, if we round up to 1, just try again.
   204  	// Getting 1 only happens 1/2⁵³ of the time, so most clients
   205  	// will not observe it anyway.
   206  again:
   207  	f := float64(r.Int63()) / (1 << 63)
   208  	if f == 1 {
   209  		goto again // resample; this branch is taken O(never)
   210  	}
   211  	return f
   212  }
   213  
   214  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
   215  func (r *Rand) Float32() float32 {
   216  	// Same rationale as in Float64: we want to preserve the Go 1 value
   217  	// stream except we want to fix it not to return 1.0
   218  	// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
   219  again:
   220  	f := float32(r.Float64())
   221  	if f == 1 {
   222  		goto again // resample; this branch is taken O(very rarely)
   223  	}
   224  	return f
   225  }
   226  
   227  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
   228  // in the half-open interval [0,n).
   229  func (r *Rand) Perm(n int) []int {
   230  	m := make([]int, n)
   231  	// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
   232  	// A change to remove this useless iteration is to assign 1 to i in the init
   233  	// statement. But Perm also effects r. Making this change will affect
   234  	// the final state of r. So this change can't be made for compatibility
   235  	// reasons for Go 1.
   236  	for i := 0; i < n; i++ {
   237  		j := r.Intn(i + 1)
   238  		m[i] = m[j]
   239  		m[j] = i
   240  	}
   241  	return m
   242  }
   243  
   244  // Shuffle pseudo-randomizes the order of elements.
   245  // n is the number of elements. Shuffle panics if n < 0.
   246  // swap swaps the elements with indexes i and j.
   247  func (r *Rand) Shuffle(n int, swap func(i, j int)) {
   248  	if n < 0 {
   249  		panic("invalid argument to Shuffle")
   250  	}
   251  
   252  	// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
   253  	// Shuffle really ought not be called with n that doesn't fit in 32 bits.
   254  	// Not only will it take a very long time, but with 2³¹! possible permutations,
   255  	// there's no way that any PRNG can have a big enough internal state to
   256  	// generate even a minuscule percentage of the possible permutations.
   257  	// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
   258  	i := n - 1
   259  	for ; i > 1<<31-1-1; i-- {
   260  		j := int(r.Int63n(int64(i + 1)))
   261  		swap(i, j)
   262  	}
   263  	for ; i > 0; i-- {
   264  		j := int(r.int31n(int32(i + 1)))
   265  		swap(i, j)
   266  	}
   267  }
   268  
   269  // Read generates len(p) random bytes and writes them into p. It
   270  // always returns len(p) and a nil error.
   271  // Read should not be called concurrently with any other Rand method.
   272  func (r *Rand) Read(p []byte) (n int, err error) {
   273  	switch src := r.src.(type) {
   274  	case *lockedSource:
   275  		return src.read(p, &r.readVal, &r.readPos)
   276  	case *runtimeSource:
   277  		return src.read(p, &r.readVal, &r.readPos)
   278  	}
   279  	return read(p, r.src, &r.readVal, &r.readPos)
   280  }
   281  
   282  func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
   283  	pos := *readPos
   284  	val := *readVal
   285  	rng, _ := src.(*rngSource)
   286  	for n = 0; n < len(p); n++ {
   287  		if pos == 0 {
   288  			if rng != nil {
   289  				val = rng.Int63()
   290  			} else {
   291  				val = src.Int63()
   292  			}
   293  			pos = 7
   294  		}
   295  		p[n] = byte(val)
   296  		val >>= 8
   297  		pos--
   298  	}
   299  	*readPos = pos
   300  	*readVal = val
   301  	return
   302  }
   303  
   304  /*
   305   * Top-level convenience functions
   306   */
   307  
   308  // globalRandGenerator is the source of random numbers for the top-level
   309  // convenience functions. When possible it uses the runtime fastrand64
   310  // function to avoid locking. This is not possible if the user called Seed,
   311  // either explicitly or implicitly via GODEBUG=randautoseed=0.
   312  var globalRandGenerator atomic.Pointer[Rand]
   313  
   314  var randautoseed = godebug.New("randautoseed")
   315  
   316  // globalRand returns the generator to use for the top-level convenience
   317  // functions.
   318  func globalRand() *Rand {
   319  	if r := globalRandGenerator.Load(); r != nil {
   320  		return r
   321  	}
   322  
   323  	// This is the first call. Initialize based on GODEBUG.
   324  	var r *Rand
   325  	if randautoseed.Value() == "0" {
   326  		randautoseed.IncNonDefault()
   327  		r = New(new(lockedSource))
   328  		r.Seed(1)
   329  	} else {
   330  		r = &Rand{
   331  			src: &runtimeSource{},
   332  			s64: &runtimeSource{},
   333  		}
   334  	}
   335  
   336  	if !globalRandGenerator.CompareAndSwap(nil, r) {
   337  		// Two different goroutines called some top-level
   338  		// function at the same time. While the results in
   339  		// that case are unpredictable, if we just use r here,
   340  		// and we are using a seed, we will most likely return
   341  		// the same value for both calls. That doesn't seem ideal.
   342  		// Just use the first one to get in.
   343  		return globalRandGenerator.Load()
   344  	}
   345  
   346  	return r
   347  }
   348  
   349  //go:linkname runtime_rand runtime.rand
   350  func runtime_rand() uint64
   351  
   352  // runtimeSource is an implementation of Source64 that uses the runtime
   353  // fastrand functions.
   354  type runtimeSource struct {
   355  	// The mutex is used to avoid race conditions in Read.
   356  	mu sync.Mutex
   357  }
   358  
   359  func (*runtimeSource) Int63() int64 {
   360  	return int64(runtime_rand() & rngMask)
   361  }
   362  
   363  func (*runtimeSource) Seed(int64) {
   364  	panic("internal error: call to runtimeSource.Seed")
   365  }
   366  
   367  func (*runtimeSource) Uint64() uint64 {
   368  	return runtime_rand()
   369  }
   370  
   371  func (fs *runtimeSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
   372  	fs.mu.Lock()
   373  	n, err = read(p, fs, readVal, readPos)
   374  	fs.mu.Unlock()
   375  	return
   376  }
   377  
   378  // Seed uses the provided seed value to initialize the default Source to a
   379  // deterministic state. Seed values that have the same remainder when
   380  // divided by 2³¹-1 generate the same pseudo-random sequence.
   381  // Seed, unlike the [Rand.Seed] method, is safe for concurrent use.
   382  //
   383  // If Seed is not called, the generator is seeded randomly at program startup.
   384  //
   385  // Prior to Go 1.20, the generator was seeded like Seed(1) at program startup.
   386  // To force the old behavior, call Seed(1) at program startup.
   387  // Alternately, set GODEBUG=randautoseed=0 in the environment
   388  // before making any calls to functions in this package.
   389  //
   390  // Deprecated: As of Go 1.20 there is no reason to call Seed with
   391  // a random value. Programs that call Seed with a known value to get
   392  // a specific sequence of results should use New(NewSource(seed)) to
   393  // obtain a local random generator.
   394  func Seed(seed int64) {
   395  	orig := globalRandGenerator.Load()
   396  
   397  	// If we are already using a lockedSource, we can just re-seed it.
   398  	if orig != nil {
   399  		if _, ok := orig.src.(*lockedSource); ok {
   400  			orig.Seed(seed)
   401  			return
   402  		}
   403  	}
   404  
   405  	// Otherwise either
   406  	// 1) orig == nil, which is the normal case when Seed is the first
   407  	// top-level function to be called, or
   408  	// 2) orig is already a runtimeSource, in which case we need to change
   409  	// to a lockedSource.
   410  	// Either way we do the same thing.
   411  
   412  	r := New(new(lockedSource))
   413  	r.Seed(seed)
   414  
   415  	if !globalRandGenerator.CompareAndSwap(orig, r) {
   416  		// Something changed underfoot. Retry to be safe.
   417  		Seed(seed)
   418  	}
   419  }
   420  
   421  // Int63 returns a non-negative pseudo-random 63-bit integer as an int64
   422  // from the default [Source].
   423  func Int63() int64 { return globalRand().Int63() }
   424  
   425  // Uint32 returns a pseudo-random 32-bit value as a uint32
   426  // from the default [Source].
   427  func Uint32() uint32 { return globalRand().Uint32() }
   428  
   429  // Uint64 returns a pseudo-random 64-bit value as a uint64
   430  // from the default [Source].
   431  func Uint64() uint64 { return globalRand().Uint64() }
   432  
   433  // Int31 returns a non-negative pseudo-random 31-bit integer as an int32
   434  // from the default [Source].
   435  func Int31() int32 { return globalRand().Int31() }
   436  
   437  // Int returns a non-negative pseudo-random int from the default [Source].
   438  func Int() int { return globalRand().Int() }
   439  
   440  // Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n)
   441  // from the default [Source].
   442  // It panics if n <= 0.
   443  func Int63n(n int64) int64 { return globalRand().Int63n(n) }
   444  
   445  // Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n)
   446  // from the default [Source].
   447  // It panics if n <= 0.
   448  func Int31n(n int32) int32 { return globalRand().Int31n(n) }
   449  
   450  // Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n)
   451  // from the default [Source].
   452  // It panics if n <= 0.
   453  func Intn(n int) int { return globalRand().Intn(n) }
   454  
   455  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
   456  // from the default [Source].
   457  func Float64() float64 { return globalRand().Float64() }
   458  
   459  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
   460  // from the default [Source].
   461  func Float32() float32 { return globalRand().Float32() }
   462  
   463  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
   464  // in the half-open interval [0,n) from the default [Source].
   465  func Perm(n int) []int { return globalRand().Perm(n) }
   466  
   467  // Shuffle pseudo-randomizes the order of elements using the default [Source].
   468  // n is the number of elements. Shuffle panics if n < 0.
   469  // swap swaps the elements with indexes i and j.
   470  func Shuffle(n int, swap func(i, j int)) { globalRand().Shuffle(n, swap) }
   471  
   472  // Read generates len(p) random bytes from the default [Source] and
   473  // writes them into p. It always returns len(p) and a nil error.
   474  // Read, unlike the [Rand.Read] method, is safe for concurrent use.
   475  //
   476  // Deprecated: For almost all use cases, [crypto/rand.Read] is more appropriate.
   477  // If a deterministic source is required, use [math/rand/v2.ChaCha8.Read].
   478  func Read(p []byte) (n int, err error) { return globalRand().Read(p) }
   479  
   480  // NormFloat64 returns a normally distributed float64 in the range
   481  // [-[math.MaxFloat64], +[math.MaxFloat64]] with
   482  // standard normal distribution (mean = 0, stddev = 1)
   483  // from the default [Source].
   484  // To produce a different normal distribution, callers can
   485  // adjust the output using:
   486  //
   487  //	sample = NormFloat64() * desiredStdDev + desiredMean
   488  func NormFloat64() float64 { return globalRand().NormFloat64() }
   489  
   490  // ExpFloat64 returns an exponentially distributed float64 in the range
   491  // (0, +[math.MaxFloat64]] with an exponential distribution whose rate parameter
   492  // (lambda) is 1 and whose mean is 1/lambda (1) from the default [Source].
   493  // To produce a distribution with a different rate parameter,
   494  // callers can adjust the output using:
   495  //
   496  //	sample = ExpFloat64() / desiredRateParameter
   497  func ExpFloat64() float64 { return globalRand().ExpFloat64() }
   498  
   499  type lockedSource struct {
   500  	lk sync.Mutex
   501  	s  *rngSource
   502  }
   503  
   504  func (r *lockedSource) Int63() (n int64) {
   505  	r.lk.Lock()
   506  	n = r.s.Int63()
   507  	r.lk.Unlock()
   508  	return
   509  }
   510  
   511  func (r *lockedSource) Uint64() (n uint64) {
   512  	r.lk.Lock()
   513  	n = r.s.Uint64()
   514  	r.lk.Unlock()
   515  	return
   516  }
   517  
   518  func (r *lockedSource) Seed(seed int64) {
   519  	r.lk.Lock()
   520  	r.seed(seed)
   521  	r.lk.Unlock()
   522  }
   523  
   524  // seedPos implements Seed for a lockedSource without a race condition.
   525  func (r *lockedSource) seedPos(seed int64, readPos *int8) {
   526  	r.lk.Lock()
   527  	r.seed(seed)
   528  	*readPos = 0
   529  	r.lk.Unlock()
   530  }
   531  
   532  // seed seeds the underlying source.
   533  // The caller must have locked r.lk.
   534  func (r *lockedSource) seed(seed int64) {
   535  	if r.s == nil {
   536  		r.s = newSource(seed)
   537  	} else {
   538  		r.s.Seed(seed)
   539  	}
   540  }
   541  
   542  // read implements Read for a lockedSource without a race condition.
   543  func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
   544  	r.lk.Lock()
   545  	n, err = read(p, r.s, readVal, readPos)
   546  	r.lk.Unlock()
   547  	return
   548  }
   549  

View as plain text