tor-browser

TestFastBernoulliTrial.cpp (5436B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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;
}