libgo/go/math/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         "errors"
   9         "fmt"
  10         "math"
  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.Abs(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.Abs(a), math.Abs(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) 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 errors.New(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 errors.New(s)
  54         }
  55         return nil
  56 }
  57
  58 func getStatsResults(samples []float64) *statsResults {
  59         res := new(statsResults)
  60         var sum, squaresum float64
  61         for _, s := range samples {
  62                 sum += s
  63                 squaresum += s * s
  64         }
  65         res.mean = sum / float64(len(samples))
  66         res.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean)
  67         return res
  68 }
  69
  70 func checkSampleDistribution(t *testing.T, samples []float64, expected *statsResults) {
  71         actual := getStatsResults(samples)
  72         err := actual.checkSimilarDistribution(expected)
  73         if err != nil {
  74                 t.Errorf(err.Error())
  75         }
  76 }
  77
  78 func checkSampleSliceDistributions(t *testing.T, samples []float64, nslices int, expected *statsResults) {
  79         chunk := len(samples) / nslices
  80         for i := 0; i < nslices; i++ {
  81                 low := i * chunk
  82                 var high int
  83                 if i == nslices-1 {
  84                         high = len(samples) - 1
  85                 } else {
  86                         high = (i + 1) * chunk
  87                 }
  88                 checkSampleDistribution(t, samples[low:high], expected)
  89         }
  90 }
  91
  92 //
  93 // Normal distribution tests
  94 //
  95
  96 func generateNormalSamples(nsamples int, mean, stddev float64, seed int64) []float64 {
  97         r := New(NewSource(seed))
  98         samples := make([]float64, nsamples)
  99         for i := range samples {
 100                 samples[i] = r.NormFloat64()*stddev + mean
 101         }
 102         return samples
 103 }
 104
 105 func testNormalDistribution(t *testing.T, nsamples int, mean, stddev float64, seed int64) {
 106         //fmt.Printf("testing nsamples=%v mean=%v stddev=%v seed=%v\n", nsamples, mean, stddev, seed);
 107
 108         samples := generateNormalSamples(nsamples, mean, stddev, seed)
 109         errorScale := max(1.0, stddev) // Error scales with stddev
 110         expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
 111
 112         // Make sure that the entire set matches the expected distribution.
 113         checkSampleDistribution(t, samples, expected)
 114
 115         // Make sure that each half of the set matches the expected distribution.
 116         checkSampleSliceDistributions(t, samples, 2, expected)
 117
 118         // Make sure that each 7th of the set matches the expected distribution.
 119         checkSampleSliceDistributions(t, samples, 7, expected)
 120 }
 121
 122 // Actual tests
 123
 124 func TestStandardNormalValues(t *testing.T) {
 125         for _, seed := range testSeeds {
 126                 testNormalDistribution(t, numTestSamples, 0, 1, seed)
 127         }
 128 }
 129
 130 func TestNonStandardNormalValues(t *testing.T) {
 131         sdmax := 1000.0
 132         mmax := 1000.0
 133         if testing.Short() {
 134                 sdmax = 5
 135                 mmax = 5
 136         }
 137         for sd := 0.5; sd < sdmax; sd *= 2 {
 138                 for m := 0.5; m < mmax; m *= 2 {
 139                         for _, seed := range testSeeds {
 140                                 testNormalDistribution(t, numTestSamples, m, sd, seed)
 141                                 if testing.Short() {
 142                                         break
 143                                 }
 144                         }
 145                 }
 146         }
 147 }
 148
 149 //
 150 // Exponential distribution tests
 151 //
 152
 153 func generateExponentialSamples(nsamples int, rate float64, seed int64) []float64 {
 154         r := New(NewSource(seed))
 155         samples := make([]float64, nsamples)
 156         for i := range samples {
 157                 samples[i] = r.ExpFloat64() / rate
 158         }
 159         return samples
 160 }
 161
 162 func testExponentialDistribution(t *testing.T, nsamples int, rate float64, seed int64) {
 163         //fmt.Printf("testing nsamples=%v rate=%v seed=%v\n", nsamples, rate, seed);
 164
 165         mean := 1 / rate
 166         stddev := mean
 167
 168         samples := generateExponentialSamples(nsamples, rate, seed)
 169         errorScale := max(1.0, 1/rate) // Error scales with the inverse of the rate
 170         expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.20 * errorScale}
 171
 172         // Make sure that the entire set matches the expected distribution.
 173         checkSampleDistribution(t, samples, expected)
 174
 175         // Make sure that each half of the set matches the expected distribution.
 176         checkSampleSliceDistributions(t, samples, 2, expected)
 177
 178         // Make sure that each 7th of the set matches the expected distribution.
 179         checkSampleSliceDistributions(t, samples, 7, expected)
 180 }
 181
 182 // Actual tests
 183
 184 func TestStandardExponentialValues(t *testing.T) {
 185         for _, seed := range testSeeds {
 186                 testExponentialDistribution(t, numTestSamples, 1, seed)
 187         }
 188 }
 189
 190 func TestNonStandardExponentialValues(t *testing.T) {
 191         for rate := 0.05; rate < 10; rate *= 2 {
 192                 for _, seed := range testSeeds {
 193                         testExponentialDistribution(t, numTestSamples, rate, seed)
 194                         if testing.Short() {
 195                                 break
 196                         }
 197                 }
 198         }
 199 }
 200
 201 //
 202 // Table generation tests
 203 //
 204
 205 func initNorm() (testKn []uint32, testWn, testFn []float32) {
 206         const m1 = 1 << 31
 207         var (
 208                 dn float64 = rn
 209                 tn         = dn
 210                 vn float64 = 9.91256303526217e-3
 211         )
 212
 213         testKn = make([]uint32, 128)
 214         testWn = make([]float32, 128)
 215         testFn = make([]float32, 128)
 216
 217         q := vn / math.Exp(-0.5*dn*dn)
 218         testKn[0] = uint32((dn / q) * m1)
 219         testKn[1] = 0
 220         testWn[0] = float32(q / m1)
 221         testWn[127] = float32(dn / m1)
 222         testFn[0] = 1.0
 223         testFn[127] = float32(math.Exp(-0.5 * dn * dn))
 224         for i := 126; i >= 1; i-- {
 225                 dn = math.Sqrt(-2.0 * math.Log(vn/dn+math.Exp(-0.5*dn*dn)))
 226                 testKn[i+1] = uint32((dn / tn) * m1)
 227                 tn = dn
 228                 testFn[i] = float32(math.Exp(-0.5 * dn * dn))
 229                 testWn[i] = float32(dn / m1)
 230         }
 231         return
 232 }
 233
 234 func initExp() (testKe []uint32, testWe, testFe []float32) {
 235         const m2 = 1 << 32
 236         var (
 237                 de float64 = re
 238                 te         = de
 239                 ve float64 = 3.9496598225815571993e-3
 240         )
 241
 242         testKe = make([]uint32, 256)
 243         testWe = make([]float32, 256)
 244         testFe = make([]float32, 256)
 245
 246         q := ve / math.Exp(-de)
 247         testKe[0] = uint32((de / q) * m2)
 248         testKe[1] = 0
 249         testWe[0] = float32(q / m2)
 250         testWe[255] = float32(de / m2)
 251         testFe[0] = 1.0
 252         testFe[255] = float32(math.Exp(-de))
 253         for i := 254; i >= 1; i-- {
 254                 de = -math.Log(ve/de + math.Exp(-de))
 255                 testKe[i+1] = uint32((de / te) * m2)
 256                 te = de
 257                 testFe[i] = float32(math.Exp(-de))
 258                 testWe[i] = float32(de / m2)
 259         }
 260         return
 261 }
 262
 263 // compareUint32Slices returns the first index where the two slices
 264 // disagree, or <0 if the lengths are the same and all elements
 265 // are identical.
 266 func compareUint32Slices(s1, s2 []uint32) int {
 267         if len(s1) != len(s2) {
 268                 if len(s1) > len(s2) {
 269                         return len(s2) + 1
 270                 }
 271                 return len(s1) + 1
 272         }
 273         for i := range s1 {
 274                 if s1[i] != s2[i] {
 275                         return i
 276                 }
 277         }
 278         return -1
 279 }
 280
 281 // compareFloat32Slices returns the first index where the two slices
 282 // disagree, or <0 if the lengths are the same and all elements
 283 // are identical.
 284 func compareFloat32Slices(s1, s2 []float32) int {
 285         if len(s1) != len(s2) {
 286                 if len(s1) > len(s2) {
 287                         return len(s2) + 1
 288                 }
 289                 return len(s1) + 1
 290         }
 291         for i := range s1 {
 292                 if !nearEqual(float64(s1[i]), float64(s2[i]), 0, 1e-7) {
 293                         return i
 294                 }
 295         }
 296         return -1
 297 }
 298
 299 func TestNormTables(t *testing.T) {
 300         testKn, testWn, testFn := initNorm()
 301         if i := compareUint32Slices(kn[0:], testKn); i >= 0 {
 302                 t.Errorf("kn disagrees at index %v; %v != %v", i, kn[i], testKn[i])
 303         }
 304         if i := compareFloat32Slices(wn[0:], testWn); i >= 0 {
 305                 t.Errorf("wn disagrees at index %v; %v != %v", i, wn[i], testWn[i])
 306         }
 307         if i := compareFloat32Slices(fn[0:], testFn); i >= 0 {
 308                 t.Errorf("fn disagrees at index %v; %v != %v", i, fn[i], testFn[i])
 309         }
 310 }
 311
 312 func TestExpTables(t *testing.T) {
 313         testKe, testWe, testFe := initExp()
 314         if i := compareUint32Slices(ke[0:], testKe); i >= 0 {
 315                 t.Errorf("ke disagrees at index %v; %v != %v", i, ke[i], testKe[i])
 316         }
 317         if i := compareFloat32Slices(we[0:], testWe); i >= 0 {
 318                 t.Errorf("we disagrees at index %v; %v != %v", i, we[i], testWe[i])
 319         }
 320         if i := compareFloat32Slices(fe[0:], testFe); i >= 0 {
 321                 t.Errorf("fe disagrees at index %v; %v != %v", i, fe[i], testFe[i])
 322         }
 323 }
 324
 325 // For issue 6721, the problem came after 7533753 calls, so check 10e6.
 326 func TestFloat32(t *testing.T) {
 327         r := New(NewSource(1))
 328         for ct := 0; ct < 10e6; ct++ {
 329                 f := r.Float32()
 330                 if f >= 1 {
 331                         t.Fatal("Float32() should be in range [0,1). ct:", ct, "f:", f)
 332                 }
 333         }
 334 }
 335
 336 // Benchmarks
 337
 338 func BenchmarkInt63Threadsafe(b *testing.B) {
 339         for n := b.N; n > 0; n-- {
 340                 Int63()
 341         }
 342 }
 343
 344 func BenchmarkInt63Unthreadsafe(b *testing.B) {
 345         r := New(NewSource(1))
 346         for n := b.N; n > 0; n-- {
 347                 r.Int63()
 348         }
 349 }
 350
 351 func BenchmarkIntn1000(b *testing.B) {
 352         r := New(NewSource(1))
 353         for n := b.N; n > 0; n-- {
 354                 r.Intn(1000)
 355         }
 356 }
 357
 358 func BenchmarkInt63n1000(b *testing.B) {
 359         r := New(NewSource(1))
 360         for n := b.N; n > 0; n-- {
 361                 r.Int63n(1000)
 362         }
 363 }
 364
 365 func BenchmarkInt31n1000(b *testing.B) {
 366         r := New(NewSource(1))
 367         for n := b.N; n > 0; n-- {
 368                 r.Int31n(1000)
 369         }
 370 }
 371
 372 func BenchmarkFloat32(b *testing.B) {
 373         r := New(NewSource(1))
 374         for n := b.N; n > 0; n-- {
 375                 r.Float32()
 376         }
 377 }
 378
 379 func BenchmarkPerm3(b *testing.B) {
 380         r := New(NewSource(1))
 381         for n := b.N; n > 0; n-- {
 382                 r.Perm(3)
 383         }
 384 }
 385
 386 func BenchmarkPerm30(b *testing.B) {
 387         r := New(NewSource(1))
 388         for n := b.N; n > 0; n-- {
 389                 r.Perm(30)
 390         }
 391 }