| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// Double-precision implementation of exp10. |
| 11 | /// |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXP10_DOUBLE_EVAL_H |
| 15 | #define LLVM_LIBC_SRC___SUPPORT_MATH_EXP10_DOUBLE_EVAL_H |
| 16 | |
| 17 | #include "src/__support/CPP/bit.h" |
| 18 | #include "src/__support/FPUtil/FPBits.h" |
| 19 | #include "src/__support/FPUtil/double_double.h" |
| 20 | #include "src/__support/FPUtil/fp_bitwise.h" |
| 21 | #include "src/__support/FPUtil/multiply_add.h" |
| 22 | #include "src/__support/common.h" |
| 23 | #include "src/__support/macros/attributes.h" |
| 24 | #include "src/__support/macros/config.h" |
| 25 | #include "src/__support/macros/optimization.h" |
| 26 | #include "src/__support/macros/properties/cpu_features.h" |
| 27 | |
| 28 | #ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 29 | #include "src/__support/math/exp_double_utils.h" |
| 30 | #else |
| 31 | #include "src/__support/math/exp_utils.h" |
| 32 | #endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 33 | |
| 34 | namespace LIBC_NAMESPACE_DECL { |
| 35 | namespace math { |
| 36 | namespace double_eval { |
| 37 | |
| 38 | // log2(10) = 0x1.a934f0979a371p+1 + 0x1.7f2495fb7fa7bp-52 |
| 39 | LIBC_INLINE_VAR constexpr double LOG2_10_HI = 0x1.a934f0979a371p+1; |
| 40 | |
| 41 | // log(10) = 0x1.26bb1bbb55516p+1 - 0x1.f48ad494ea3e9p-53 |
| 42 | LIBC_INLINE_VAR constexpr DoubleDouble LOG_10_DD = {.lo: -0x1.f48ad494ea3e9p-53, |
| 43 | .hi: 0x1.26bb1bbb55516p+1}; |
| 44 | |
| 45 | #if defined(LIBC_MATH_HAS_SKIP_ACCURATE_PASS) && \ |
| 46 | defined(LIBC_MATH_HAS_SMALL_TABLES) |
| 47 | // Splitting -2^-3 * log10(2) ~ hi + lo with 36-bit-precision hi part so that |
| 48 | // kd * MLOG10_2_EXP2_HI is exact for |kd| < 2^14: |
| 49 | // > a = -2^-3 * log10(2); |
| 50 | // > hi = round(a, 36, RN); // -0x1.34413509f8p-5 |
| 51 | // > lo = round(a - hi, D, RN); // 0x1.80433b83b532ap-47 |
| 52 | LIBC_INLINE_VAR constexpr double MLOG10_2_EXP2_HI = -0x1.34413509f8p-5; |
| 53 | LIBC_INLINE_VAR constexpr double MLOG10_2_EXP2_MID = 0x1.80433b83b532ap-47; |
| 54 | #else |
| 55 | // Splitting -2^-7 * log10(2) ~ hi + lo with 35-bit-precision hi part so that |
| 56 | // kd * MLOG10_2_EXP2_HI is exact for |kd| < 2^18: |
| 57 | // > a = -2^-7 * log10(2); |
| 58 | // > hi = round(a, 35, RN); // -0x1.3441350ap-9 |
| 59 | // > lo = round(a - hi, D, RN); // 0x1.0c0219dc1da99p-46 |
| 60 | LIBC_INLINE_VAR constexpr double MLOG10_2_EXP2_HI = -0x1.3441350ap-9; |
| 61 | LIBC_INLINE_VAR constexpr double MLOG10_2_EXP2_MID = 0x1.0c0219dc1da99p-46; |
| 62 | #endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS && LIBC_MATH_HAS_SMALL_TABLES |
| 63 | |
| 64 | #ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 65 | // Splitting log(10) ~ hi + lo with 12-bit-precision hi part for exact non-FMA |
| 66 | // multiplication without Veltkamp splitting: |
| 67 | // > hi = round(log(10), 12, RN); |
| 68 | // > lo = round(log(10) - hi, D, RN); |
| 69 | LIBC_INLINE_VAR constexpr double LOG_10_HI_12 = 0x1.26cp+1; |
| 70 | LIBC_INLINE_VAR constexpr double LOG_10_LO_12 = |
| 71 | (LOG_10_DD.hi - LOG_10_HI_12) + LOG_10_DD.lo; |
| 72 | |
| 73 | // Fast-path Ziv error bound for exp10: |
| 74 | LIBC_INLINE_VAR constexpr double EXP10_ERR_D = 0x1.8p-64; |
| 75 | |
| 76 | // Exact powers of 10 in double precision: 10^1, 10^2, ..., 10^22. |
| 77 | LIBC_INLINE_VAR constexpr double EXP10_EXACT[22] = { |
| 78 | 0x1.4p+3, // 10^1 |
| 79 | 0x1.9p+6, // 10^2 |
| 80 | 0x1.f4p+9, // 10^3 |
| 81 | 0x1.388p+13, // 10^4 |
| 82 | 0x1.86ap+16, // 10^5 |
| 83 | 0x1.e848p+19, // 10^6 |
| 84 | 0x1.312dp+23, // 10^7 |
| 85 | 0x1.7d784p+26, // 10^8 |
| 86 | 0x1.dcd65p+29, // 10^9 |
| 87 | 0x1.2a05f2p+33, // 10^10 |
| 88 | 0x1.74876e8p+36, // 10^11 |
| 89 | 0x1.d1a94a2p+39, // 10^12 |
| 90 | 0x1.2309ce54p+43, // 10^13 |
| 91 | 0x1.6bcc41e9p+46, // 10^14 |
| 92 | 0x1.c6bf52634p+49, // 10^15 |
| 93 | 0x1.1c37937e08p+53, // 10^16 |
| 94 | 0x1.6345785d8ap+56, // 10^17 |
| 95 | 0x1.bc16d674ec8p+59, // 10^18 |
| 96 | 0x1.158e460913d00p+63, // 10^19 |
| 97 | 0x1.5af1d78b58c40p+66, // 10^20 |
| 98 | 0x1.b1ae4d6e2ef50p+69, // 10^21 |
| 99 | 0x1.0f0cf064dd592p+73, // 10^22 |
| 100 | }; |
| 101 | #endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 102 | |
| 103 | LIBC_ALWAYS_INLINE double exp10(double x) { |
| 104 | using FPBits = fputil::FPBits<double>; |
| 105 | FPBits xbits(x); |
| 106 | |
| 107 | uint64_t x_u = xbits.uintval(); |
| 108 | uint64_t x_abs = xbits.abs().uintval(); |
| 109 | |
| 110 | // Bound constants (with biased exponent and mantissa bits): |
| 111 | // - Tiny bound: 10^x ~ 1 when |x| <= 2^-54 / log(10) |
| 112 | // > round(2^-54 / log(10), D, RD) = 0x1.bcb7b1526e50ep-56 |
| 113 | // > round(2^-54 / log(10), D, RU) = 0x1.bcb7b1526e50fp-56 |
| 114 | constexpr uint64_t TINY_BOUND = 0x3c7b'cb7b'1526'e50fULL; |
| 115 | // - Overflow bound: 10^x overflows when x >= log10(2^1024) |
| 116 | // > round(log10(2^1024), D, RU) = 0x1.34413509f79ffp+8 |
| 117 | constexpr uint64_t OVERFLOW_BOUND = 0x4073'4413'509f'79ffULL; |
| 118 | // -0x1.34413509f79ffp+8: |
| 119 | constexpr uint64_t NEG_OVERFLOW_BOUND = 0xc073'4413'509f'79ffULL; |
| 120 | // - Underflow bound: 10^x underflows to 0 when x <= log10(2^-1075) |
| 121 | // > round(log10(2^-1075), D, RD) = -0x1.439b746e36b53p+8 |
| 122 | constexpr uint64_t UNDERFLOW_BOUND = 0xc074'39b7'46e3'6b53ULL; |
| 123 | |
| 124 | // Normal non-tiny range: TINY_BOUND <= |x| < OVERFLOW_BOUND. |
| 125 | if (LIBC_UNLIKELY(x_abs - TINY_BOUND >= OVERFLOW_BOUND - TINY_BOUND)) { |
| 126 | // Exclude non-underflowing negative inputs in |
| 127 | // (UNDERFLOW_BOUND, NEG_OVERFLOW_BOUND]. |
| 128 | if (LIBC_LIKELY(x_u < NEG_OVERFLOW_BOUND || x_u >= UNDERFLOW_BOUND)) |
| 129 | return set_exceptional(x); |
| 130 | } |
| 131 | |
| 132 | #ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 133 | // Exact outputs when x = 1, 2, ..., 22 (must not raise FE_INEXACT). |
| 134 | // 0x3ff0 = high 16 bits of 0x1.0p+0 (1.0) |
| 135 | // 0x4036 = high 16 bits of 0x1.6p+4 (22.0) |
| 136 | if (LIBC_UNLIKELY((x_u << 16) == 0ULL)) { |
| 137 | uint32_t d = static_cast<uint32_t>(x_u >> 48) - 0x3ff0U; |
| 138 | if (d <= 0x46U) { |
| 139 | uint32_t scaled = (16U | (d & 0xfU)) << (d >> 4); |
| 140 | if ((scaled & 0xfU) == 0U) |
| 141 | return EXP10_EXACT[(scaled >> 4) - 1]; |
| 142 | } |
| 143 | } |
| 144 | #endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 145 | |
| 146 | // Now -0x1.439b746e36b53p+8 < x < -0x1.bcb7b1526e50ep-56 or |
| 147 | // 0x1.bcb7b1526e50ep-56 < x < 0x1.34413509f79ffp+8. |
| 148 | |
| 149 | // Range reduction: |
| 150 | // Let x = k * (log10(2) / 2^N) + dx |
| 151 | // in which: |
| 152 | // k = round(x * 2^N * log2(10)) |
| 153 | // hi = k >> N |
| 154 | // idx = k & (2^N - 1) |
| 155 | // then: |
| 156 | // 10^x = 2^hi * 2^(idx / 2^N) * exp(dx * log(10)). |
| 157 | // |
| 158 | // Using ROUND_BIAS, ROUND_SHIFT, and ROUND_MASK (see exp_utils.h), we compute |
| 159 | // k_biased = fma(x, LOG2_10_SCALE, ROUND_BIAS) and extract in parallel: |
| 160 | // kd = (k_biased & ROUND_MASK) - ROUND_SHIFT |
| 161 | // hi = (int32_t)(k_bits >> 19) >> (13 + N) |
| 162 | // idx = (k_bits >> 32) & (2^N - 1). |
| 163 | constexpr double LOG2_10_SCALE = EXP_SCALE * LOG2_10_HI; |
| 164 | |
| 165 | double k_biased = fputil::multiply_add(x, y: LOG2_10_SCALE, z: ROUND_BIAS); |
| 166 | double kd = fputil::fp_and(a: k_biased, b: ROUND_MASK) - ROUND_SHIFT; |
| 167 | uint64_t k_bits = cpp::bit_cast<uint64_t>(from: k_biased); |
| 168 | |
| 169 | int hi = static_cast<int32_t>(k_bits >> 19) >> (13 + EXP_N_BITS); |
| 170 | unsigned idx = static_cast<unsigned>(k_bits >> 32) & EXP_MASK; |
| 171 | |
| 172 | #ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 173 | double t1 = fputil::multiply_add(kd, MLOG10_2_EXP2_HI, x); // exact |
| 174 | double dx = fputil::multiply_add(kd, MLOG10_2_EXP2_MID, t1); |
| 175 | double u = dx * LOG_10_DD.hi; |
| 176 | return exp2_eval(x, u, hi, idx); |
| 177 | #else // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 178 | #ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 179 | // With FMA, we use the full 53-bit: |
| 180 | // MLOG10_2_HI_53 = -2^-7 * log10(2) = -0x1.34413509f79ffp-9 (lsb = 2^-61) |
| 181 | // and pre-multiplied remainder: |
| 182 | // MLOG10_2_MID_53_LOG10 = (-2^-7 * log10(2) - MLOG10_2_HI_53) * log(10) |
| 183 | // = 0x1.dc5b0a78f8364p-65 |
| 184 | // to compute: |
| 185 | // u = (x - k * 2^-7 * log10(2)) * log(10) ~ t1 * log(10) + corr |
| 186 | // where: |
| 187 | // t1 = fma(kd, MLOG10_2_HI_53, x) (exact for k != 0) |
| 188 | // corr = kd * MLOG10_2_MID_53_LOG10 (|corr| < 2^18 * 2^-64 = 2^-46). |
| 189 | // |
| 190 | // Writing: |
| 191 | // exp(u.hi + d) = exp(u.hi) * exp(d) |
| 192 | // ~ (1 + u.hi + u.hi^2 * P(u.hi)) * (1 + d), |
| 193 | // we fold the linear cross-term u.hi * corr into u.lo. |
| 194 | constexpr double MLOG10_2_HI_53 = -0x1.34413509f79ffp-2 * EXP_SCALE_INV; |
| 195 | constexpr double MLOG10_2_MID_53_LOG10 = |
| 196 | 0x1.dc5b0a78f8364p-58 * EXP_SCALE_INV; |
| 197 | |
| 198 | double t1 = fputil::multiply_add(kd, MLOG10_2_HI_53, x); // exact |
| 199 | double corr = kd * MLOG10_2_MID_53_LOG10; |
| 200 | DoubleDouble u = fputil::exact_mult(t1, LOG_10_DD.hi); |
| 201 | double lo1 = fputil::multiply_add(t1, LOG_10_DD.lo, corr); |
| 202 | double lo2 = fputil::multiply_add(u.hi, corr, lo1); |
| 203 | u.lo += lo2; |
| 204 | return exp2_eval(x, u, hi, idx, EXP10_ERR_D, &LOG2_10_192); |
| 205 | #else // !LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 206 | // Without FMA, we use a 35-bit-precision high part MLOG10_2_EXP2_HI (with |
| 207 | // lsb = 2^-43) so that: |
| 208 | // dx1 = x + kd * MLOG10_2_EXP2_HI |
| 209 | // is exact for |kd| < 2^18. |
| 210 | // |
| 211 | // We then split dx1 at 2^-18 before multiplying by the 12-bit LOG_10_HI_12 |
| 212 | // (with lsb = 2^-10): |
| 213 | // dx_hi = (dx1 + SPLIT_18) - SPLIT_18 (exact, lsb = 2^-18) |
| 214 | // dx_lo = (dx1 - dx_hi) + dx2 (|dx_lo| < 2^-18) |
| 215 | // u_hi = dx_hi * LOG_10_HI_12 (exact, lsb = 2^-28 >= 2^-30) |
| 216 | // u_lo = dx_lo * LOG_10_HI_12 + dx_sum * LOG_10_LO_12. |
| 217 | double dx1 = fputil::multiply_add(x: kd, y: MLOG10_2_EXP2_HI, z: x); // exact |
| 218 | double dx2 = kd * MLOG10_2_EXP2_MID; |
| 219 | double dx_sum = dx1 + dx2; |
| 220 | double dx_hi = (dx1 + SPLIT_18) - SPLIT_18; |
| 221 | double dx_lo = (dx1 - dx_hi) + dx2; |
| 222 | double u_hi = dx_hi * LOG_10_HI_12; // exact, lsb = 2^-28 >= 2^-30 |
| 223 | double u_lo = dx_lo * LOG_10_HI_12 + dx_sum * LOG_10_LO_12; |
| 224 | return exp2_eval(x, u: {.lo: u_lo, .hi: u_hi}, hi, idx, err_d: EXP10_ERR_D, log2_base: &LOG2_10_192); |
| 225 | #endif // LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 226 | #endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 227 | } |
| 228 | |
| 229 | } // namespace double_eval |
| 230 | } // namespace math |
| 231 | } // namespace LIBC_NAMESPACE_DECL |
| 232 | |
| 233 | #endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXP10_DOUBLE_EVAL_H |
| 234 | |