random/internal/fastmath.h

0001 // Copyright 2017 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_RANDOM_INTERNAL_FASTMATH_H_
0016 #define ABSL_RANDOM_INTERNAL_FASTMATH_H_
0017
0018 // This file contains fast math functions (bitwise ops as well as some others)
0019 // which are implementation details of various absl random number distributions.
0020
0021 #include <cassert>
0022 #include <cmath>
0023 #include <cstdint>
0024
0025 #include "absl/numeric/bits.h"
0026
0027 namespace absl {
0028 ABSL_NAMESPACE_BEGIN
0029 namespace random_internal {
0030
0031 // Compute log2(n) using integer operations.
0032 // While std::log2 is more accurate than std::log(n) / std::log(2), for
0033 // very large numbers--those close to std::numeric_limits<uint64_t>::max() - 2,
0034 // for instance--std::log2 rounds up rather than down, which introduces
0035 // definite skew in the results.
0036 inline int IntLog2Floor(uint64_t n) {
0037   return (n <= 1) ? 0 : (63 - countl_zero(n));
0038 }
0039 inline int IntLog2Ceil(uint64_t n) {
0040   return (n <= 1) ? 0 : (64 - countl_zero(n - 1));
0041 }
0042
0043 inline double StirlingLogFactorial(double n) {
0044   assert(n >= 1);
0045   // Using Stirling's approximation.
0046   constexpr double kLog2PI = 1.83787706640934548356;
0047   const double logn = std::log(n);
0048   const double ninv = 1.0 / static_cast<double>(n);
0049   return n * logn - n + 0.5 * (kLog2PI + logn) + (1.0 / 12.0) * ninv -
0050          (1.0 / 360.0) * ninv * ninv * ninv;
0051 }
0052
0053 }  // namespace random_internal
0054 ABSL_NAMESPACE_END
0055 }  // namespace absl
0056
0057 #endif  // ABSL_RANDOM_INTERNAL_FASTMATH_H_