The Go Programming Language

Source file src/pkg/rand/rand_test.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
     6	
     7	import (
     8		"math"
     9		"fmt"
    10		"os"
    11		"testing"
    12	)
    13	
    14	const (
    15		numTestSamples = 10000
    16	)
    17	
    18	type statsResults struct {
    19		mean        float64
    20		stddev      float64
    21		closeEnough float64
    22		maxError    float64
    23	}
    24	
    25	func max(a, b float64) float64 {
    26		if a > b {
    27			return a
    28		}
    29		return b
    30	}
    31	
    32	func nearEqual(a, b, closeEnough, maxError float64) bool {
    33		absDiff := math.Fabs(a - b)
    34		if absDiff < closeEnough { // Necessary when one value is zero and one value is close to zero.
    35			return true
    36		}
    37		return absDiff/max(math.Fabs(a), math.Fabs(b)) < maxError
    38	}
    39	
    40	var testSeeds = []int64{1, 1754801282, 1698661970, 1550503961}
    41	
    42	// checkSimilarDistribution returns success if the mean and stddev of the
    43	// two statsResults are similar.
    44	func (this *statsResults) checkSimilarDistribution(expected *statsResults) os.Error {
    45		if !nearEqual(this.mean, expected.mean, expected.closeEnough, expected.maxError) {
    46			s := fmt.Sprintf("mean %v != %v (allowed error %v, %v)", this.mean, expected.mean, expected.closeEnough, expected.maxError)
    47			fmt.Println(s)
    48			return os.NewError(s)
    49		}
    50		if !nearEqual(this.stddev, expected.stddev, 0, expected.maxError) {
    51			s := fmt.Sprintf("stddev %v != %v (allowed error %v, %v)", this.stddev, expected.stddev, expected.closeEnough, expected.maxError)
    52			fmt.Println(s)
    53			return os.NewError(s)
    54		}
    55		return nil
    56	}
    57	
    58	func getStatsResults(samples []float64) *statsResults {
    59		res := new(statsResults)
    60		var sum float64
    61		for i := range samples {
    62			sum += samples[i]
    63		}
    64		res.mean = sum / float64(len(samples))
    65		var devsum float64
    66		for i := range samples {
    67			devsum += math.Pow(samples[i]-res.mean, 2)
    68		}
    69		res.stddev = math.Sqrt(devsum / float64(len(samples)))
    70		return res
    71	}
    72	
    73	func checkSampleDistribution(t *testing.T, samples []float64, expected *statsResults) {
    74		actual := getStatsResults(samples)
    75		err := actual.checkSimilarDistribution(expected)
    76		if err != nil {
    77			t.Errorf(err.String())
    78		}
    79	}
    80	
    81	func checkSampleSliceDistributions(t *testing.T, samples []float64, nslices int, expected *statsResults) {
    82		chunk := len(samples) / nslices
    83		for i := 0; i < nslices; i++ {
    84			low := i * chunk
    85			var high int
    86			if i == nslices-1 {
    87				high = len(samples) - 1
    88			} else {
    89				high = (i + 1) * chunk
    90			}
    91			checkSampleDistribution(t, samples[low:high], expected)
    92		}
    93	}
    94	
    95	//
    96	// Normal distribution tests
    97	//
    98	
    99	func generateNormalSamples(nsamples int, mean, stddev float64, seed int64) []float64 {
   100		r := New(NewSource(seed))
   101		samples := make([]float64, nsamples)
   102		for i := range samples {
   103			samples[i] = r.NormFloat64()*stddev + mean
   104		}
   105		return samples
   106	}
   107	
   108	func testNormalDistribution(t *testing.T, nsamples int, mean, stddev float64, seed int64) {
   109		//fmt.Printf("testing nsamples=%v mean=%v stddev=%v seed=%v\n", nsamples, mean, stddev, seed);
   110	
   111		samples := generateNormalSamples(nsamples, mean, stddev, seed)
   112		errorScale := max(1.0, stddev) // Error scales with stddev
   113		expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
   114	
   115		// Make sure that the entire set matches the expected distribution.
   116		checkSampleDistribution(t, samples, expected)
   117	
   118		// Make sure that each half of the set matches the expected distribution.
   119		checkSampleSliceDistributions(t, samples, 2, expected)
   120	
   121		// Make sure that each 7th of the set matches the expected distribution.
   122		checkSampleSliceDistributions(t, samples, 7, expected)
   123	}
   124	
   125	// Actual tests
   126	
   127	func TestStandardNormalValues(t *testing.T) {
   128		for _, seed := range testSeeds {
   129			testNormalDistribution(t, numTestSamples, 0, 1, seed)
   130		}
   131	}
   132	
   133	func TestNonStandardNormalValues(t *testing.T) {
   134		for sd := 0.5; sd < 1000; sd *= 2 {
   135			for m := 0.5; m < 1000; m *= 2 {
   136				for _, seed := range testSeeds {
   137					testNormalDistribution(t, numTestSamples, m, sd, seed)
   138				}
   139			}
   140		}
   141	}
   142	
   143	//
   144	// Exponential distribution tests
   145	//
   146	
   147	func generateExponentialSamples(nsamples int, rate float64, seed int64) []float64 {
   148		r := New(NewSource(seed))
   149		samples := make([]float64, nsamples)
   150		for i := range samples {
   151			samples[i] = r.ExpFloat64() / rate
   152		}
   153		return samples
   154	}
   155	
   156	func testExponentialDistribution(t *testing.T, nsamples int, rate float64, seed int64) {
   157		//fmt.Printf("testing nsamples=%v rate=%v seed=%v\n", nsamples, rate, seed);
   158	
   159		mean := 1 / rate
   160		stddev := mean
   161	
   162		samples := generateExponentialSamples(nsamples, rate, seed)
   163		errorScale := max(1.0, 1/rate) // Error scales with the inverse of the rate
   164		expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.20 * errorScale}
   165	
   166		// Make sure that the entire set matches the expected distribution.
   167		checkSampleDistribution(t, samples, expected)
   168	
   169		// Make sure that each half of the set matches the expected distribution.
   170		checkSampleSliceDistributions(t, samples, 2, expected)
   171	
   172		// Make sure that each 7th of the set matches the expected distribution.
   173		checkSampleSliceDistributions(t, samples, 7, expected)
   174	}
   175	
   176	// Actual tests
   177	
   178	func TestStandardExponentialValues(t *testing.T) {
   179		for _, seed := range testSeeds {
   180			testExponentialDistribution(t, numTestSamples, 1, seed)
   181		}
   182	}
   183	
   184	func TestNonStandardExponentialValues(t *testing.T) {
   185		for rate := 0.05; rate < 10; rate *= 2 {
   186			for _, seed := range testSeeds {
   187				testExponentialDistribution(t, numTestSamples, rate, seed)
   188			}
   189		}
   190	}
   191	
   192	//
   193	// Table generation tests
   194	//
   195	
   196	func initNorm() (testKn []uint32, testWn, testFn []float32) {
   197		const m1 = 1 << 31
   198		var (
   199			dn float64 = rn
   200			tn         = dn
   201			vn float64 = 9.91256303526217e-3
   202		)
   203	
   204		testKn = make([]uint32, 128)
   205		testWn = make([]float32, 128)
   206		testFn = make([]float32, 128)
   207	
   208		q := vn / math.Exp(-0.5*dn*dn)
   209		testKn[0] = uint32((dn / q) * m1)
   210		testKn[1] = 0
   211		testWn[0] = float32(q / m1)
   212		testWn[127] = float32(dn / m1)
   213		testFn[0] = 1.0
   214		testFn[127] = float32(math.Exp(-0.5 * dn * dn))
   215		for i := 126; i >= 1; i-- {
   216			dn = math.Sqrt(-2.0 * math.Log(vn/dn+math.Exp(-0.5*dn*dn)))
   217			testKn[i+1] = uint32((dn / tn) * m1)
   218			tn = dn
   219			testFn[i] = float32(math.Exp(-0.5 * dn * dn))
   220			testWn[i] = float32(dn / m1)
   221		}
   222		return
   223	}
   224	
   225	func initExp() (testKe []uint32, testWe, testFe []float32) {
   226		const m2 = 1 << 32
   227		var (
   228			de float64 = re
   229			te         = de
   230			ve float64 = 3.9496598225815571993e-3
   231		)
   232	
   233		testKe = make([]uint32, 256)
   234		testWe = make([]float32, 256)
   235		testFe = make([]float32, 256)
   236	
   237		q := ve / math.Exp(-de)
   238		testKe[0] = uint32((de / q) * m2)
   239		testKe[1] = 0
   240		testWe[0] = float32(q / m2)
   241		testWe[255] = float32(de / m2)
   242		testFe[0] = 1.0
   243		testFe[255] = float32(math.Exp(-de))
   244		for i := 254; i >= 1; i-- {
   245			de = -math.Log(ve/de + math.Exp(-de))
   246			testKe[i+1] = uint32((de / te) * m2)
   247			te = de
   248			testFe[i] = float32(math.Exp(-de))
   249			testWe[i] = float32(de / m2)
   250		}
   251		return
   252	}
   253	
   254	// compareUint32Slices returns the first index where the two slices
   255	// disagree, or <0 if the lengths are the same and all elements
   256	// are identical.
   257	func compareUint32Slices(s1, s2 []uint32) int {
   258		if len(s1) != len(s2) {
   259			if len(s1) > len(s2) {
   260				return len(s2) + 1
   261			}
   262			return len(s1) + 1
   263		}
   264		for i := range s1 {
   265			if s1[i] != s2[i] {
   266				return i
   267			}
   268		}
   269		return -1
   270	}
   271	
   272	// compareFloat32Slices returns the first index where the two slices
   273	// disagree, or <0 if the lengths are the same and all elements
   274	// are identical.
   275	func compareFloat32Slices(s1, s2 []float32) int {
   276		if len(s1) != len(s2) {
   277			if len(s1) > len(s2) {
   278				return len(s2) + 1
   279			}
   280			return len(s1) + 1
   281		}
   282		for i := range s1 {
   283			if !nearEqual(float64(s1[i]), float64(s2[i]), 0, 1e-7) {
   284				return i
   285			}
   286		}
   287		return -1
   288	}
   289	
   290	func TestNormTables(t *testing.T) {
   291		testKn, testWn, testFn := initNorm()
   292		if i := compareUint32Slices(kn[0:], testKn); i >= 0 {
   293			t.Errorf("kn disagrees at index %v; %v != %v", i, kn[i], testKn[i])
   294		}
   295		if i := compareFloat32Slices(wn[0:], testWn); i >= 0 {
   296			t.Errorf("wn disagrees at index %v; %v != %v", i, wn[i], testWn[i])
   297		}
   298		if i := compareFloat32Slices(fn[0:], testFn); i >= 0 {
   299			t.Errorf("fn disagrees at index %v; %v != %v", i, fn[i], testFn[i])
   300		}
   301	}
   302	
   303	func TestExpTables(t *testing.T) {
   304		testKe, testWe, testFe := initExp()
   305		if i := compareUint32Slices(ke[0:], testKe); i >= 0 {
   306			t.Errorf("ke disagrees at index %v; %v != %v", i, ke[i], testKe[i])
   307		}
   308		if i := compareFloat32Slices(we[0:], testWe); i >= 0 {
   309			t.Errorf("we disagrees at index %v; %v != %v", i, we[i], testWe[i])
   310		}
   311		if i := compareFloat32Slices(fe[0:], testFe); i >= 0 {
   312			t.Errorf("fe disagrees at index %v; %v != %v", i, fe[i], testFe[i])
   313		}
   314	}
   315	
   316	// Benchmarks
   317	
   318	func BenchmarkInt63Threadsafe(b *testing.B) {
   319		for n := b.N; n > 0; n-- {
   320			Int63()
   321		}
   322	}
   323	
   324	func BenchmarkInt63Unthreadsafe(b *testing.B) {
   325		r := New(NewSource(1))
   326		for n := b.N; n > 0; n-- {
   327			r.Int63()
   328		}
   329	}
   330	
   331	func BenchmarkIntn1000(b *testing.B) {
   332		r := New(NewSource(1))
   333		for n := b.N; n > 0; n-- {
   334			r.Intn(1000)
   335		}
   336	}
   337	
   338	func BenchmarkInt63n1000(b *testing.B) {
   339		r := New(NewSource(1))
   340		for n := b.N; n > 0; n-- {
   341			r.Int63n(1000)
   342		}
   343	}
   344	
   345	func BenchmarkInt31n1000(b *testing.B) {
   346		r := New(NewSource(1))
   347		for n := b.N; n > 0; n-- {
   348			r.Int31n(1000)
   349		}
   350	}

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.