Source file src/golang.org/x/exp/rand/rand_test.go

Documentation: golang.org/x/exp/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
     6  
     7  import (
     8  	"bytes"
     9  	"errors"
    10  	"fmt"
    11  	"io"
    12  	"math"
    13  	"os"
    14  	"runtime"
    15  	"testing"
    16  	"testing/iotest"
    17  	"time"
    18  )
    19  
    20  const (
    21  	numTestSamples = 10000
    22  )
    23  
    24  type statsResults struct {
    25  	mean        float64
    26  	stddev      float64
    27  	closeEnough float64
    28  	maxError    float64
    29  }
    30  
    31  func max(a, b float64) float64 {
    32  	if a > b {
    33  		return a
    34  	}
    35  	return b
    36  }
    37  
    38  func nearEqual(a, b, closeEnough, maxError float64) bool {
    39  	absDiff := math.Abs(a - b)
    40  	if absDiff < closeEnough { // Necessary when one value is zero and one value is close to zero.
    41  		return true
    42  	}
    43  	return absDiff/max(math.Abs(a), math.Abs(b)) < maxError
    44  }
    45  
    46  var testSeeds = []uint64{1, 1754801282, 1698661970, 1550503961}
    47  
    48  // checkSimilarDistribution returns success if the mean and stddev of the
    49  // two statsResults are similar.
    50  func (this *statsResults) checkSimilarDistribution(expected *statsResults) error {
    51  	if !nearEqual(this.mean, expected.mean, expected.closeEnough, expected.maxError) {
    52  		s := fmt.Sprintf("mean %v != %v (allowed error %v, %v)", this.mean, expected.mean, expected.closeEnough, expected.maxError)
    53  		fmt.Println(s)
    54  		return errors.New(s)
    55  	}
    56  	if !nearEqual(this.stddev, expected.stddev, 0, expected.maxError) {
    57  		s := fmt.Sprintf("stddev %v != %v (allowed error %v, %v)", this.stddev, expected.stddev, expected.closeEnough, expected.maxError)
    58  		fmt.Println(s)
    59  		return errors.New(s)
    60  	}
    61  	return nil
    62  }
    63  
    64  func getStatsResults(samples []float64) *statsResults {
    65  	res := new(statsResults)
    66  	var sum, squaresum float64
    67  	for _, s := range samples {
    68  		sum += s
    69  		squaresum += s * s
    70  	}
    71  	res.mean = sum / float64(len(samples))
    72  	res.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean)
    73  	return res
    74  }
    75  
    76  func checkSampleDistribution(t *testing.T, samples []float64, expected *statsResults) {
    77  	t.Helper()
    78  	actual := getStatsResults(samples)
    79  	err := actual.checkSimilarDistribution(expected)
    80  	if err != nil {
    81  		t.Errorf(err.Error())
    82  	}
    83  }
    84  
    85  func checkSampleSliceDistributions(t *testing.T, samples []float64, nslices int, expected *statsResults) {
    86  	t.Helper()
    87  	chunk := len(samples) / nslices
    88  	for i := 0; i < nslices; i++ {
    89  		low := i * chunk
    90  		var high int
    91  		if i == nslices-1 {
    92  			high = len(samples) - 1
    93  		} else {
    94  			high = (i + 1) * chunk
    95  		}
    96  		checkSampleDistribution(t, samples[low:high], expected)
    97  	}
    98  }
    99  
   100  //
   101  // Normal distribution tests
   102  //
   103  
   104  func generateNormalSamples(nsamples int, mean, stddev float64, seed uint64) []float64 {
   105  	r := New(NewSource(seed))
   106  	samples := make([]float64, nsamples)
   107  	for i := range samples {
   108  		samples[i] = r.NormFloat64()*stddev + mean
   109  	}
   110  	return samples
   111  }
   112  
   113  func testNormalDistribution(t *testing.T, nsamples int, mean, stddev float64, seed uint64) {
   114  	//fmt.Printf("testing nsamples=%v mean=%v stddev=%v seed=%v\n", nsamples, mean, stddev, seed);
   115  
   116  	samples := generateNormalSamples(nsamples, mean, stddev, seed)
   117  	errorScale := max(1.0, stddev) // Error scales with stddev
   118  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
   119  
   120  	// Make sure that the entire set matches the expected distribution.
   121  	checkSampleDistribution(t, samples, expected)
   122  
   123  	// Make sure that each half of the set matches the expected distribution.
   124  	checkSampleSliceDistributions(t, samples, 2, expected)
   125  
   126  	// Make sure that each 7th of the set matches the expected distribution.
   127  	checkSampleSliceDistributions(t, samples, 7, expected)
   128  }
   129  
   130  // Actual tests
   131  
   132  func TestStandardNormalValues(t *testing.T) {
   133  	for _, seed := range testSeeds {
   134  		testNormalDistribution(t, numTestSamples, 0, 1, seed)
   135  	}
   136  }
   137  
   138  func TestNonStandardNormalValues(t *testing.T) {
   139  	sdmax := 1000.0
   140  	mmax := 1000.0
   141  	if testing.Short() {
   142  		sdmax = 5
   143  		mmax = 5
   144  	}
   145  	for sd := 0.5; sd < sdmax; sd *= 2 {
   146  		for m := 0.5; m < mmax; m *= 2 {
   147  			for _, seed := range testSeeds {
   148  				testNormalDistribution(t, numTestSamples, m, sd, seed)
   149  				if testing.Short() {
   150  					break
   151  				}
   152  			}
   153  		}
   154  	}
   155  }
   156  
   157  //
   158  // Exponential distribution tests
   159  //
   160  
   161  func generateExponentialSamples(nsamples int, rate float64, seed uint64) []float64 {
   162  	r := New(NewSource(seed))
   163  	samples := make([]float64, nsamples)
   164  	for i := range samples {
   165  		samples[i] = r.ExpFloat64() / rate
   166  	}
   167  	return samples
   168  }
   169  
   170  func testExponentialDistribution(t *testing.T, nsamples int, rate float64, seed uint64) {
   171  	//fmt.Printf("testing nsamples=%v rate=%v seed=%v\n", nsamples, rate, seed)
   172  
   173  	mean := 1 / rate
   174  	stddev := mean
   175  
   176  	samples := generateExponentialSamples(nsamples, rate, seed)
   177  	errorScale := max(1.0, 1/rate) // Error scales with the inverse of the rate
   178  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.20 * errorScale}
   179  
   180  	// Make sure that the entire set matches the expected distribution.
   181  	checkSampleDistribution(t, samples, expected)
   182  
   183  	// Make sure that each half of the set matches the expected distribution.
   184  	checkSampleSliceDistributions(t, samples, 2, expected)
   185  
   186  	// Make sure that each 7th of the set matches the expected distribution.
   187  	checkSampleSliceDistributions(t, samples, 7, expected)
   188  }
   189  
   190  // Actual tests
   191  
   192  func TestStandardExponentialValues(t *testing.T) {
   193  	for _, seed := range testSeeds {
   194  		testExponentialDistribution(t, numTestSamples, 1, seed)
   195  	}
   196  }
   197  
   198  func TestNonStandardExponentialValues(t *testing.T) {
   199  	for rate := 0.05; rate < 10; rate *= 2 {
   200  		for _, seed := range testSeeds {
   201  			testExponentialDistribution(t, numTestSamples, rate, seed)
   202  			if testing.Short() {
   203  				break
   204  			}
   205  		}
   206  	}
   207  }
   208  
   209  //
   210  // Table generation tests
   211  //
   212  
   213  func initNorm() (testKn []uint32, testWn, testFn []float32) {
   214  	const m1 = 1 << 31
   215  	var (
   216  		dn float64 = rn
   217  		tn         = dn
   218  		vn float64 = 9.91256303526217e-3
   219  	)
   220  
   221  	testKn = make([]uint32, 128)
   222  	testWn = make([]float32, 128)
   223  	testFn = make([]float32, 128)
   224  
   225  	q := vn / math.Exp(-0.5*dn*dn)
   226  	testKn[0] = uint32((dn / q) * m1)
   227  	testKn[1] = 0
   228  	testWn[0] = float32(q / m1)
   229  	testWn[127] = float32(dn / m1)
   230  	testFn[0] = 1.0
   231  	testFn[127] = float32(math.Exp(-0.5 * dn * dn))
   232  	for i := 126; i >= 1; i-- {
   233  		dn = math.Sqrt(-2.0 * math.Log(vn/dn+math.Exp(-0.5*dn*dn)))
   234  		testKn[i+1] = uint32((dn / tn) * m1)
   235  		tn = dn
   236  		testFn[i] = float32(math.Exp(-0.5 * dn * dn))
   237  		testWn[i] = float32(dn / m1)
   238  	}
   239  	return
   240  }
   241  
   242  func initExp() (testKe []uint32, testWe, testFe []float32) {
   243  	const m2 = 1 << 32
   244  	var (
   245  		de float64 = re
   246  		te         = de
   247  		ve float64 = 3.9496598225815571993e-3
   248  	)
   249  
   250  	testKe = make([]uint32, 256)
   251  	testWe = make([]float32, 256)
   252  	testFe = make([]float32, 256)
   253  
   254  	q := ve / math.Exp(-de)
   255  	testKe[0] = uint32((de / q) * m2)
   256  	testKe[1] = 0
   257  	testWe[0] = float32(q / m2)
   258  	testWe[255] = float32(de / m2)
   259  	testFe[0] = 1.0
   260  	testFe[255] = float32(math.Exp(-de))
   261  	for i := 254; i >= 1; i-- {
   262  		de = -math.Log(ve/de + math.Exp(-de))
   263  		testKe[i+1] = uint32((de / te) * m2)
   264  		te = de
   265  		testFe[i] = float32(math.Exp(-de))
   266  		testWe[i] = float32(de / m2)
   267  	}
   268  	return
   269  }
   270  
   271  // compareUint32Slices returns the first index where the two slices
   272  // disagree, or <0 if the lengths are the same and all elements
   273  // are identical.
   274  func compareUint32Slices(s1, s2 []uint32) int {
   275  	if len(s1) != len(s2) {
   276  		if len(s1) > len(s2) {
   277  			return len(s2) + 1
   278  		}
   279  		return len(s1) + 1
   280  	}
   281  	for i := range s1 {
   282  		if s1[i] != s2[i] {
   283  			return i
   284  		}
   285  	}
   286  	return -1
   287  }
   288  
   289  // compareFloat32Slices returns the first index where the two slices
   290  // disagree, or <0 if the lengths are the same and all elements
   291  // are identical.
   292  func compareFloat32Slices(s1, s2 []float32) int {
   293  	if len(s1) != len(s2) {
   294  		if len(s1) > len(s2) {
   295  			return len(s2) + 1
   296  		}
   297  		return len(s1) + 1
   298  	}
   299  	for i := range s1 {
   300  		if !nearEqual(float64(s1[i]), float64(s2[i]), 0, 1e-7) {
   301  			return i
   302  		}
   303  	}
   304  	return -1
   305  }
   306  
   307  func TestNormTables(t *testing.T) {
   308  	testKn, testWn, testFn := initNorm()
   309  	if i := compareUint32Slices(kn[0:], testKn); i >= 0 {
   310  		t.Errorf("kn disagrees at index %v; %v != %v", i, kn[i], testKn[i])
   311  	}
   312  	if i := compareFloat32Slices(wn[0:], testWn); i >= 0 {
   313  		t.Errorf("wn disagrees at index %v; %v != %v", i, wn[i], testWn[i])
   314  	}
   315  	if i := compareFloat32Slices(fn[0:], testFn); i >= 0 {
   316  		t.Errorf("fn disagrees at index %v; %v != %v", i, fn[i], testFn[i])
   317  	}
   318  }
   319  
   320  func TestExpTables(t *testing.T) {
   321  	testKe, testWe, testFe := initExp()
   322  	if i := compareUint32Slices(ke[0:], testKe); i >= 0 {
   323  		t.Errorf("ke disagrees at index %v; %v != %v", i, ke[i], testKe[i])
   324  	}
   325  	if i := compareFloat32Slices(we[0:], testWe); i >= 0 {
   326  		t.Errorf("we disagrees at index %v; %v != %v", i, we[i], testWe[i])
   327  	}
   328  	if i := compareFloat32Slices(fe[0:], testFe); i >= 0 {
   329  		t.Errorf("fe disagrees at index %v; %v != %v", i, fe[i], testFe[i])
   330  	}
   331  }
   332  
   333  func hasSlowFloatingPoint() bool {
   334  	switch runtime.GOARCH {
   335  	case "arm":
   336  		return os.Getenv("GOARM") == "5"
   337  	case "mips", "mipsle", "mips64", "mips64le":
   338  		// Be conservative and assume that all mips boards
   339  		// have emulated floating point.
   340  		// TODO: detect what it actually has.
   341  		return true
   342  	}
   343  	return false
   344  }
   345  
   346  func TestFloat32(t *testing.T) {
   347  	// For issue 6721, the problem came after 7533753 calls, so check 10e6.
   348  	num := int(10e6)
   349  	// But do the full amount only on builders (not locally).
   350  	// But ARM5 floating point emulation is slow (Issue 10749), so
   351  	// do less for that builder:
   352  	if testing.Short() && hasSlowFloatingPoint() { // TODO: (testenv.Builder() == "" || hasSlowFloatingPoint())
   353  		num /= 100 // 1.72 seconds instead of 172 seconds
   354  	}
   355  
   356  	r := New(NewSource(1))
   357  	for ct := 0; ct < num; ct++ {
   358  		f := r.Float32()
   359  		if f >= 1 {
   360  			t.Fatal("Float32() should be in range [0,1). ct:", ct, "f:", f)
   361  		}
   362  	}
   363  }
   364  
   365  func testReadUniformity(t *testing.T, n int, seed uint64) {
   366  	r := New(NewSource(seed))
   367  	buf := make([]byte, n)
   368  	nRead, err := r.Read(buf)
   369  	if err != nil {
   370  		t.Errorf("Read err %v", err)
   371  	}
   372  	if nRead != n {
   373  		t.Errorf("Read returned unexpected n; %d != %d", nRead, n)
   374  	}
   375  
   376  	// Expect a uniform distribution of byte values, which lie in [0, 255].
   377  	var (
   378  		mean       = 255.0 / 2
   379  		stddev     = 256.0 / math.Sqrt(12.0)
   380  		errorScale = stddev / math.Sqrt(float64(n))
   381  	)
   382  
   383  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
   384  
   385  	// Cast bytes as floats to use the common distribution-validity checks.
   386  	samples := make([]float64, n)
   387  	for i, val := range buf {
   388  		samples[i] = float64(val)
   389  	}
   390  	// Make sure that the entire set matches the expected distribution.
   391  	checkSampleDistribution(t, samples, expected)
   392  }
   393  
   394  func TestReadUniformity(t *testing.T) {
   395  	testBufferSizes := []int{
   396  		2, 4, 7, 64, 1024, 1 << 16, 1 << 20,
   397  	}
   398  	for _, seed := range testSeeds {
   399  		for _, n := range testBufferSizes {
   400  			testReadUniformity(t, n, seed)
   401  		}
   402  	}
   403  }
   404  
   405  func TestReadEmpty(t *testing.T) {
   406  	r := New(NewSource(1))
   407  	buf := make([]byte, 0)
   408  	n, err := r.Read(buf)
   409  	if err != nil {
   410  		t.Errorf("Read err into empty buffer; %v", err)
   411  	}
   412  	if n != 0 {
   413  		t.Errorf("Read into empty buffer returned unexpected n of %d", n)
   414  	}
   415  }
   416  
   417  func TestReadByOneByte(t *testing.T) {
   418  	r := New(NewSource(1))
   419  	b1 := make([]byte, 100)
   420  	_, err := io.ReadFull(iotest.OneByteReader(r), b1)
   421  	if err != nil {
   422  		t.Errorf("read by one byte: %v", err)
   423  	}
   424  	r = New(NewSource(1))
   425  	b2 := make([]byte, 100)
   426  	_, err = r.Read(b2)
   427  	if err != nil {
   428  		t.Errorf("read: %v", err)
   429  	}
   430  	if !bytes.Equal(b1, b2) {
   431  		t.Errorf("read by one byte vs single read:\n%x\n%x", b1, b2)
   432  	}
   433  }
   434  
   435  func TestReadSeedReset(t *testing.T) {
   436  	r := New(NewSource(42))
   437  	b1 := make([]byte, 128)
   438  	_, err := r.Read(b1)
   439  	if err != nil {
   440  		t.Errorf("read: %v", err)
   441  	}
   442  	r.Seed(42)
   443  	b2 := make([]byte, 128)
   444  	_, err = r.Read(b2)
   445  	if err != nil {
   446  		t.Errorf("read: %v", err)
   447  	}
   448  	if !bytes.Equal(b1, b2) {
   449  		t.Errorf("mismatch after re-seed:\n%x\n%x", b1, b2)
   450  	}
   451  }
   452  
   453  func TestShuffleSmall(t *testing.T) {
   454  	// Check that Shuffle allows n=0 and n=1, but that swap is never called for them.
   455  	r := New(NewSource(1))
   456  	for n := 0; n <= 1; n++ {
   457  		r.Shuffle(n, func(i, j int) { t.Fatalf("swap called, n=%d i=%d j=%d", n, i, j) })
   458  	}
   459  }
   460  
   461  func TestPCGSourceRoundTrip(t *testing.T) {
   462  	var src PCGSource
   463  	src.Seed(uint64(time.Now().Unix()))
   464  
   465  	src.Uint64() // Step PRNG once to makes sure high and low are different.
   466  
   467  	buf, err := src.MarshalBinary()
   468  	if err != nil {
   469  		t.Errorf("unexpected error marshaling state: %v", err)
   470  	}
   471  
   472  	var dst PCGSource
   473  	// Get dst into a non-zero state.
   474  	dst.Seed(1)
   475  	for i := 0; i < 10; i++ {
   476  		dst.Uint64()
   477  	}
   478  
   479  	err = dst.UnmarshalBinary(buf)
   480  	if err != nil {
   481  		t.Errorf("unexpected error unmarshaling state: %v", err)
   482  	}
   483  
   484  	if dst != src {
   485  		t.Errorf("mismatch between generator states: got:%+v want:%+v", dst, src)
   486  	}
   487  }
   488  
   489  // Benchmarks
   490  
   491  func BenchmarkSource(b *testing.B) {
   492  	rng := NewSource(0)
   493  	for n := b.N; n > 0; n-- {
   494  		rng.Uint64()
   495  	}
   496  }
   497  
   498  func BenchmarkInt63Threadsafe(b *testing.B) {
   499  	for n := b.N; n > 0; n-- {
   500  		Int63()
   501  	}
   502  }
   503  
   504  func BenchmarkInt63ThreadsafeParallel(b *testing.B) {
   505  	b.RunParallel(func(pb *testing.PB) {
   506  		for pb.Next() {
   507  			Int63()
   508  		}
   509  	})
   510  }
   511  
   512  func BenchmarkInt63Unthreadsafe(b *testing.B) {
   513  	r := New(NewSource(1))
   514  	for n := b.N; n > 0; n-- {
   515  		r.Int63()
   516  	}
   517  }
   518  
   519  func BenchmarkIntn1000(b *testing.B) {
   520  	r := New(NewSource(1))
   521  	for n := b.N; n > 0; n-- {
   522  		r.Intn(1000)
   523  	}
   524  }
   525  
   526  func BenchmarkInt63n1000(b *testing.B) {
   527  	r := New(NewSource(1))
   528  	for n := b.N; n > 0; n-- {
   529  		r.Int63n(1000)
   530  	}
   531  }
   532  
   533  func BenchmarkInt31n1000(b *testing.B) {
   534  	r := New(NewSource(1))
   535  	for n := b.N; n > 0; n-- {
   536  		r.Int31n(1000)
   537  	}
   538  }
   539  
   540  func BenchmarkFloat32(b *testing.B) {
   541  	r := New(NewSource(1))
   542  	for n := b.N; n > 0; n-- {
   543  		r.Float32()
   544  	}
   545  }
   546  
   547  func BenchmarkFloat64(b *testing.B) {
   548  	r := New(NewSource(1))
   549  	for n := b.N; n > 0; n-- {
   550  		r.Float64()
   551  	}
   552  }
   553  
   554  func BenchmarkPerm3(b *testing.B) {
   555  	r := New(NewSource(1))
   556  	for n := b.N; n > 0; n-- {
   557  		r.Perm(3)
   558  	}
   559  }
   560  
   561  func BenchmarkPerm30(b *testing.B) {
   562  	r := New(NewSource(1))
   563  	for n := b.N; n > 0; n-- {
   564  		r.Perm(30)
   565  	}
   566  }
   567  
   568  func BenchmarkPerm30ViaShuffle(b *testing.B) {
   569  	r := New(NewSource(1))
   570  	for n := b.N; n > 0; n-- {
   571  		p := make([]int, 30)
   572  		for i := range p {
   573  			p[i] = i
   574  		}
   575  		r.Shuffle(30, func(i, j int) { p[i], p[j] = p[j], p[i] })
   576  	}
   577  }
   578  
   579  // BenchmarkShuffleOverhead uses a minimal swap function
   580  // to measure just the shuffling overhead.
   581  func BenchmarkShuffleOverhead(b *testing.B) {
   582  	r := New(NewSource(1))
   583  	for n := b.N; n > 0; n-- {
   584  		r.Shuffle(52, func(i, j int) {
   585  			if i < 0 || i >= 52 || j < 0 || j >= 52 {
   586  				b.Fatalf("bad swap(%d, %d)", i, j)
   587  			}
   588  		})
   589  	}
   590  }
   591  
   592  func BenchmarkRead3(b *testing.B) {
   593  	r := New(NewSource(1))
   594  	buf := make([]byte, 3)
   595  	b.ResetTimer()
   596  	for n := b.N; n > 0; n-- {
   597  		r.Read(buf)
   598  	}
   599  }
   600  
   601  func BenchmarkRead64(b *testing.B) {
   602  	r := New(NewSource(1))
   603  	buf := make([]byte, 64)
   604  	b.ResetTimer()
   605  	for n := b.N; n > 0; n-- {
   606  		r.Read(buf)
   607  	}
   608  }
   609  
   610  func BenchmarkRead1000(b *testing.B) {
   611  	r := New(NewSource(1))
   612  	buf := make([]byte, 1000)
   613  	b.ResetTimer()
   614  	for n := b.N; n > 0; n-- {
   615  		r.Read(buf)
   616  	}
   617  }
   618  

View as plain text