Line data    Source code

       1             : /*
       2             :  *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
       3             :  *
       4             :  *  Use of this source code is governed by a BSD-style license
       5             :  *  that can be found in the LICENSE file in the root of the source
       6             :  *  tree. An additional intellectual property rights grant can be found
       7             :  *  in the file PATENTS.  All contributing project authors may
       8             :  *  be found in the AUTHORS file in the root of the source tree.
       9             :  */
      10             : #include "webrtc/base/random.h"
      11             : 
      12             : #include <math.h>
      13             : 
      14             : #include "webrtc/base/checks.h"
      15             : 
      16             : namespace webrtc {
      17             : 
      18           0 : Random::Random(uint64_t seed) {
      19           0 :   RTC_DCHECK(seed != 0x0ull);
      20           0 :   state_ = seed;
      21           0 : }
      22             : 
      23           0 : uint32_t Random::Rand(uint32_t t) {
      24             :   // Casting the output to 32 bits will give an almost uniform number.
      25             :   // Pr[x=0] = (2^32-1) / (2^64-1)
      26             :   // Pr[x=k] = 2^32 / (2^64-1) for k!=0
      27             :   // Uniform would be Pr[x=k] = 2^32 / 2^64 for all 32-bit integers k.
      28           0 :   uint32_t x = NextOutput();
      29             :   // If x / 2^32 is uniform on [0,1), then x / 2^32 * (t+1) is uniform on
      30             :   // the interval [0,t+1), so the integer part is uniform on [0,t].
      31           0 :   uint64_t result = x * (static_cast<uint64_t>(t) + 1);
      32           0 :   result >>= 32;
      33           0 :   return result;
      34             : }
      35             : 
      36           0 : uint32_t Random::Rand(uint32_t low, uint32_t high) {
      37           0 :   RTC_DCHECK(low <= high);
      38           0 :   return Rand(high - low) + low;
      39             : }
      40             : 
      41           0 : int32_t Random::Rand(int32_t low, int32_t high) {
      42           0 :   RTC_DCHECK(low <= high);
      43             :   // We rely on subtraction (and addition) to be the same for signed and
      44             :   // unsigned numbers in two-complement representation. Thus, although
      45             :   // high - low might be negative as an int, it is the correct difference
      46             :   // when interpreted as an unsigned.
      47           0 :   return Rand(high - low) + low;
      48             : }
      49             : 
      50             : template <>
      51           0 : float Random::Rand<float>() {
      52           0 :   double result = NextOutput() - 1;
      53           0 :   result = result / 0xFFFFFFFFFFFFFFFEull;
      54           0 :   return static_cast<float>(result);
      55             : }
      56             : 
      57             : template <>
      58           0 : double Random::Rand<double>() {
      59           0 :   double result = NextOutput() - 1;
      60           0 :   result = result / 0xFFFFFFFFFFFFFFFEull;
      61           0 :   return result;
      62             : }
      63             : 
      64             : template <>
      65           0 : bool Random::Rand<bool>() {
      66           0 :   return Rand(0, 1) == 1;
      67             : }
      68             : 
      69           0 : double Random::Gaussian(double mean, double standard_deviation) {
      70             :   // Creating a Normal distribution variable from two independent uniform
      71             :   // variables based on the Box-Muller transform, which is defined on the
      72             :   // interval (0, 1]. Note that we rely on NextOutput to generate integers
      73             :   // in the range [1, 2^64-1]. Normally this behavior is a bit frustrating,
      74             :   // but here it is exactly what we need.
      75           0 :   const double kPi = 3.14159265358979323846;
      76           0 :   double u1 = static_cast<double>(NextOutput()) / 0xFFFFFFFFFFFFFFFFull;
      77           0 :   double u2 = static_cast<double>(NextOutput()) / 0xFFFFFFFFFFFFFFFFull;
      78           0 :   return mean + standard_deviation * sqrt(-2 * log(u1)) * cos(2 * kPi * u2);
      79             : }
      80             : 
      81           0 : double Random::Exponential(double lambda) {
      82           0 :   double uniform = Rand<double>();
      83           0 :   return -log(uniform) / lambda;
      84             : }
      85             : 
      86             : }  // namespace webrtc