libgo/go/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         "math"
  10         "fmt"
  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 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.Error())
  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 }