fastmath_test.cc (3267B)
1 // Copyright 2017 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/random/internal/fastmath.h" 16 17 #include "gtest/gtest.h" 18 19 #if defined(__native_client__) || defined(__EMSCRIPTEN__) 20 // NACL has a less accurate implementation of std::log2 than most of 21 // the other platforms. For some values which should have integral results, 22 // sometimes NACL returns slightly larger values. 23 // 24 // The MUSL libc used by emscripten also has a similar bug. 25 #define ABSL_RANDOM_INACCURATE_LOG2 26 #endif 27 28 namespace { 29 30 TEST(FastMathTest, IntLog2FloorTest) { 31 using absl::random_internal::IntLog2Floor; 32 constexpr uint64_t kZero = 0; 33 EXPECT_EQ(0, IntLog2Floor(0)); // boundary. return 0. 34 EXPECT_EQ(0, IntLog2Floor(1)); 35 EXPECT_EQ(1, IntLog2Floor(2)); 36 EXPECT_EQ(63, IntLog2Floor(~kZero)); 37 38 // A boundary case: Converting 0xffffffffffffffff requires > 53 39 // bits of precision, so the conversion to double rounds up, 40 // and the result of std::log2(x) > IntLog2Floor(x). 41 EXPECT_LT(IntLog2Floor(~kZero), static_cast<int>(std::log2(~kZero))); 42 43 for (int i = 0; i < 64; i++) { 44 const uint64_t i_pow_2 = static_cast<uint64_t>(1) << i; 45 EXPECT_EQ(i, IntLog2Floor(i_pow_2)); 46 EXPECT_EQ(i, static_cast<int>(std::log2(i_pow_2))); 47 48 uint64_t y = i_pow_2; 49 for (int j = i - 1; j > 0; --j) { 50 y = y | (i_pow_2 >> j); 51 EXPECT_EQ(i, IntLog2Floor(y)); 52 } 53 } 54 } 55 56 TEST(FastMathTest, IntLog2CeilTest) { 57 using absl::random_internal::IntLog2Ceil; 58 constexpr uint64_t kZero = 0; 59 EXPECT_EQ(0, IntLog2Ceil(0)); // boundary. return 0. 60 EXPECT_EQ(0, IntLog2Ceil(1)); 61 EXPECT_EQ(1, IntLog2Ceil(2)); 62 EXPECT_EQ(64, IntLog2Ceil(~kZero)); 63 64 // A boundary case: Converting 0xffffffffffffffff requires > 53 65 // bits of precision, so the conversion to double rounds up, 66 // and the result of std::log2(x) > IntLog2Floor(x). 67 EXPECT_LE(IntLog2Ceil(~kZero), static_cast<int>(std::log2(~kZero))); 68 69 for (int i = 0; i < 64; i++) { 70 const uint64_t i_pow_2 = static_cast<uint64_t>(1) << i; 71 EXPECT_EQ(i, IntLog2Ceil(i_pow_2)); 72 #ifndef ABSL_RANDOM_INACCURATE_LOG2 73 EXPECT_EQ(i, static_cast<int>(std::ceil(std::log2(i_pow_2)))); 74 #endif 75 76 uint64_t y = i_pow_2; 77 for (int j = i - 1; j > 0; --j) { 78 y = y | (i_pow_2 >> j); 79 EXPECT_EQ(i + 1, IntLog2Ceil(y)); 80 } 81 } 82 } 83 84 TEST(FastMathTest, StirlingLogFactorial) { 85 using absl::random_internal::StirlingLogFactorial; 86 87 EXPECT_NEAR(StirlingLogFactorial(1.0), 0, 1e-3); 88 EXPECT_NEAR(StirlingLogFactorial(1.50), 0.284683, 1e-3); 89 EXPECT_NEAR(StirlingLogFactorial(2.0), 0.69314718056, 1e-4); 90 91 for (int i = 2; i < 50; i++) { 92 double d = static_cast<double>(i); 93 EXPECT_NEAR(StirlingLogFactorial(d), std::lgamma(d + 1), 3e-5); 94 } 95 } 96 97 } // namespace