arrow/testing/uniform_real.h

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017
0018 // Random real generation is very slow on Arm if built with clang + libstdc++
0019 // due to software emulated long double arithmetic.
0020 // This file ports some random real libs from llvm libc++ library, which are
0021 // free from long double calculation.
0022 // It improves performance significantly on both Arm (~100x) and x86 (~8x) in
0023 // generating random reals when built with clang + gnu libstdc++.
0024 // Based on: https://github.com/llvm/llvm-project/tree/main/libcxx
0025
0026 #pragma once
0027
0028 #include <limits>
0029
0030 #include <arrow/util/bit_util.h>
0031
0032 namespace arrow {
0033 namespace random {
0034
0035 namespace detail {
0036
0037 // std::generate_canonical, simplified
0038 // https://en.cppreference.com/w/cpp/numeric/random/generate_canonical
0039 template <typename RealType, typename Rng>
0040 RealType generate_canonical(Rng& rng) {
0041   const size_t b = std::numeric_limits<RealType>::digits;
0042   const size_t log2R = 63 - ::arrow::bit_util::CountLeadingZeros(
0043                                 static_cast<uint64_t>(Rng::max() - Rng::min()) + 1);
0044   const size_t k = b / log2R + (b % log2R != 0) + (b == 0);
0045   const RealType r = static_cast<RealType>(Rng::max() - Rng::min()) + 1;
0046   RealType base = r;
0047   RealType sp = static_cast<RealType>(rng() - Rng::min());
0048   for (size_t i = 1; i < k; ++i, base *= r) {
0049     sp += (rng() - Rng::min()) * base;
0050   }
0051   return sp / base;
0052 }
0053
0054 }  // namespace detail
0055
0056 // std::uniform_real_distribution, simplified
0057 // https://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution
0058 template <typename RealType = double>
0059 struct uniform_real_distribution {
0060   const RealType a, b;
0061
0062   explicit uniform_real_distribution(RealType a = 0, RealType b = 1) : a(a), b(b) {}
0063
0064   template <typename Rng>
0065   RealType operator()(Rng& rng) {
0066     return (b - a) * detail::generate_canonical<RealType>(rng) + a;
0067   }
0068 };
0069
0070 // std::bernoulli_distribution, simplified
0071 // https://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution
0072 struct bernoulli_distribution {
0073   const double p;
0074
0075   explicit bernoulli_distribution(double p = 0.5) : p(p) {}
0076
0077   template <class Rng>
0078   bool operator()(Rng& rng) {
0079     return detail::generate_canonical<double>(rng) < p;
0080   }
0081 };
0082
0083 }  // namespace random
0084 }  // namespace arrow