| 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 | /// Shared utilities and tables for double-precision exponential functions. |
| 11 | /// |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXP_UTILS_H |
| 15 | #define LLVM_LIBC_SRC___SUPPORT_MATH_EXP_UTILS_H |
| 16 | |
| 17 | #include "hdr/errno_macros.h" |
| 18 | #include "src/__support/CPP/bit.h" |
| 19 | #include "src/__support/CPP/optional.h" |
| 20 | #include "src/__support/FPUtil/FEnvImpl.h" |
| 21 | #include "src/__support/FPUtil/FPBits.h" |
| 22 | #include "src/__support/FPUtil/double_double.h" |
| 23 | #include "src/__support/FPUtil/except_value_utils.h" |
| 24 | #include "src/__support/FPUtil/fp_bitwise.h" |
| 25 | #include "src/__support/FPUtil/multiply_add.h" |
| 26 | #include "src/__support/FPUtil/polyeval.h" |
| 27 | #include "src/__support/macros/attributes.h" |
| 28 | #include "src/__support/macros/config.h" |
| 29 | #include "src/__support/macros/optimization.h" |
| 30 | #include "src/__support/macros/properties/cpu_features.h" |
| 31 | |
| 32 | #ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 33 | #include "src/__support/math/exp2_accurate_128.h" |
| 34 | #endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 35 | |
| 36 | namespace LIBC_NAMESPACE_DECL { |
| 37 | |
| 38 | // Rounding tests for 2^hi * (mid + lo) when the output might be denormal. We |
| 39 | // assume further that 1 <= mid < 2, mid + lo < 2, and |lo| << mid. |
| 40 | // Notice that, if 0 < x < 2^-1022, |
| 41 | // double(2^-1022 + x) - 2^-1022 = double(x). |
| 42 | // So if we scale x up by 2^1022, we can use |
| 43 | // double(1.0 + 2^1022 * x) - 1.0 to test how x is rounded in denormal range. |
| 44 | template <bool SKIP_ZIV_TEST = false> |
| 45 | LIBC_INLINE constexpr cpp::optional<double> |
| 46 | ziv_test_denorm(int hi, double mid, double lo, double err) { |
| 47 | // Scaling factor = 1/(min normal number) = 2^1022 |
| 48 | int scale_up = hi + 1022; |
| 49 | double mid_hi = fputil::scale_exp2(r: mid, hi: scale_up); |
| 50 | double lo_scaled = (lo != 0.0) ? fputil::scale_exp2(r: lo, hi: scale_up) : 0.0; |
| 51 | |
| 52 | double = 0.0; |
| 53 | int scale_down = -1022; |
| 54 | |
| 55 | // Result is denormal if (mid_hi + lo_scale < 1.0). |
| 56 | if ((1.0 - mid_hi) > lo_scaled) { |
| 57 | // Extra rounding step is needed, which adds more rounding errors. |
| 58 | err += 0x1.0p-52; |
| 59 | extra_factor = 1.0; |
| 60 | scale_down = -1023; |
| 61 | } |
| 62 | |
| 63 | // By adding 1.0, the results will have similar rounding points as denormal |
| 64 | // outputs. |
| 65 | if constexpr (SKIP_ZIV_TEST) { |
| 66 | double r = extra_factor + (mid_hi + lo_scaled); |
| 67 | return fputil::scale_exp2(r, hi: scale_down); |
| 68 | } else { |
| 69 | double err_scaled = fputil::scale_exp2(r: err, hi: scale_up); |
| 70 | |
| 71 | double lo_u = lo_scaled + err_scaled; |
| 72 | double lo_l = lo_scaled - err_scaled; |
| 73 | |
| 74 | double upper = extra_factor + (mid_hi + lo_u); |
| 75 | double lower = extra_factor + (mid_hi + lo_l); |
| 76 | |
| 77 | if (LIBC_LIKELY(upper == lower)) |
| 78 | return fputil::scale_exp2(r: upper, hi: scale_down); |
| 79 | |
| 80 | return cpp::nullopt; |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | namespace math { |
| 85 | namespace double_eval { |
| 86 | |
| 87 | using fputil::DoubleDouble; |
| 88 | using fputil::scale_exp2; |
| 89 | |
| 90 | // log(2) in double-double precision, generated by Sollya with: |
| 91 | // > display = hexadecimal!; |
| 92 | // > prec = 500; |
| 93 | // > hi = round(log(2), D, RN); |
| 94 | // > lo = round(log(2) - hi, D, RN); |
| 95 | // > print("{", lo, ",", hi, "};"); |
| 96 | LIBC_INLINE_VAR constexpr DoubleDouble LOG_2_DD = {.lo: 0x1.abc9e3b39803fp-56, |
| 97 | .hi: 0x1.62e42fefa39efp-1}; |
| 98 | |
| 99 | // log2(e) in double-double precision, generated by Sollya with: |
| 100 | // > display = hexadecimal!; |
| 101 | // > prec = 500; |
| 102 | // > hi = round(log2(exp(1)), D, RN); |
| 103 | // > lo = round(log2(exp(1)) - hi, D, RN); |
| 104 | // > print("{", lo, ",", hi, "};"); |
| 105 | LIBC_INLINE_VAR constexpr DoubleDouble LOG2_E_DD = {.lo: 0x1.777d0ffda0d24p-56, |
| 106 | .hi: 0x1.71547652b82fep+0}; |
| 107 | |
| 108 | // Check for exceptional cases (tiny, overflow, underflow, inf, or nan) for |
| 109 | // exp, exp2, and exp10. Callers have already verified that x is in the exact |
| 110 | // tiny, underflow, or overflow/inf/nan range for the specific function before |
| 111 | // calling this helper. |
| 112 | LIBC_NOINLINE LIBC_INLINE double set_exceptional(double x) { |
| 113 | using FPBits = fputil::FPBits<double>; |
| 114 | FPBits xbits(x); |
| 115 | |
| 116 | // |x| <= 0x1.0p-53 (caller has already checked the exact tiny bound): |
| 117 | constexpr uint64_t TINY_BOUND = 0x3ca0'0000'0000'0000ULL; |
| 118 | if (xbits.abs().uintval() <= TINY_BOUND) { |
| 119 | // b^x ~ 1 + x |
| 120 | return 1.0 + x; |
| 121 | } |
| 122 | |
| 123 | // Negative underflow or -inf/nan (caller has already excluded |
| 124 | // non-underflowing negative inputs): |
| 125 | if (xbits.is_neg()) { |
| 126 | // b^(-Inf) = 0 |
| 127 | if (xbits.is_inf()) |
| 128 | return 0.0; |
| 129 | |
| 130 | // b^(nan) = nan |
| 131 | // Adding 0.0 to silence signaling nan. |
| 132 | if (xbits.is_nan()) |
| 133 | return x + 0.0; |
| 134 | |
| 135 | return fputil::set_underflow<double>(); |
| 136 | } |
| 137 | |
| 138 | // Positive overflow or +inf/nan (caller has already checked the exact |
| 139 | // overflow bound) |
| 140 | |
| 141 | // x is finite and positive |
| 142 | if (xbits.uintval() < FPBits::inf().uintval()) |
| 143 | return fputil::set_overflow<double>(); |
| 144 | |
| 145 | // x is +inf or nan |
| 146 | // Adding `inf` to silence signaling nan. |
| 147 | return x + FPBits::inf().get_val(); |
| 148 | } |
| 149 | |
| 150 | // Fast range-reduction rounding constants for exp, exp2, sinh, and cosh: |
| 151 | // |
| 152 | // Instead of calling fputil::nearest_integer(x * SCALE) and |
| 153 | // static_cast<int>(kd) (which has a serial dependency chain: |
| 154 | // multiply -> roundsd/frintn -> cvttsd2si/fcvtzs), |
| 155 | // we fuse the scaling and rounding bias into a single FMA: |
| 156 | // k_biased = fma(x, SCALE, ROUND_BIAS). |
| 157 | // |
| 158 | // Derivation of ROUND_SHIFT, ROUND_BIAS, and ROUND_MASK: |
| 159 | // 1) Why we cannot use 1.5 * 2^52: |
| 160 | // Adding 1.5 * 2^52 (ulp = 1) relies on the hardware FMA rounding mode to |
| 161 | // round z = x * SCALE to an integer. In directed rounding modes |
| 162 | // (FE_DOWNWARD, FE_UPWARD, FE_TOWARDZERO), that rounds toward -inf/+inf/0 |
| 163 | // instead of nearest, doubling the reduced argument |u| from <= 0.5 * 2^-N |
| 164 | // to <= 2^-N. |
| 165 | // To round to nearest in all rounding modes, we keep F = 52 - M > 0 |
| 166 | // fractional bits in the 52-bit mantissa using: |
| 167 | // ROUND_SHIFT = 1.5 * 2^M, |
| 168 | // add +0.5 explicitly in ROUND_BIAS, and mask out the F fractional bits. |
| 169 | // |
| 170 | // 2) Choosing M = 20 (20 integer bits + 32 fractional bits): |
| 171 | // For all non-overflowing/non-underflowing inputs of exp, exp2, sinh, and |
| 172 | // cosh, the scaled input z = x * SCALE satisfies |z| < 2^18. To keep |
| 173 | // z + 1.5 * 2^M inside the single binade: |
| 174 | // [1.25 * 2^M, 1.75 * 2^M) subset [2^M, 2^(M + 1)) |
| 175 | // without carrying across 2^M, we need 2^18 <= 2^(M - 2), i.e., M >= 20. |
| 176 | // Choosing the minimum M = 20 maximizes the fractional precision at |
| 177 | // F = 52 - 20 = 32 fractional bits and aligns the binary point of k right |
| 178 | // at the 32-bit word boundary (bit 32): |
| 179 | // ROUND_SHIFT = 1.5 * 2^20 = 0x1.8p+20, ulp = 2^(20 - 52) = 2^-32. |
| 180 | // In k_biased = z + ROUND_BIAS: |
| 181 | // - The low 32 bits [31:0] hold the 32 fractional bits in [0, 1). |
| 182 | // - Bits [50:32] hold the 19-bit signed two's-complement integer k (with |
| 183 | // |k| < 2^18 and sign bit at bit 50). |
| 184 | // |
| 185 | // 3) Deriving the bias (+0.5 + 2^-32): |
| 186 | // Masking out the low 32 fractional bits with: |
| 187 | // ROUND_MASK = 0xffff'ffff'0000'0000 |
| 188 | // truncates toward -inf (floor). Adding +0.5 turns floor into nearest: |
| 189 | // floor(z + 0.5) = round(z). |
| 190 | // However, the FMA rounds z + ROUND_BIAS at ulp = 2^-32 before the mask. |
| 191 | // With only +0.5, a tiny negative input (-2^-32 < z < 0) in FE_DOWNWARD or |
| 192 | // FE_TOWARDZERO would round z + (1.5 * 2^20 + 0.5) down by 1 ULP to: |
| 193 | // 1.5 * 2^20 + 0.5 - 2^-32, |
| 194 | // which truncates to k = -1 instead of k = 0. |
| 195 | // Adding +2^-32 (1 ULP at 2^20, i.e., mantissa bit 0) gives: |
| 196 | // ROUND_BIAS = 1.5 * 2^20 + 0.5 + 2^-32 = 0x1.8000080000001p+20, |
| 197 | // ensuring k_biased >= 1.5 * 2^20 (so k = 0 and kd = 0.0) for all |
| 198 | // |x| < 2^-9 across all rounding modes. |
| 199 | // |
| 200 | // 4) Note on rounding errors: |
| 201 | // Rounding the FMA at ulp(k_biased) = 2^-32 before truncating the 32 |
| 202 | // fractional bits gives: |
| 203 | // k = floor(z + 0.5 + 2^-32 + delta), |delta| < 2^-32. |
| 204 | // Since k (extracted from bits [50:32]) and: |
| 205 | // kd = (k_biased & ROUND_MASK) - ROUND_SHIFT |
| 206 | // are still equal integers, the range-reduction identity remains exact; the |
| 207 | // extra rounding error only shifts the half-integer rounding boundary by at |
| 208 | // most 2^-31, widening the reduced argument |u| by at most a factor of |
| 209 | // (1 + 2^-30) and increasing the polynomial approximation error by < 2^-90. |
| 210 | LIBC_INLINE_VAR constexpr double ROUND_BIAS = 0x1.8000080000001p+20; |
| 211 | LIBC_INLINE_VAR constexpr double ROUND_SHIFT = 0x1.8p+20; |
| 212 | LIBC_BIT_CAST_CONSTEXPR_VAR double ROUND_MASK = |
| 213 | cpp::bit_cast<double>(from: 0xffff'ffff'0000'0000ULL); |
| 214 | |
| 215 | #if !defined(LIBC_MATH_HAS_SKIP_ACCURATE_PASS) || \ |
| 216 | !defined(LIBC_MATH_HAS_SMALL_TABLES) |
| 217 | |
| 218 | LIBC_INLINE_VAR constexpr int EXP_N_BITS = 7; |
| 219 | LIBC_INLINE_VAR constexpr double EXP_SCALE = 128.0; // 2^EXP_N_BITS = 2^7 |
| 220 | LIBC_INLINE_VAR constexpr double EXP_SCALE_INV = 0x1.0p-7; |
| 221 | LIBC_INLINE_VAR constexpr int EXP_MASK = 0x7f; |
| 222 | |
| 223 | // Polynomial approximation for (exp(x) - 1 - x) / x^2 on |
| 224 | // [-B, B] with B = 2^-8 * log(2): |
| 225 | // |
| 226 | // 1) A degree-3 minimax polynomial P0 for (exp(x) - 1 - x) / x^2 on [-B, B] |
| 227 | // (which minimizes the error of exp(x) - (1 + x + x^2 * P0(x)) weighted by |
| 228 | // 1 / x^2, i.e., relative error with respect to x^2): |
| 229 | // > display = hexadecimal!; |
| 230 | // > prec = 500; |
| 231 | // > B = 2^(-8) * log(2); |
| 232 | // > P0 = fpminimax((exp(x) - 1 - x)/x^2, 3, [|D...|], [-B, B]); |
| 233 | // > dirtyinfnorm(exp(x) - (1 + x + x^2 * P0), [-B, B]); |
| 234 | // 0x1.4362...p-64 < 2^-63. |
| 235 | // |
| 236 | // Some explanation for the errors (from Chebyshev polynomials): |
| 237 | // Because P0 minimizes |(exp(x) - 1 - x) / x^2 - P0(x)|, its error is governed |
| 238 | // by the degree-4 Chebyshev polynomial: |
| 239 | // T_4(x / B) = 8*(x / B)^4 - 8*(x / B)^2 + 1 |
| 240 | // approximating the leading omitted Taylor term x^4 / 720, with magnitude: |
| 241 | // B^4 / (720 * 8). |
| 242 | // Multiplying by x^2 gives an absolute error of: |
| 243 | // x^2 * B^4 / (720 * 8) * T_4(x / B), |
| 244 | // peaking at x = +-B with: |
| 245 | // B^6 / (720 * 8) ~ 0x1.4309...p-64 < 2^-63. |
| 246 | // |
| 247 | // 2) If we instead minimize the absolute error of exp(x) - (1 + x + P(x)) |
| 248 | // directly on [-B, B] with monomials [|2, 3, 4, 5|]: |
| 249 | // > P = fpminimax(exp(x) - 1 - x, [|2, 3, 4, 5|], [|D...|], [-B, B], |
| 250 | // absolute); |
| 251 | // > dirtyinfnorm(exp(x) - (1 + x + P), [-B, B]); |
| 252 | // 0x1.8e05...p-66 < 2^-65. |
| 253 | // |
| 254 | // Some explanation for the better errors from Chebyshev polynomials: |
| 255 | // The free x^2 and x^4 coefficients in P(x) approximate the omitted x^6 / 720 |
| 256 | // term on [-B, B] subject to vanishing at x = 0. Setting t = (x / B)^2 in |
| 257 | // [0, 1], this is equivalent to approximating t^3 on [0, 1] by: |
| 258 | // a_2 * t^2 + a_1 * t |
| 259 | // vanishing at t = 0. |
| 260 | // The degree-3 Chebyshev polynomial: |
| 261 | // T_3(z) = 4*z^3 - 3*z |
| 262 | // has a root at z = -sqrt(3)/2 and three alternating extrema +-1 on |
| 263 | // [-sqrt(3)/2, 1] at z = -1/2, 1/2, 1. |
| 264 | // Mapping t in [0, 1] affinely onto z in [-sqrt(3)/2, 1] via: |
| 265 | // z = ((2 + sqrt(3)) / 2) * t - sqrt(3) / 2 |
| 266 | // gives an error curve T_3(z) that vanishes at t = 0 and equioscillates three |
| 267 | // times on (0, 1], with leading coefficient: |
| 268 | // 4 * ((2 + sqrt(3)) / 2)^3 = (2 + sqrt(3))^3 / 2. |
| 269 | // Dividing by this leading coefficient gives a maximum error on [-B, B] of: |
| 270 | // (2 / (2 + sqrt(3))^3) * B^6 / 720 = 2 * (2 - sqrt(3))^3 * B^6 / 720 |
| 271 | // ~ 0x1.8dba...p-66 < 2^-65, |
| 272 | // reducing the maximum error compared to P0 by: |
| 273 | // (2 + sqrt(3))^3 / 16 > 3x. |
| 274 | LIBC_INLINE_VAR constexpr double EXP_P_COEFFS[4] = { |
| 275 | 0x1.ffffffffffdbdp-2, // p_0 |
| 276 | 0x1.555555555543dp-3, // p_1 |
| 277 | 0x1.55555cf16d6eep-5, // p_2 |
| 278 | 0x1.111116782220ap-7, // p_3 |
| 279 | }; |
| 280 | |
| 281 | // Splitting -2^-7 * log(2) ~ hi + lo with 35-bit-precision hi part so that |
| 282 | // kd * MLOG_2_EXP2_HI is exact for |kd| < 2^18: |
| 283 | // > hi = round(-2^-7 * log(2), 35, RN); |
| 284 | // > lo = round(-2^-7 * log(2) - hi, D, RN); |
| 285 | LIBC_INLINE_VAR constexpr double MLOG_2_EXP2_HI = -0x1.62e42fefcp-8; |
| 286 | LIBC_INLINE_VAR constexpr double MLOG_2_EXP2_MID = 0x1.c610ca86c3899p-44; |
| 287 | |
| 288 | #endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS || !LIBC_MATH_HAS_SMALL_TABLES |
| 289 | |
| 290 | #ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 291 | |
| 292 | // Fixed-point splitting constants (ulp = 2^-18, 2^-30) and pre-split |
| 293 | // 12-bit + 53-bit logarithm constants for exact non-FMA multiplication without |
| 294 | // Veltkamp splitting: |
| 295 | LIBC_INLINE_VAR constexpr double SPLIT_18 = 0x1.8p34; // 1.5 * 2^(-18 + 52) |
| 296 | LIBC_INLINE_VAR constexpr double SPLIT_30 = 0x1.8p22; // 1.5 * 2^(-30 + 52) |
| 297 | |
| 298 | // Splitting log(2) ~ hi + lo with 12-bit-precision hi part. |
| 299 | // > hi = round(log(2), 12, RN); |
| 300 | // > lo = round(log(2) - hi, D, RN); |
| 301 | LIBC_INLINE_VAR constexpr double LOG_2_HI_12 = 0x1.62ep-1; |
| 302 | LIBC_INLINE_VAR constexpr double LOG_2_LO_12 = 0x1.0bfbe8e7bcd5ep-15; |
| 303 | |
| 304 | // Error bounds for double precision fast path (N = 7, Ziv failure rate < |
| 305 | // 0.05%): |
| 306 | LIBC_INLINE_VAR constexpr double EXP_ERR_D = 0x1.4p-62; |
| 307 | LIBC_INLINE_VAR constexpr double EXP2_ERR_D = 0x1.0p-64; |
| 308 | |
| 309 | // Lookup table for 2^(i * 2^-7) with i = 0..127. |
| 310 | // Generated by Sollya with: |
| 311 | // > for i from 0 to 127 do { |
| 312 | // a = 2^(i * 2^-7); |
| 313 | // b = round(a, D, RN); |
| 314 | // c = round(a - b, D, RN); |
| 315 | // print("{", c, ",", b, "},"); |
| 316 | // }; |
| 317 | LIBC_INLINE_VAR constexpr DoubleDouble EXP2_MID[128] = { |
| 318 | {.lo: 0, .hi: 0x1p0}, |
| 319 | {.lo: 0x1.b61299ab8cdb7p-54, .hi: 0x1.0163da9fb3335p0}, |
| 320 | {.lo: -0x1.19083535b085dp-56, .hi: 0x1.02c9a3e778061p0}, |
| 321 | {.lo: -0x1.0a31c1977c96ep-54, .hi: 0x1.04315e86e7f85p0}, |
| 322 | {.lo: 0x1.d73e2a475b465p-55, .hi: 0x1.059b0d3158574p0}, |
| 323 | {.lo: -0x1.c91dfe2b13c27p-55, .hi: 0x1.0706b29ddf6dep0}, |
| 324 | {.lo: 0x1.186be4bb284ffp-57, .hi: 0x1.0874518759bc8p0}, |
| 325 | {.lo: 0x1.1487818316136p-54, .hi: 0x1.09e3ecac6f383p0}, |
| 326 | {.lo: 0x1.8a62e4adc610bp-54, .hi: 0x1.0b5586cf9890fp0}, |
| 327 | {.lo: 0x1.01edc16e24f71p-54, .hi: 0x1.0cc922b7247f7p0}, |
| 328 | {.lo: 0x1.03a1727c57b53p-59, .hi: 0x1.0e3ec32d3d1a2p0}, |
| 329 | {.lo: -0x1.b9bedc44ebd7bp-57, .hi: 0x1.0fb66affed31bp0}, |
| 330 | {.lo: -0x1.6c51039449b3ap-54, .hi: 0x1.11301d0125b51p0}, |
| 331 | {.lo: -0x1.1b514b36ca5c7p-58, .hi: 0x1.12abdc06c31ccp0}, |
| 332 | {.lo: -0x1.32fbf9af1369ep-54, .hi: 0x1.1429aaea92dep0}, |
| 333 | {.lo: 0x1.2406ab9eeab0ap-55, .hi: 0x1.15a98c8a58e51p0}, |
| 334 | {.lo: -0x1.19041b9d78a76p-55, .hi: 0x1.172b83c7d517bp0}, |
| 335 | {.lo: -0x1.11023d1970f6cp-54, .hi: 0x1.18af9388c8deap0}, |
| 336 | {.lo: 0x1.e5b4c7b4968e4p-55, .hi: 0x1.1a35beb6fcb75p0}, |
| 337 | {.lo: -0x1.95386352ef607p-54, .hi: 0x1.1bbe084045cd4p0}, |
| 338 | {.lo: 0x1.e016e00a2643cp-54, .hi: 0x1.1d4873168b9aap0}, |
| 339 | {.lo: -0x1.1df98027bb78cp-54, .hi: 0x1.1ed5022fcd91dp0}, |
| 340 | {.lo: 0x1.dc775814a8495p-55, .hi: 0x1.2063b88628cd6p0}, |
| 341 | {.lo: 0x1.2a97e9494a5eep-55, .hi: 0x1.21f49917ddc96p0}, |
| 342 | {.lo: 0x1.9b07eb6c70573p-54, .hi: 0x1.2387a6e756238p0}, |
| 343 | {.lo: 0x1.ac155bef4f4a4p-55, .hi: 0x1.251ce4fb2a63fp0}, |
| 344 | {.lo: 0x1.2bd339940e9d9p-55, .hi: 0x1.26b4565e27cddp0}, |
| 345 | {.lo: -0x1.a4c3a8c3f0d7ep-54, .hi: 0x1.284dfe1f56381p0}, |
| 346 | {.lo: 0x1.612e8afad1255p-55, .hi: 0x1.29e9df51fdee1p0}, |
| 347 | {.lo: -0x1.10adcd6381aa4p-59, .hi: 0x1.2b87fd0dad99p0}, |
| 348 | {.lo: 0x1.0024754db41d5p-54, .hi: 0x1.2d285a6e4030bp0}, |
| 349 | {.lo: 0x1.1ca0f45d52383p-56, .hi: 0x1.2ecafa93e2f56p0}, |
| 350 | {.lo: 0x1.6f46ad23182e4p-55, .hi: 0x1.306fe0a31b715p0}, |
| 351 | {.lo: 0x1.a9ce78e18047cp-55, .hi: 0x1.32170fc4cd831p0}, |
| 352 | {.lo: 0x1.32721843659a6p-54, .hi: 0x1.33c08b26416ffp0}, |
| 353 | {.lo: -0x1.b5cee5c4e4628p-55, .hi: 0x1.356c55f929ff1p0}, |
| 354 | {.lo: -0x1.63aeabf42eae2p-54, .hi: 0x1.371a7373aa9cbp0}, |
| 355 | {.lo: -0x1.e958d3c9904bdp-54, .hi: 0x1.38cae6d05d866p0}, |
| 356 | {.lo: -0x1.5e436d661f5e3p-56, .hi: 0x1.3a7db34e59ff7p0}, |
| 357 | {.lo: -0x1.efff8375d29c3p-54, .hi: 0x1.3c32dc313a8e5p0}, |
| 358 | {.lo: 0x1.ada0911f09ebcp-55, .hi: 0x1.3dea64c123422p0}, |
| 359 | {.lo: -0x1.7d023f956f9f3p-54, .hi: 0x1.3fa4504ac801cp0}, |
| 360 | {.lo: -0x1.ef3691c309278p-58, .hi: 0x1.4160a21f72e2ap0}, |
| 361 | {.lo: -0x1.1c7dde35f7999p-55, .hi: 0x1.431f5d950a897p0}, |
| 362 | {.lo: 0x1.89b7a04ef80dp-59, .hi: 0x1.44e086061892dp0}, |
| 363 | {.lo: 0x1.c944bd1648a76p-54, .hi: 0x1.46a41ed1d0057p0}, |
| 364 | {.lo: 0x1.3c1a3b69062fp-56, .hi: 0x1.486a2b5c13cdp0}, |
| 365 | {.lo: 0x1.9cb62f3d1be56p-54, .hi: 0x1.4a32af0d7d3dep0}, |
| 366 | {.lo: 0x1.d4397afec42e2p-56, .hi: 0x1.4bfdad5362a27p0}, |
| 367 | {.lo: 0x1.8ecdbbc6a7833p-54, .hi: 0x1.4dcb299fddd0dp0}, |
| 368 | {.lo: -0x1.4b309d25957e3p-54, .hi: 0x1.4f9b2769d2ca7p0}, |
| 369 | {.lo: -0x1.f768569bd93efp-55, .hi: 0x1.516daa2cf6642p0}, |
| 370 | {.lo: -0x1.07abe1db13cadp-55, .hi: 0x1.5342b569d4f82p0}, |
| 371 | {.lo: -0x1.d689cefede59bp-55, .hi: 0x1.551a4ca5d920fp0}, |
| 372 | {.lo: 0x1.9bb2c011d93adp-54, .hi: 0x1.56f4736b527dap0}, |
| 373 | {.lo: 0x1.295e15b9a1de8p-55, .hi: 0x1.58d12d497c7fdp0}, |
| 374 | {.lo: 0x1.6324c054647adp-54, .hi: 0x1.5ab07dd485429p0}, |
| 375 | {.lo: 0x1.c4b1b816986a2p-60, .hi: 0x1.5c9268a5946b7p0}, |
| 376 | {.lo: 0x1.ba6f93080e65ep-54, .hi: 0x1.5e76f15ad2148p0}, |
| 377 | {.lo: -0x1.3e2429b56de47p-54, .hi: 0x1.605e1b976dc09p0}, |
| 378 | {.lo: -0x1.383c17e40b497p-54, .hi: 0x1.6247eb03a5585p0}, |
| 379 | {.lo: -0x1.c483c759d8933p-55, .hi: 0x1.6434634ccc32p0}, |
| 380 | {.lo: -0x1.bb60987591c34p-54, .hi: 0x1.6623882552225p0}, |
| 381 | {.lo: 0x1.038ae44f73e65p-57, .hi: 0x1.68155d44ca973p0}, |
| 382 | {.lo: -0x1.bdd3413b26456p-54, .hi: 0x1.6a09e667f3bcdp0}, |
| 383 | {.lo: -0x1.2895667ff0b0dp-56, .hi: 0x1.6c012750bdabfp0}, |
| 384 | {.lo: -0x1.bbe3a683c88abp-57, .hi: 0x1.6dfb23c651a2fp0}, |
| 385 | {.lo: -0x1.83c0f25860ef6p-55, .hi: 0x1.6ff7df9519484p0}, |
| 386 | {.lo: -0x1.16e4786887a99p-55, .hi: 0x1.71f75e8ec5f74p0}, |
| 387 | {.lo: -0x1.0a8d96c65d53cp-54, .hi: 0x1.73f9a48a58174p0}, |
| 388 | {.lo: -0x1.0245957316dd3p-54, .hi: 0x1.75feb564267c9p0}, |
| 389 | {.lo: 0x1.866b80a02162dp-54, .hi: 0x1.780694fde5d3fp0}, |
| 390 | {.lo: -0x1.41577ee04992fp-55, .hi: 0x1.7a11473eb0187p0}, |
| 391 | {.lo: 0x1.f124cd1164dd6p-54, .hi: 0x1.7c1ed0130c132p0}, |
| 392 | {.lo: 0x1.05d02ba15797ep-56, .hi: 0x1.7e2f336cf4e62p0}, |
| 393 | {.lo: -0x1.27c86626d972bp-54, .hi: 0x1.80427543e1a12p0}, |
| 394 | {.lo: -0x1.d4c1dd41532d8p-54, .hi: 0x1.82589994cce13p0}, |
| 395 | {.lo: -0x1.8d684a341cdfbp-55, .hi: 0x1.8471a4623c7adp0}, |
| 396 | {.lo: -0x1.fc6f89bd4f6bap-54, .hi: 0x1.868d99b4492edp0}, |
| 397 | {.lo: 0x1.994c2f37cb53ap-54, .hi: 0x1.88ac7d98a6699p0}, |
| 398 | {.lo: 0x1.6e9f156864b27p-54, .hi: 0x1.8ace5422aa0dbp0}, |
| 399 | {.lo: -0x1.0d55e32e9e3aap-56, .hi: 0x1.8cf3216b5448cp0}, |
| 400 | {.lo: 0x1.5cc13a2e3976cp-55, .hi: 0x1.8f1ae99157736p0}, |
| 401 | {.lo: -0x1.dd6792e582524p-54, .hi: 0x1.9145b0b91ffc6p0}, |
| 402 | {.lo: -0x1.75fc781b57ebcp-57, .hi: 0x1.93737b0cdc5e5p0}, |
| 403 | {.lo: -0x1.64b7c96a5f039p-56, .hi: 0x1.95a44cbc8520fp0}, |
| 404 | {.lo: -0x1.d185b7c1b85d1p-54, .hi: 0x1.97d829fde4e5p0}, |
| 405 | {.lo: -0x1.173bd91cee632p-54, .hi: 0x1.9a0f170ca07bap0}, |
| 406 | {.lo: 0x1.c7c46b071f2bep-56, .hi: 0x1.9c49182a3f09p0}, |
| 407 | {.lo: 0x1.824ca78e64c6ep-56, .hi: 0x1.9e86319e32323p0}, |
| 408 | {.lo: -0x1.359495d1cd533p-54, .hi: 0x1.a0c667b5de565p0}, |
| 409 | {.lo: 0x1.6305c7ddc36abp-54, .hi: 0x1.a309bec4a2d33p0}, |
| 410 | {.lo: -0x1.d2f6edb8d41e1p-54, .hi: 0x1.a5503b23e255dp0}, |
| 411 | {.lo: 0x1.bcb7ecac563c7p-54, .hi: 0x1.a799e1330b358p0}, |
| 412 | {.lo: 0x1.0fac90ef7fd31p-54, .hi: 0x1.a9e6b5579fdbfp0}, |
| 413 | {.lo: -0x1.f9234cae76cdp-55, .hi: 0x1.ac36bbfd3f37ap0}, |
| 414 | {.lo: 0x1.7a1cd345dcc81p-54, .hi: 0x1.ae89f995ad3adp0}, |
| 415 | {.lo: -0x1.bdef54c80e425p-54, .hi: 0x1.b0e07298db666p0}, |
| 416 | {.lo: -0x1.2805e3084d708p-57, .hi: 0x1.b33a2b84f15fbp0}, |
| 417 | {.lo: -0x1.c71dfbbba6de3p-54, .hi: 0x1.b59728de5593ap0}, |
| 418 | {.lo: -0x1.5584f7e54ac3bp-56, .hi: 0x1.b7f76f2fb5e47p0}, |
| 419 | {.lo: -0x1.efcd30e54292ep-54, .hi: 0x1.ba5b030a1064ap0}, |
| 420 | {.lo: 0x1.23dd07a2d9e84p-55, .hi: 0x1.bcc1e904bc1d2p0}, |
| 421 | {.lo: -0x1.efdca3f6b9c73p-54, .hi: 0x1.bf2c25bd71e09p0}, |
| 422 | {.lo: 0x1.11065895048ddp-55, .hi: 0x1.c199bdd85529cp0}, |
| 423 | {.lo: 0x1.b4537e083c60ap-54, .hi: 0x1.c40ab5fffd07ap0}, |
| 424 | {.lo: 0x1.2884dff483cadp-54, .hi: 0x1.c67f12e57d14bp0}, |
| 425 | {.lo: 0x1.1acbc48805c44p-56, .hi: 0x1.c8f6d9406e7b5p0}, |
| 426 | {.lo: 0x1.503cbd1e949dbp-56, .hi: 0x1.cb720dcef9069p0}, |
| 427 | {.lo: -0x1.dd83b53829d72p-55, .hi: 0x1.cdf0b555dc3fap0}, |
| 428 | {.lo: -0x1.cbc3743797a9cp-54, .hi: 0x1.d072d4a07897cp0}, |
| 429 | {.lo: -0x1.d487b719d8578p-54, .hi: 0x1.d2f87080d89f2p0}, |
| 430 | {.lo: 0x1.2ed02d75b3707p-55, .hi: 0x1.d5818dcfba487p0}, |
| 431 | {.lo: -0x1.11ec18beddfe8p-54, .hi: 0x1.d80e316c98398p0}, |
| 432 | {.lo: 0x1.c2300696db532p-54, .hi: 0x1.da9e603db3285p0}, |
| 433 | {.lo: 0x1.2da5778f018c3p-54, .hi: 0x1.dd321f301b46p0}, |
| 434 | {.lo: -0x1.1a5cd4f184b5cp-54, .hi: 0x1.dfc97337b9b5fp0}, |
| 435 | {.lo: -0x1.7b627817a1496p-54, .hi: 0x1.e264614f5a129p0}, |
| 436 | {.lo: 0x1.39e8980a9cc8fp-55, .hi: 0x1.e502ee78b3ff6p0}, |
| 437 | {.lo: 0x1.2d522ca0c8de2p-54, .hi: 0x1.e7a51fbc74c83p0}, |
| 438 | {.lo: -0x1.e9c23179c2893p-54, .hi: 0x1.ea4afa2a490dap0}, |
| 439 | {.lo: -0x1.c93f3b411ad8cp-54, .hi: 0x1.ecf482d8e67f1p0}, |
| 440 | {.lo: 0x1.dc7f486a4b6bp-54, .hi: 0x1.efa1bee615a27p0}, |
| 441 | {.lo: 0x1.3a1a5bf0d8e43p-54, .hi: 0x1.f252b376bba97p0}, |
| 442 | {.lo: 0x1.9d3e12dd8a18bp-54, .hi: 0x1.f50765b6e454p0}, |
| 443 | {.lo: -0x1.dbb12d006350ap-54, .hi: 0x1.f7bfdad9cbe14p0}, |
| 444 | {.lo: 0x1.74853f3a5931ep-55, .hi: 0x1.fa7c1819e90d8p0}, |
| 445 | {.lo: 0x1.2eb74966579e7p-57, .hi: 0x1.fd3c22b8f71f1p0}, |
| 446 | }; |
| 447 | |
| 448 | // Cold path for scaling and rounding: |
| 449 | // 2^hi * (r_hi + r_lo) ~ b^x |
| 450 | // when the result may be subnormal (hi <= -1022). Falls back to 128-bit |
| 451 | // evaluation exp_accurate_128(x, log2_base) if Ziv's denormal rounding test |
| 452 | // fails. |
| 453 | // |
| 454 | // Input expectations: |
| 455 | // - x: original input in the non-overflowing/non-underflowing range of b^x. |
| 456 | // - hi: integer exponent k >> 7 in [-1075, -1022]. |
| 457 | // - r_hi, lo_u: high part and upper-bounded low part (r_lo + err_d) of the |
| 458 | // unscaled mantissa: |
| 459 | // 2^(idx / 2^7) * exp(u) in [1 - 2^-8, 2), |
| 460 | // with |lo_u - err_d| << r_hi. |
| 461 | // - err_d: Ziv error bound on r_hi + r_lo. |
| 462 | // - log2_base: pointer to 192-bit log2(b) table (or nullptr when b = 2). |
| 463 | LIBC_NOINLINE LIBC_INLINE double |
| 464 | exp_denorm(double x, int hi, double r_hi, double lo_u, double err_d, |
| 465 | const ExpBase192 *log2_base = nullptr) { |
| 466 | using FPBits = fputil::FPBits<double>; |
| 467 | // Exact subnormal power of 2 when x is an integer in [-1074, -1022]. |
| 468 | if (log2_base == nullptr && LIBC_UNLIKELY(static_cast<double>(hi) == x)) |
| 469 | return FPBits(uint64_t(1) << (hi + 1074)).get_val(); |
| 470 | |
| 471 | if (auto r_denorm = ziv_test_denorm(hi, mid: r_hi, lo: lo_u - err_d, err: err_d); |
| 472 | LIBC_LIKELY(r_denorm.has_value())) { |
| 473 | double res = r_denorm.value(); |
| 474 | if (LIBC_UNLIKELY(FPBits(res).is_normal())) |
| 475 | return res; |
| 476 | |
| 477 | fputil::set_errno_if_required(ERANGE); |
| 478 | fputil::raise_underflow_except_if_required<double>(); |
| 479 | return res; |
| 480 | } |
| 481 | return exp_accurate_128(x, log2_base); |
| 482 | } |
| 483 | |
| 484 | // Evaluate: |
| 485 | // b^x = 2^hi * 2^(idx / 2^7) * exp(u) |
| 486 | // in double-double precision and apply Ziv's rounding test, falling back to |
| 487 | // exp_denorm (when hi <= -1022) or exp_accurate_128 (when Ziv's test fails). |
| 488 | // |
| 489 | // Input expectations: |
| 490 | // - x: original input after filtering out tiny, overflow, underflow, and |
| 491 | // Inf/NaN cases. |
| 492 | // - u: reduced argument: |
| 493 | // u.hi + u.lo ~ x * log(b) - k * 2^-7 * log(2) |
| 494 | // with |u.hi + u.lo| <= 2^-8 * log(2). On targets without FMA, |
| 495 | // lsb(u.hi) >= 2^-30 and |u.lo| < 2^-18 |
| 496 | // so that m_hi * u.hi is exact in double. |
| 497 | // - hi: integer exponent k >> 7 in [-1075, 1024]. |
| 498 | // When hi == 1024, k = 1024 * 2^7 so |
| 499 | // idx = 0 (exp2_mid = 1.0) and u < -2^-46 < 0, |
| 500 | // since x is strictly below the overflow threshold, which keeps upper in |
| 501 | // [1 - 2^-8, 1) with unbiased exponent -1 (biased exponent 1022). Adding |
| 502 | // hi = 1024 in scale_exp2(upper, hi) then produces biased exponent 2046 |
| 503 | // (unbiased exponent 1023) without overflowing. |
| 504 | // - idx: table index k & 0x7f in [0, 127]. |
| 505 | // - err_d: Ziv error bound on the double-double approximation r_hi + r_lo. |
| 506 | // - log2_base: pointer to 192-bit log2(b) table (or nullptr when b = 2). |
| 507 | LIBC_ALWAYS_INLINE double exp2_eval(double x, DoubleDouble u, int hi, |
| 508 | unsigned idx, double err_d = EXP2_ERR_D, |
| 509 | const ExpBase192 *log2_base = nullptr) { |
| 510 | DoubleDouble exp2_mid = EXP2_MID[idx]; |
| 511 | |
| 512 | // Reconstruction of 2^(idx / 2^7) * exp(u) ~ exp2_mid * (1 + u + u^2 * P(u)) |
| 513 | // where: |
| 514 | // exp2_mid = 2^(idx / 2^7) = exp2_mid.hi + exp2_mid.lo |
| 515 | // u = dx * log(b) = u.hi + u.lo |
| 516 | #ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 517 | // Decompose exp2_mid * (1 + u + u^2 * P(u)) ~ r_hi + (r_lo + tail): |
| 518 | // r_hi + r_lo = exp2_mid.hi * (1 + u.hi) |
| 519 | // tail = exp2_mid.hi * (u.lo + u^2 * P(u)) |
| 520 | // + exp2_mid.lo * (1 + u.hi) |
| 521 | // where the omitted term: |
| 522 | // exp2_mid.lo * (u.lo + u^2 * P(u)) |
| 523 | // is bounded by 2^(-54 - 18) = 2^-72 and absorbed into err_d. |
| 524 | |
| 525 | // p ~ (exp(u) - 1 - u) / u^2 |
| 526 | double u2 = u.hi * u.hi; |
| 527 | double p = fputil::estrin_polyeval(u.hi, EXP_P_COEFFS); |
| 528 | |
| 529 | // r_hi = round(exp2_mid.hi * (1 + u.hi)) |
| 530 | double r_hi = fputil::multiply_add(exp2_mid.hi, u.hi, exp2_mid.hi); |
| 531 | // mid_lo ~ exp2_mid.lo * (1 + u.hi) |
| 532 | double mid_lo = fputil::multiply_add(exp2_mid.lo, u.hi, exp2_mid.lo); |
| 533 | // poly_lo ~ u.lo + u^2 * P(u) |
| 534 | double poly_lo = fputil::multiply_add(u2, p, u.lo); |
| 535 | |
| 536 | // Fold +/-err_d into mid_lo so tail_u, tail_l, and r_lo can be evaluated in |
| 537 | // parallel: |
| 538 | // mid_u = mid_lo + err_d |
| 539 | // mid_l = mid_lo - err_d |
| 540 | double mid_u = mid_lo + err_d; |
| 541 | double mid_l = mid_lo - err_d; |
| 542 | // tail_{u,l} ~ exp2_mid.hi * (u.lo + u^2 * P(u)) + exp2_mid.lo * (1 + u.hi) |
| 543 | // +/- err_d |
| 544 | double tail_u = fputil::multiply_add(exp2_mid.hi, poly_lo, mid_u); |
| 545 | double tail_l = fputil::multiply_add(exp2_mid.hi, poly_lo, mid_l); |
| 546 | // r_lo = exp2_mid.hi * (1 + u.hi) - r_hi (exact to within 2^-105) |
| 547 | double r_lo = fputil::multiply_add(exp2_mid.hi, u.hi, exp2_mid.hi - r_hi); |
| 548 | |
| 549 | // lo_{u,l} ~ r_lo + tail +/- err_d |
| 550 | double lo_u = r_lo + tail_u; |
| 551 | double lo_l = r_lo + tail_l; |
| 552 | #else |
| 553 | // p ~ (exp(u) - 1 - u) / u^2 |
| 554 | double u_sum = u.hi + u.lo; |
| 555 | double u2 = u_sum * u_sum; |
| 556 | double p = fputil::estrin_polyeval(x: u_sum, a: EXP_P_COEFFS); |
| 557 | |
| 558 | // Split exp2_mid = m_hi + m_lo with lsb(m_hi) >= 2^-22 and |m_lo| < 2^-22: |
| 559 | LIBC_BIT_CAST_CONSTEXPR_VAR double HI_MASK_22 = |
| 560 | cpp::bit_cast<double>(from: 0xffff'ffff'c000'0000ULL); |
| 561 | double m_hi = fputil::fp_and(a: exp2_mid.hi, b: HI_MASK_22); // lsb = 2^-22 |
| 562 | double m_lo = (exp2_mid.hi - m_hi) + exp2_mid.lo; |
| 563 | |
| 564 | // Since lsb(u.hi) >= 2^-30 and r_hi is in [1 - 2^-8, 2), both: |
| 565 | // m_hi * u.hi and r_hi = m_hi * (1 + u.hi) |
| 566 | // are exact: |
| 567 | double prod_hi = m_hi * u.hi; // exact, lsb = 2^-52 |
| 568 | double r_hi = m_hi + prod_hi; // exact |
| 569 | |
| 570 | // poly_lo ~ u.lo + u^2 * P(u) |
| 571 | double u2_p = u2 * p; |
| 572 | double poly_lo = u.lo + u2_p; |
| 573 | |
| 574 | // r_lo ~ exp2_mid.hi * (u.lo + u^2 * P(u)) + m_lo * (1 + u.hi) |
| 575 | double l0 = exp2_mid.hi * poly_lo; |
| 576 | double l1 = m_lo * (1.0 + u.hi); |
| 577 | double r_lo = l0 + l1; |
| 578 | |
| 579 | // lo_{u,l} = r_lo +/- err_d |
| 580 | double lo_u = r_lo + err_d; |
| 581 | double lo_l = r_lo - err_d; |
| 582 | #endif |
| 583 | // Ziv's rounding test in the current rounding mode: |
| 584 | double upper = r_hi + lo_u; |
| 585 | double lower = r_hi + lo_l; |
| 586 | |
| 587 | if (LIBC_LIKELY(upper == lower && hi > -1022)) |
| 588 | return scale_exp2(r: upper, hi); |
| 589 | |
| 590 | if (LIBC_UNLIKELY(hi <= -1022)) |
| 591 | return exp_denorm(x, hi, r_hi, lo_u, err_d, log2_base); |
| 592 | |
| 593 | return exp_accurate_128(x, log2_base); |
| 594 | } |
| 595 | |
| 596 | #endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 597 | |
| 598 | } // namespace double_eval |
| 599 | } // namespace math |
| 600 | } // namespace LIBC_NAMESPACE_DECL |
| 601 | |
| 602 | #endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXP_UTILS_H |
| 603 | |