1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this file,
* You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "mozilla/Assertions.h"
#include "mozilla/FastBernoulliTrial.h"
#include <math.h>
// Note that because we always provide FastBernoulliTrial with a fixed
// pseudorandom seed in these tests, the results here are completely
// deterministic.
//
// A non-optimized version of this test runs in .009s on my laptop. Using larger
// sample sizes lets us meet tighter bounds on the counts.
static void
TestProportions()
{
mozilla::FastBernoulliTrial bernoulli(1.0,
698079309544035222ULL,
6012389156611637584ULL);
for (size_t i = 0; i < 100; i++)
MOZ_RELEASE_ASSERT(bernoulli.trial());
{
bernoulli.setProbability(0.5);
size_t count = 0;
for (size_t i = 0; i < 1000; i++)
count += bernoulli.trial();
MOZ_RELEASE_ASSERT(count == 496);
}
{
bernoulli.setProbability(0.001);
size_t count = 0;
for (size_t i = 0; i < 1000; i++)
count += bernoulli.trial();
MOZ_RELEASE_ASSERT(count == 2);
}
{
bernoulli.setProbability(0.85);
size_t count = 0;
for (size_t i = 0; i < 1000; i++)
count += bernoulli.trial();
MOZ_RELEASE_ASSERT(count == 852);
}
bernoulli.setProbability(0.0);
for (size_t i = 0; i < 100; i++)
MOZ_RELEASE_ASSERT(!bernoulli.trial());
}
static void
TestHarmonics()
{
mozilla::FastBernoulliTrial bernoulli(0.1,
698079309544035222ULL,
6012389156611637584ULL);
const size_t n = 100000;
bool trials[n];
for (size_t i = 0; i < n; i++)
trials[i] = bernoulli.trial();
// For each harmonic and phase, check that the proportion sampled is
// within acceptable bounds.
for (size_t harmonic = 1; harmonic < 20; harmonic++) {
size_t expected = n / harmonic / 10;
size_t low_expected = expected * 85 / 100;
size_t high_expected = expected * 115 / 100;
for (size_t phase = 0; phase < harmonic; phase++) {
size_t count = 0;
for (size_t i = phase; i < n; i += harmonic)
count += trials[i];
MOZ_RELEASE_ASSERT(low_expected <= count && count <= high_expected);
}
}
}
static void
TestTrialN()
{
mozilla::FastBernoulliTrial bernoulli(0.01,
0x67ff17e25d855942ULL,
0x74f298193fe1c5b1ULL);
{
size_t count = 0;
for (size_t i = 0; i < 10000; i++)
count += bernoulli.trial(1);
// Expected value: 0.01 * 10000 == 100
MOZ_RELEASE_ASSERT(count == 97);
}
{
size_t count = 0;
for (size_t i = 0; i < 10000; i++)
count += bernoulli.trial(3);
// Expected value: (1 - (1 - 0.01) ** 3) == 0.0297,
// 0.0297 * 10000 == 297
MOZ_RELEASE_ASSERT(count == 304);
}
{
size_t count = 0;
for (size_t i = 0; i < 10000; i++)
count += bernoulli.trial(10);
// Expected value: (1 - (1 - 0.01) ** 10) == 0.0956,
// 0.0956 * 10000 == 956
MOZ_RELEASE_ASSERT(count == 936);
}
{
size_t count = 0;
for (size_t i = 0; i < 10000; i++)
count += bernoulli.trial(100);
// Expected value: (1 - (1 - 0.01) ** 100) == 0.6339
// 0.6339 * 10000 == 6339
MOZ_RELEASE_ASSERT(count == 6372);
}
{
size_t count = 0;
for (size_t i = 0; i < 10000; i++)
count += bernoulli.trial(1000);
// Expected value: (1 - (1 - 0.01) ** 1000) == 0.9999
// 0.9999 * 10000 == 9999
MOZ_RELEASE_ASSERT(count == 9998);
}
}
static void
TestChangeProbability()
{
mozilla::FastBernoulliTrial bernoulli(1.0,
0x67ff17e25d855942ULL,
0x74f298193fe1c5b1ULL);
// Establish a very high skip count.
bernoulli.setProbability(0.0);
// This should re-establish a zero skip count.
bernoulli.setProbability(1.0);
// So this should return true.
MOZ_RELEASE_ASSERT(bernoulli.trial());
}
static void
TestCuspProbabilities()
{
/*
* FastBernoulliTrial takes care to avoid screwing up on edge cases. The
* checks here all look pretty dumb, but they exercise paths in the code that
* could exhibit undefined behavior if coded naïvely.
*/
/*
* This should not be perceptibly different from 1; for 64-bit doubles, this
* is a one in ten trillion chance of the trial not succeeding. Overflows
* converting doubles to size_t skip counts may change this, though.
*/
mozilla::FastBernoulliTrial bernoulli(nextafter(1, 0),
0x67ff17e25d855942ULL,
0x74f298193fe1c5b1ULL);
for (size_t i = 0; i < 1000; i++)
MOZ_RELEASE_ASSERT(bernoulli.trial());
/*
* This should not be perceptibly different from 0; for 64-bit doubles,
* the FastBernoulliTrial will actually treat this as exactly zero.
*/
bernoulli.setProbability(nextafter(0, 1));
for (size_t i = 0; i < 1000; i++)
MOZ_RELEASE_ASSERT(!bernoulli.trial());
/*
* This should be a vanishingly low probability which FastBernoulliTrial does
* *not* treat as exactly zero.
*/
bernoulli.setProbability(1 - nextafter(1, 0));
for (size_t i = 0; i < 1000; i++)
MOZ_RELEASE_ASSERT(!bernoulli.trial());
}
int
main()
{
TestProportions();
TestHarmonics();
TestTrialN();
TestChangeProbability();
TestCuspProbabilities();
return 0;
}
|
