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