...
Run Format

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.
     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.
    12	//
    13	// For random numbers suitable for security-sensitive work, see the crypto/rand
    14	// package.
    15	package rand
    16	
    17	import "sync"
    18	
    19	// A Source represents a source of uniformly-distributed
    20	// pseudo-random int64 values in the range [0, 1<<63).
    21	type Source interface {
    22		Int63() int64
    23		Seed(seed int64)
    24	}
    25	
    26	// A Source64 is a Source that can also generate
    27	// uniformly-distributed pseudo-random uint64 values in
    28	// the range [0, 1<<64) directly.
    29	// If a Rand r's underlying Source s implements Source64,
    30	// then r.Uint64 returns the result of one call to s.Uint64
    31	// instead of making two calls to s.Int63.
    32	type Source64 interface {
    33		Source
    34		Uint64() uint64
    35	}
    36	
    37	// NewSource returns a new pseudo-random Source seeded with the given value.
    38	// Unlike the default Source used by top-level functions, this source is not
    39	// safe for concurrent use by multiple goroutines.
    40	func NewSource(seed int64) Source {
    41		var rng rngSource
    42		rng.Seed(seed)
    43		return &rng
    44	}
    45	
    46	// A Rand is a source of random numbers.
    47	type Rand struct {
    48		src Source
    49		s64 Source64 // non-nil if src is source64
    50	
    51		// readVal contains remainder of 63-bit integer used for bytes
    52		// generation during most recent Read call.
    53		// It is saved so next Read call can start where the previous
    54		// one finished.
    55		readVal int64
    56		// readPos indicates the number of low-order bytes of readVal
    57		// that are still valid.
    58		readPos int8
    59	}
    60	
    61	// New returns a new Rand that uses random values from src
    62	// to generate other random values.
    63	func New(src Source) *Rand {
    64		s64, _ := src.(Source64)
    65		return &Rand{src: src, s64: s64}
    66	}
    67	
    68	// Seed uses the provided seed value to initialize the generator to a deterministic state.
    69	// Seed should not be called concurrently with any other Rand method.
    70	func (r *Rand) Seed(seed int64) {
    71		if lk, ok := r.src.(*lockedSource); ok {
    72			lk.seedPos(seed, &r.readPos)
    73			return
    74		}
    75	
    76		r.src.Seed(seed)
    77		r.readPos = 0
    78	}
    79	
    80	// Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
    81	func (r *Rand) Int63() int64 { return r.src.Int63() }
    82	
    83	// Uint32 returns a pseudo-random 32-bit value as a uint32.
    84	func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) }
    85	
    86	// Uint64 returns a pseudo-random 64-bit value as a uint64.
    87	func (r *Rand) Uint64() uint64 {
    88		if r.s64 != nil {
    89			return r.s64.Uint64()
    90		}
    91		return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
    92	}
    93	
    94	// Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
    95	func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
    96	
    97	// Int returns a non-negative pseudo-random int.
    98	func (r *Rand) Int() int {
    99		u := uint(r.Int63())
   100		return int(u << 1 >> 1) // clear sign bit if int == int32
   101	}
   102	
   103	// Int63n returns, as an int64, a non-negative pseudo-random number in [0,n).
   104	// It panics if n <= 0.
   105	func (r *Rand) Int63n(n int64) int64 {
   106		if n <= 0 {
   107			panic("invalid argument to Int63n")
   108		}
   109		if n&(n-1) == 0 { // n is power of two, can mask
   110			return r.Int63() & (n - 1)
   111		}
   112		max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
   113		v := r.Int63()
   114		for v > max {
   115			v = r.Int63()
   116		}
   117		return v % n
   118	}
   119	
   120	// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
   121	// It panics if n <= 0.
   122	func (r *Rand) Int31n(n int32) int32 {
   123		if n <= 0 {
   124			panic("invalid argument to Int31n")
   125		}
   126		if n&(n-1) == 0 { // n is power of two, can mask
   127			return r.Int31() & (n - 1)
   128		}
   129		max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
   130		v := r.Int31()
   131		for v > max {
   132			v = r.Int31()
   133		}
   134		return v % n
   135	}
   136	
   137	// Intn returns, as an int, a non-negative pseudo-random number in [0,n).
   138	// It panics if n <= 0.
   139	func (r *Rand) Intn(n int) int {
   140		if n <= 0 {
   141			panic("invalid argument to Intn")
   142		}
   143		if n <= 1<<31-1 {
   144			return int(r.Int31n(int32(n)))
   145		}
   146		return int(r.Int63n(int64(n)))
   147	}
   148	
   149	// Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
   150	func (r *Rand) Float64() float64 {
   151		// A clearer, simpler implementation would be:
   152		//	return float64(r.Int63n(1<<53)) / (1<<53)
   153		// However, Go 1 shipped with
   154		//	return float64(r.Int63()) / (1 << 63)
   155		// and we want to preserve that value stream.
   156		//
   157		// There is one bug in the value stream: r.Int63() may be so close
   158		// to 1<<63 that the division rounds up to 1.0, and we've guaranteed
   159		// that the result is always less than 1.0.
   160		//
   161		// We tried to fix this by mapping 1.0 back to 0.0, but since float64
   162		// values near 0 are much denser than near 1, mapping 1 to 0 caused
   163		// a theoretically significant overshoot in the probability of returning 0.
   164		// Instead of that, if we round up to 1, just try again.
   165		// Getting 1 only happens 1/2⁵³ of the time, so most clients
   166		// will not observe it anyway.
   167	again:
   168		f := float64(r.Int63()) / (1 << 63)
   169		if f == 1 {
   170			goto again // resample; this branch is taken O(never)
   171		}
   172		return f
   173	}
   174	
   175	// Float32 returns, as a float32, a pseudo-random number in [0.0,1.0).
   176	func (r *Rand) Float32() float32 {
   177		// Same rationale as in Float64: we want to preserve the Go 1 value
   178		// stream except we want to fix it not to return 1.0
   179		// This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64).
   180	again:
   181		f := float32(r.Float64())
   182		if f == 1 {
   183			goto again // resample; this branch is taken O(very rarely)
   184		}
   185		return f
   186	}
   187	
   188	// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
   189	func (r *Rand) Perm(n int) []int {
   190		m := make([]int, n)
   191		// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
   192		// A change to remove this useless iteration is to assign 1 to i in the init
   193		// statement. But Perm also effects r. Making this change will affect
   194		// the final state of r. So this change can't be made for compatibility
   195		// reasons for Go 1.
   196		for i := 0; i < n; i++ {
   197			j := r.Intn(i + 1)
   198			m[i] = m[j]
   199			m[j] = i
   200		}
   201		return m
   202	}
   203	
   204	// Read generates len(p) random bytes and writes them into p. It
   205	// always returns len(p) and a nil error.
   206	// Read should not be called concurrently with any other Rand method.
   207	func (r *Rand) Read(p []byte) (n int, err error) {
   208		if lk, ok := r.src.(*lockedSource); ok {
   209			return lk.read(p, &r.readVal, &r.readPos)
   210		}
   211		return read(p, r.Int63, &r.readVal, &r.readPos)
   212	}
   213	
   214	func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, err error) {
   215		pos := *readPos
   216		val := *readVal
   217		for n = 0; n < len(p); n++ {
   218			if pos == 0 {
   219				val = int63()
   220				pos = 7
   221			}
   222			p[n] = byte(val)
   223			val >>= 8
   224			pos--
   225		}
   226		*readPos = pos
   227		*readVal = val
   228		return
   229	}
   230	
   231	/*
   232	 * Top-level convenience functions
   233	 */
   234	
   235	var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})
   236	
   237	// Seed uses the provided seed value to initialize the default Source to a
   238	// deterministic state. If Seed is not called, the generator behaves as
   239	// if seeded by Seed(1). Seed values that have the same remainder when
   240	// divided by 2^31-1 generate the same pseudo-random sequence.
   241	// Seed, unlike the Rand.Seed method, is safe for concurrent use.
   242	func Seed(seed int64) { globalRand.Seed(seed) }
   243	
   244	// Int63 returns a non-negative pseudo-random 63-bit integer as an int64
   245	// from the default Source.
   246	func Int63() int64 { return globalRand.Int63() }
   247	
   248	// Uint32 returns a pseudo-random 32-bit value as a uint32
   249	// from the default Source.
   250	func Uint32() uint32 { return globalRand.Uint32() }
   251	
   252	// Uint64 returns a pseudo-random 64-bit value as a uint64
   253	// from the default Source.
   254	func Uint64() uint64 { return globalRand.Uint64() }
   255	
   256	// Int31 returns a non-negative pseudo-random 31-bit integer as an int32
   257	// from the default Source.
   258	func Int31() int32 { return globalRand.Int31() }
   259	
   260	// Int returns a non-negative pseudo-random int from the default Source.
   261	func Int() int { return globalRand.Int() }
   262	
   263	// Int63n returns, as an int64, a non-negative pseudo-random number in [0,n)
   264	// from the default Source.
   265	// It panics if n <= 0.
   266	func Int63n(n int64) int64 { return globalRand.Int63n(n) }
   267	
   268	// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n)
   269	// from the default Source.
   270	// It panics if n <= 0.
   271	func Int31n(n int32) int32 { return globalRand.Int31n(n) }
   272	
   273	// Intn returns, as an int, a non-negative pseudo-random number in [0,n)
   274	// from the default Source.
   275	// It panics if n <= 0.
   276	func Intn(n int) int { return globalRand.Intn(n) }
   277	
   278	// Float64 returns, as a float64, a pseudo-random number in [0.0,1.0)
   279	// from the default Source.
   280	func Float64() float64 { return globalRand.Float64() }
   281	
   282	// Float32 returns, as a float32, a pseudo-random number in [0.0,1.0)
   283	// from the default Source.
   284	func Float32() float32 { return globalRand.Float32() }
   285	
   286	// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n)
   287	// from the default Source.
   288	func Perm(n int) []int { return globalRand.Perm(n) }
   289	
   290	// Read generates len(p) random bytes from the default Source and
   291	// writes them into p. It always returns len(p) and a nil error.
   292	// Read, unlike the Rand.Read method, is safe for concurrent use.
   293	func Read(p []byte) (n int, err error) { return globalRand.Read(p) }
   294	
   295	// NormFloat64 returns a normally distributed float64 in the range
   296	// [-math.MaxFloat64, +math.MaxFloat64] with
   297	// standard normal distribution (mean = 0, stddev = 1)
   298	// from the default Source.
   299	// To produce a different normal distribution, callers can
   300	// adjust the output using:
   301	//
   302	//  sample = NormFloat64() * desiredStdDev + desiredMean
   303	//
   304	func NormFloat64() float64 { return globalRand.NormFloat64() }
   305	
   306	// ExpFloat64 returns an exponentially distributed float64 in the range
   307	// (0, +math.MaxFloat64] with an exponential distribution whose rate parameter
   308	// (lambda) is 1 and whose mean is 1/lambda (1) from the default Source.
   309	// To produce a distribution with a different rate parameter,
   310	// callers can adjust the output using:
   311	//
   312	//  sample = ExpFloat64() / desiredRateParameter
   313	//
   314	func ExpFloat64() float64 { return globalRand.ExpFloat64() }
   315	
   316	type lockedSource struct {
   317		lk  sync.Mutex
   318		src Source64
   319	}
   320	
   321	func (r *lockedSource) Int63() (n int64) {
   322		r.lk.Lock()
   323		n = r.src.Int63()
   324		r.lk.Unlock()
   325		return
   326	}
   327	
   328	func (r *lockedSource) Uint64() (n uint64) {
   329		r.lk.Lock()
   330		n = r.src.Uint64()
   331		r.lk.Unlock()
   332		return
   333	}
   334	
   335	func (r *lockedSource) Seed(seed int64) {
   336		r.lk.Lock()
   337		r.src.Seed(seed)
   338		r.lk.Unlock()
   339	}
   340	
   341	// seedPos implements Seed for a lockedSource without a race condiiton.
   342	func (r *lockedSource) seedPos(seed int64, readPos *int8) {
   343		r.lk.Lock()
   344		r.src.Seed(seed)
   345		*readPos = 0
   346		r.lk.Unlock()
   347	}
   348	
   349	// read implements Read for a lockedSource without a race condition.
   350	func (r *lockedSource) read(p []byte, readVal *int64, readPos *int8) (n int, err error) {
   351		r.lk.Lock()
   352		n, err = read(p, r.src.Int63, readVal, readPos)
   353		r.lk.Unlock()
   354		return
   355	}
   356	

View as plain text