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  	"math/bits"
    22  	_ "unsafe" // for go:linkname
    23  )
    24  
    25  // A Source is a source of uniformly-distributed
    26  // pseudo-random uint64 values in the range [0, 1<<64).
    27  //
    28  // A Source is not safe for concurrent use by multiple goroutines.
    29  type Source interface {
    30  	Uint64() uint64
    31  }
    32  
    33  // A Rand is a source of random numbers.
    34  type Rand struct {
    35  	src Source
    36  }
    37  
    38  // New returns a new Rand that uses random values from src
    39  // to generate other random values.
    40  func New(src Source) *Rand {
    41  	return &Rand{src: src}
    42  }
    43  
    44  // Int64 returns a non-negative pseudo-random 63-bit integer as an int64.
    45  func (r *Rand) Int64() int64 { return int64(r.src.Uint64() &^ (1 << 63)) }
    46  
    47  // Uint32 returns a pseudo-random 32-bit value as a uint32.
    48  func (r *Rand) Uint32() uint32 { return uint32(r.src.Uint64() >> 32) }
    49  
    50  // Uint64 returns a pseudo-random 64-bit value as a uint64.
    51  func (r *Rand) Uint64() uint64 { return r.src.Uint64() }
    52  
    53  // Int32 returns a non-negative pseudo-random 31-bit integer as an int32.
    54  func (r *Rand) Int32() int32 { return int32(r.src.Uint64() >> 33) }
    55  
    56  // Int returns a non-negative pseudo-random int.
    57  func (r *Rand) Int() int { return int(uint(r.src.Uint64()) << 1 >> 1) }
    58  
    59  // Uint returns a pseudo-random uint.
    60  func (r *Rand) Uint() uint { return uint(r.src.Uint64()) }
    61  
    62  // Int64N returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n).
    63  // It panics if n <= 0.
    64  func (r *Rand) Int64N(n int64) int64 {
    65  	if n <= 0 {
    66  		panic("invalid argument to Int64N")
    67  	}
    68  	return int64(r.uint64n(uint64(n)))
    69  }
    70  
    71  // Uint64N returns, as a uint64, a non-negative pseudo-random number in the half-open interval [0,n).
    72  // It panics if n == 0.
    73  func (r *Rand) Uint64N(n uint64) uint64 {
    74  	if n == 0 {
    75  		panic("invalid argument to Uint64N")
    76  	}
    77  	return r.uint64n(n)
    78  }
    79  
    80  // uint64n is the no-bounds-checks version of Uint64N.
    81  func (r *Rand) uint64n(n uint64) uint64 {
    82  	if is32bit && uint64(uint32(n)) == n {
    83  		return uint64(r.uint32n(uint32(n)))
    84  	}
    85  	if n&(n-1) == 0 { // n is power of two, can mask
    86  		return r.Uint64() & (n - 1)
    87  	}
    88  
    89  	// Suppose we have a uint64 x uniform in the range [0,2⁶⁴)
    90  	// and want to reduce it to the range [0,n) preserving exact uniformity.
    91  	// We can simulate a scaling arbitrary precision x * (n/2⁶⁴) by
    92  	// the high bits of a double-width multiply of x*n, meaning (x*n)/2⁶⁴.
    93  	// Since there are 2⁶⁴ possible inputs x and only n possible outputs,
    94  	// the output is necessarily biased if n does not divide 2⁶⁴.
    95  	// In general (x*n)/2⁶⁴ = k for x*n in [k*2⁶⁴,(k+1)*2⁶⁴).
    96  	// There are either floor(2⁶⁴/n) or ceil(2⁶⁴/n) possible products
    97  	// in that range, depending on k.
    98  	// But suppose we reject the sample and try again when
    99  	// x*n is in [k*2⁶⁴, k*2⁶⁴+(2⁶⁴%n)), meaning rejecting fewer than n possible
   100  	// outcomes out of the 2⁶⁴.
   101  	// Now there are exactly floor(2⁶⁴/n) possible ways to produce
   102  	// each output value k, so we've restored uniformity.
   103  	// To get valid uint64 math, 2⁶⁴ % n = (2⁶⁴ - n) % n = -n % n,
   104  	// so the direct implementation of this algorithm would be:
   105  	//
   106  	//	hi, lo := bits.Mul64(r.Uint64(), n)
   107  	//	thresh := -n % n
   108  	//	for lo < thresh {
   109  	//		hi, lo = bits.Mul64(r.Uint64(), n)
   110  	//	}
   111  	//
   112  	// That still leaves an expensive 64-bit division that we would rather avoid.
   113  	// We know that thresh < n, and n is usually much less than 2⁶⁴, so we can
   114  	// avoid the last four lines unless lo < n.
   115  	//
   116  	// See also:
   117  	// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
   118  	// https://lemire.me/blog/2016/06/30/fast-random-shuffling
   119  	hi, lo := bits.Mul64(r.Uint64(), n)
   120  	if lo < n {
   121  		thresh := -n % n
   122  		for lo < thresh {
   123  			hi, lo = bits.Mul64(r.Uint64(), n)
   124  		}
   125  	}
   126  	return hi
   127  }
   128  
   129  // uint32n is an identical computation to uint64n
   130  // but optimized for 32-bit systems.
   131  func (r *Rand) uint32n(n uint32) uint32 {
   132  	if n&(n-1) == 0 { // n is power of two, can mask
   133  		return uint32(r.Uint64()) & (n - 1)
   134  	}
   135  	// On 64-bit systems we still use the uint64 code below because
   136  	// the probability of a random uint64 lo being < a uint32 n is near zero,
   137  	// meaning the unbiasing loop almost never runs.
   138  	// On 32-bit systems, here we need to implement that same logic in 32-bit math,
   139  	// both to preserve the exact output sequence observed on 64-bit machines
   140  	// and to preserve the optimization that the unbiasing loop almost never runs.
   141  	//
   142  	// We want to compute
   143  	// 	hi, lo := bits.Mul64(r.Uint64(), n)
   144  	// In terms of 32-bit halves, this is:
   145  	// 	x1:x0 := r.Uint64()
   146  	// 	0:hi, lo1:lo0 := bits.Mul64(x1:x0, 0:n)
   147  	// Writing out the multiplication in terms of bits.Mul32 allows
   148  	// using direct hardware instructions and avoiding
   149  	// the computations involving these zeros.
   150  	x := r.Uint64()
   151  	lo1a, lo0 := bits.Mul32(uint32(x), n)
   152  	hi, lo1b := bits.Mul32(uint32(x>>32), n)
   153  	lo1, c := bits.Add32(lo1a, lo1b, 0)
   154  	hi += c
   155  	if lo1 == 0 && lo0 < uint32(n) {
   156  		n64 := uint64(n)
   157  		thresh := uint32(-n64 % n64)
   158  		for lo1 == 0 && lo0 < thresh {
   159  			x := r.Uint64()
   160  			lo1a, lo0 = bits.Mul32(uint32(x), n)
   161  			hi, lo1b = bits.Mul32(uint32(x>>32), n)
   162  			lo1, c = bits.Add32(lo1a, lo1b, 0)
   163  			hi += c
   164  		}
   165  	}
   166  	return hi
   167  }
   168  
   169  // Int32N returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
   170  // It panics if n <= 0.
   171  func (r *Rand) Int32N(n int32) int32 {
   172  	if n <= 0 {
   173  		panic("invalid argument to Int32N")
   174  	}
   175  	return int32(r.uint64n(uint64(n)))
   176  }
   177  
   178  // Uint32N returns, as a uint32, a non-negative pseudo-random number in the half-open interval [0,n).
   179  // It panics if n == 0.
   180  func (r *Rand) Uint32N(n uint32) uint32 {
   181  	if n == 0 {
   182  		panic("invalid argument to Uint32N")
   183  	}
   184  	return uint32(r.uint64n(uint64(n)))
   185  }
   186  
   187  const is32bit = ^uint(0)>>32 == 0
   188  
   189  // IntN returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n).
   190  // It panics if n <= 0.
   191  func (r *Rand) IntN(n int) int {
   192  	if n <= 0 {
   193  		panic("invalid argument to IntN")
   194  	}
   195  	return int(r.uint64n(uint64(n)))
   196  }
   197  
   198  // UintN returns, as a uint, a non-negative pseudo-random number in the half-open interval [0,n).
   199  // It panics if n == 0.
   200  func (r *Rand) UintN(n uint) uint {
   201  	if n == 0 {
   202  		panic("invalid argument to UintN")
   203  	}
   204  	return uint(r.uint64n(uint64(n)))
   205  }
   206  
   207  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0).
   208  func (r *Rand) Float64() float64 {
   209  	// There are exactly 1<<53 float64s in [0,1). Use Intn(1<<53) / (1<<53).
   210  	return float64(r.Uint64()<<11>>11) / (1 << 53)
   211  }
   212  
   213  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0).
   214  func (r *Rand) Float32() float32 {
   215  	// There are exactly 1<<24 float32s in [0,1). Use Intn(1<<24) / (1<<24).
   216  	return float32(r.Uint32()<<8>>8) / (1 << 24)
   217  }
   218  
   219  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
   220  // in the half-open interval [0,n).
   221  func (r *Rand) Perm(n int) []int {
   222  	p := make([]int, n)
   223  	for i := range p {
   224  		p[i] = i
   225  	}
   226  	r.Shuffle(len(p), func(i, j int) { p[i], p[j] = p[j], p[i] })
   227  	return p
   228  }
   229  
   230  // Shuffle pseudo-randomizes the order of elements.
   231  // n is the number of elements. Shuffle panics if n < 0.
   232  // swap swaps the elements with indexes i and j.
   233  func (r *Rand) Shuffle(n int, swap func(i, j int)) {
   234  	if n < 0 {
   235  		panic("invalid argument to Shuffle")
   236  	}
   237  
   238  	// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
   239  	// Shuffle really ought not be called with n that doesn't fit in 32 bits.
   240  	// Not only will it take a very long time, but with 2³¹! possible permutations,
   241  	// there's no way that any PRNG can have a big enough internal state to
   242  	// generate even a minuscule percentage of the possible permutations.
   243  	// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
   244  	for i := n - 1; i > 0; i-- {
   245  		j := int(r.uint64n(uint64(i + 1)))
   246  		swap(i, j)
   247  	}
   248  }
   249  
   250  /*
   251   * Top-level convenience functions
   252   */
   253  
   254  // globalRand is the source of random numbers for the top-level
   255  // convenience functions.
   256  var globalRand = &Rand{src: &runtimeSource{}}
   257  
   258  //go:linkname runtime_rand runtime.rand
   259  func runtime_rand() uint64
   260  
   261  // runtimeSource is a Source that uses the runtime fastrand functions.
   262  type runtimeSource struct{}
   263  
   264  func (*runtimeSource) Uint64() uint64 {
   265  	return runtime_rand()
   266  }
   267  
   268  // Int64 returns a non-negative pseudo-random 63-bit integer as an int64
   269  // from the default Source.
   270  func Int64() int64 { return globalRand.Int64() }
   271  
   272  // Uint32 returns a pseudo-random 32-bit value as a uint32
   273  // from the default Source.
   274  func Uint32() uint32 { return globalRand.Uint32() }
   275  
   276  // Uint64N returns, as a uint64, a pseudo-random number in the half-open interval [0,n)
   277  // from the default Source.
   278  // It panics if n <= 0.
   279  func Uint64N(n uint64) uint64 { return globalRand.Uint64N(n) }
   280  
   281  // Uint32N returns, as a uint32, a pseudo-random number in the half-open interval [0,n)
   282  // from the default Source.
   283  // It panics if n <= 0.
   284  func Uint32N(n uint32) uint32 { return globalRand.Uint32N(n) }
   285  
   286  // Uint64 returns a pseudo-random 64-bit value as a uint64
   287  // from the default Source.
   288  func Uint64() uint64 { return globalRand.Uint64() }
   289  
   290  // Int32 returns a non-negative pseudo-random 31-bit integer as an int32
   291  // from the default Source.
   292  func Int32() int32 { return globalRand.Int32() }
   293  
   294  // Int returns a non-negative pseudo-random int from the default Source.
   295  func Int() int { return globalRand.Int() }
   296  
   297  // Uint returns a pseudo-random uint from the default Source.
   298  func Uint() uint { return globalRand.Uint() }
   299  
   300  // Int64N returns, as an int64, a pseudo-random number in the half-open interval [0,n)
   301  // from the default Source.
   302  // It panics if n <= 0.
   303  func Int64N(n int64) int64 { return globalRand.Int64N(n) }
   304  
   305  // Int32N returns, as an int32, a pseudo-random number in the half-open interval [0,n)
   306  // from the default Source.
   307  // It panics if n <= 0.
   308  func Int32N(n int32) int32 { return globalRand.Int32N(n) }
   309  
   310  // IntN returns, as an int, a pseudo-random number in the half-open interval [0,n)
   311  // from the default Source.
   312  // It panics if n <= 0.
   313  func IntN(n int) int { return globalRand.IntN(n) }
   314  
   315  // UintN returns, as a uint, a pseudo-random number in the half-open interval [0,n)
   316  // from the default Source.
   317  // It panics if n <= 0.
   318  func UintN(n uint) uint { return globalRand.UintN(n) }
   319  
   320  // N returns a pseudo-random number in the half-open interval [0,n) from the default Source.
   321  // The type parameter Int can be any integer type.
   322  // It panics if n <= 0.
   323  func N[Int intType](n Int) Int {
   324  	if n <= 0 {
   325  		panic("invalid argument to N")
   326  	}
   327  	return Int(globalRand.uint64n(uint64(n)))
   328  }
   329  
   330  type intType interface {
   331  	~int | ~int8 | ~int16 | ~int32 | ~int64 |
   332  		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
   333  }
   334  
   335  // Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0)
   336  // from the default Source.
   337  func Float64() float64 { return globalRand.Float64() }
   338  
   339  // Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0)
   340  // from the default Source.
   341  func Float32() float32 { return globalRand.Float32() }
   342  
   343  // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
   344  // in the half-open interval [0,n) from the default Source.
   345  func Perm(n int) []int { return globalRand.Perm(n) }
   346  
   347  // Shuffle pseudo-randomizes the order of elements using the default Source.
   348  // n is the number of elements. Shuffle panics if n < 0.
   349  // swap swaps the elements with indexes i and j.
   350  func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }
   351  
   352  // NormFloat64 returns a normally distributed float64 in the range
   353  // [-math.MaxFloat64, +math.MaxFloat64] with
   354  // standard normal distribution (mean = 0, stddev = 1)
   355  // from the default Source.
   356  // To produce a different normal distribution, callers can
   357  // adjust the output using:
   358  //
   359  //	sample = NormFloat64() * desiredStdDev + desiredMean
   360  func NormFloat64() float64 { return globalRand.NormFloat64() }
   361  
   362  // ExpFloat64 returns an exponentially distributed float64 in the range
   363  // (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
   364  // (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
   365  // To produce a distribution with a different rate parameter,
   366  // callers can adjust the output using:
   367  //
   368  //	sample = ExpFloat64() / desiredRateParameter
   369  func ExpFloat64() float64 { return globalRand.ExpFloat64() }
   370
View as plain text