| 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 | /// 128-bit accurate path for double-precision pow(x, y). |
| 11 | /// |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_128_H |
| 15 | #define LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_128_H |
| 16 | |
| 17 | #include "src/__support/CPP/bit.h" |
| 18 | #include "src/__support/FPUtil/FPBits.h" |
| 19 | #include "src/__support/FPUtil/dyadic_float.h" |
| 20 | #include "src/__support/FPUtil/except_value_utils.h" |
| 21 | #include "src/__support/big_int.h" |
| 22 | #include "src/__support/common.h" |
| 23 | #include "src/__support/frac128.h" |
| 24 | #include "src/__support/frac64.h" |
| 25 | #include "src/__support/macros/attributes.h" |
| 26 | #include "src/__support/macros/config.h" |
| 27 | #include "src/__support/macros/optimization.h" |
| 28 | #include "src/__support/math/exp2_accurate_128.h" |
| 29 | #include "src/__support/math/pow_accurate_256.h" |
| 30 | #include "src/__support/math/pow_utils.h" |
| 31 | #include "src/__support/sign.h" |
| 32 | |
| 33 | namespace LIBC_NAMESPACE_DECL { |
| 34 | namespace math { |
| 35 | namespace pow_internal { |
| 36 | |
| 37 | using DFloat128 = typename fputil::DyadicFloat<128>; |
| 38 | |
| 39 | // Accurate log2(x) in 128-bit precision using 2-step integer range reduction: |
| 40 | // x = 2^x_e * m_x, with 1 <= m_x < 2 |
| 41 | // log2(x) = x_e + (-log2(r1)) + (-log2(r2)) + log2(1 + dx). |
| 42 | // log2(1 + dx) is evaluated with a degree-15 prefix of LOG2_POLY_256 using a |
| 43 | // 2-tier Horner scheme (Frac64 and Frac128). |
| 44 | LIBC_COLD LIBC_INLINE DFloat128 log2_f128(int x_e, uint64_t x_mant) { |
| 45 | if (LIBC_UNLIKELY(x_mant == 0)) |
| 46 | return df_from_int<128>(x: x_e); |
| 47 | |
| 48 | unsigned idx1 = 0; |
| 49 | int k2 = 0; |
| 50 | int64_t dx_int = log2_range_reduce(x_mant, idx1, k2); // lsb = 2^-65 |
| 51 | bool dx_is_neg = (dx_int < 0); |
| 52 | uint64_t abs_dx = |
| 53 | static_cast<uint64_t>(dx_is_neg ? -dx_int : dx_int); // lsb = 2^-65 |
| 54 | |
| 55 | Frac64 y64(abs_dx >> 1); // lsb = 2^-64 |
| 56 | Frac128 y({abs_dx << 63, abs_dx >> 1}); // lsb = 2^-128 |
| 57 | |
| 58 | // Step 1: 64-bit evaluation for degrees 8..15 (|dx|^8 < 2^-63.7): |
| 59 | Frac64 p64 = LOG2_POLY_128[7].to_frac64(); // lsb = 2^-64 |
| 60 | LIBC_LOOP_NOUNROLL |
| 61 | for (int k = 6; k >= 0; --k) { |
| 62 | Frac64 py = p64 * y64; |
| 63 | Frac64 c = LOG2_POLY_128[k].to_frac64(); |
| 64 | p64 = dx_is_neg ? (c + py) : (c - py); // lsb = 2^-64 |
| 65 | } |
| 66 | |
| 67 | // Step 2: 128-bit evaluation for degrees 0..7: |
| 68 | Frac128 p({0, p64.val[0]}); // lsb = 2^-128 |
| 69 | LIBC_LOOP_NOUNROLL |
| 70 | for (int k = 7; k >= 0; --k) { |
| 71 | Frac128 py = p * y; |
| 72 | Frac128 c = LOG2_POLY_256[k].to_frac128(); |
| 73 | p = dx_is_neg ? (c + py) : (c - py); // lsb = 2^-128 |
| 74 | } |
| 75 | |
| 76 | // Normalize abs_dx before multiplying by p so near-1.0 inputs (x_e - log2(r) |
| 77 | // == 0) retain full 128-bit precision without shifting out low bits. |
| 78 | int lz = cpp::countl_zero(value: abs_dx); |
| 79 | uint64_t norm_dx = abs_dx << lz; // lsb = 2^-(65 + lz) |
| 80 | Frac128 norm_log2_1p = Frac128({0, norm_dx}) * p; // lsb = 2^-(128 + lz) |
| 81 | if (LIBC_UNLIKELY((x_e == 0 && idx1 == 0 && k2 == 0) || |
| 82 | (x_e == -1 && idx1 == 16 && k2 == 0))) { |
| 83 | return df_norm_1bit<128>(sign: dx_is_neg ? Sign::NEG : Sign::POS, exp: -128 - lz, |
| 84 | m: UInt<128>(norm_log2_1p.val)); |
| 85 | } |
| 86 | |
| 87 | Frac128 log2_1p = norm_log2_1p >> static_cast<size_t>(lz + 1); // lsb = 2^-127 |
| 88 | Frac128 log2_rd = LOG2_R1_FRAC256[idx1].to_frac128() + |
| 89 | LOG2_R2_FRAC256[k2 + 4].to_frac128(); // lsb = 2^-127 |
| 90 | Frac128 log2_m = |
| 91 | dx_is_neg ? (log2_rd - log2_1p) : (log2_rd + log2_1p); // lsb = 2^-127 |
| 92 | |
| 93 | return combine_log2_df<128>(x_e, log2_m: UInt<128>(log2_m.val)); |
| 94 | } |
| 95 | |
| 96 | // Accurate pow(x, y) in 128-bit precision. |
| 97 | LIBC_COLD LIBC_NOINLINE LIBC_INLINE double |
| 98 | pow_accurate(double y, bool is_neg, int x_e, uint64_t x_mant) { |
| 99 | if (LIBC_UNLIKELY(x_e == 0 && x_mant == 0)) |
| 100 | return is_neg ? -1.0 : 1.0; |
| 101 | |
| 102 | Sign out_sign = is_neg ? Sign::NEG : Sign::POS; |
| 103 | using FPBits = fputil::FPBits<double>; |
| 104 | FPBits ybits(y); |
| 105 | int exp_y = ybits.get_exponent(); |
| 106 | uint64_t mant_y = (ybits.get_mantissa() | (1ULL << 52)) << 11; |
| 107 | |
| 108 | DFloat128 log2_x = log2_f128(x_e, x_mant); |
| 109 | uint64_t z_hi = mul_uint64(a&: log2_x.mantissa, b: mant_y); |
| 110 | uint64_t z_lo = log2_x.mantissa.val[0]; |
| 111 | |
| 112 | DFloat128 z; |
| 113 | z.sign = (ybits.sign() == log2_x.sign) ? Sign::POS : Sign::NEG; |
| 114 | z.exponent = log2_x.exponent + exp_y + 1; |
| 115 | z.mantissa = UInt<128>({log2_x.mantissa.val[1], z_hi}); |
| 116 | |
| 117 | // 2^1025 > max normal double; 2^-1076 < min subnormal double. |
| 118 | int msb = static_cast<int>(z_hi >> 63); |
| 119 | int z_exp = z.exponent + 126 + msb; |
| 120 | if (LIBC_UNLIKELY(z_exp >= 10)) { |
| 121 | uint64_t int_z = (z_exp > 10) ? 2048 : (z_hi >> (52 + msb)); |
| 122 | if (!z.sign.is_neg() && int_z >= 1025) |
| 123 | return fputil::set_overflow<double>(out_sign); |
| 124 | if (z.sign.is_neg() && int_z >= 1076) |
| 125 | return fputil::set_underflow<double>(out_sign); |
| 126 | } |
| 127 | |
| 128 | // For 0 < |z| < 2^-54, x^y is strictly in (1 - 2^-54, 1 + 2^-53) \ {1}. |
| 129 | DFloat128 r; |
| 130 | if (LIBC_UNLIKELY(z_exp <= -55)) { |
| 131 | r.sign = out_sign; |
| 132 | if (z.sign.is_neg()) { |
| 133 | r.exponent = -128; |
| 134 | r.mantissa = UInt<128>({~0ULL, ~0ULL}); |
| 135 | } else { |
| 136 | r.exponent = -127; |
| 137 | r.mantissa = UInt<128>({1ULL, 1ULL << 63}); |
| 138 | } |
| 139 | return static_cast<double>(r); |
| 140 | } |
| 141 | |
| 142 | r = double_eval::exp2_df128(z, lo: z_lo); |
| 143 | r.sign = out_sign; |
| 144 | |
| 145 | int unbiased_exp = r.exponent + 127; |
| 146 | if (LIBC_UNLIKELY(unbiased_exp >= 1024)) |
| 147 | return fputil::set_overflow<double>(out_sign); |
| 148 | |
| 149 | // Check if r is close to a 54-bit rounding boundary (either an exact 53-bit |
| 150 | // float or a midpoint). |
| 151 | // Lauter & Lefevre (2009) showed that if x^y is not an exact 54-bit number, |
| 152 | // |x^y - o_54(x^y)| / x^y >= 2^-114 (distance >= 2^13 in r.mantissa). |
| 153 | // For normal outputs (unbiased_exp >= -1022), the 54 leading bits occupy bits |
| 154 | // [127:74] of r.mantissa. Extracting frac_hi = bits [73:10] (1 unit = 2^10 in |
| 155 | // r.mantissa) bounds the evaluation error 32 * |y| + 2^13 (< 2^(exp_y + 6) + |
| 156 | // 2^13) by eps10 = 8 + 2^max(exp_y - 4, 0) in 2^10 units, reducing the |
| 157 | // two-sided boundary check to a single unsigned wraparound compare. |
| 158 | bool is_boundary_candidate = true; |
| 159 | if (LIBC_LIKELY(unbiased_exp >= -1022)) { |
| 160 | uint64_t frac_hi = (r.mantissa.val[1] << 54) | (r.mantissa.val[0] >> 10); |
| 161 | int shift_e = (exp_y > 4) ? (exp_y - 4) : 0; |
| 162 | uint64_t eps10 = 8ULL + (1ULL << shift_e); |
| 163 | is_boundary_candidate = (frac_hi + eps10) < (eps10 << 1); |
| 164 | } |
| 165 | |
| 166 | if (LIBC_UNLIKELY(is_boundary_candidate)) { |
| 167 | uint64_t exact_m = 0; |
| 168 | int exact_exp = 0; |
| 169 | if (is_exact_rounding_boundary(x_e, x_mant, y, exact_m, exact_exp)) { |
| 170 | int l = 64 - cpp::countl_zero(value: exact_m); |
| 171 | r.exponent = exact_exp + l - 128; |
| 172 | r.mantissa = UInt<128>({0, exact_m << (64 - l)}); |
| 173 | } else { |
| 174 | r = pow_accurate_256(y_sign: ybits.sign(), exp_y, mant_y, is_neg, x_e, x_mant); |
| 175 | } |
| 176 | } |
| 177 | |
| 178 | if (LIBC_UNLIKELY(r.exponent + 127 >= 1024)) |
| 179 | return fputil::set_overflow<double>(out_sign); |
| 180 | double res = static_cast<double>(r); |
| 181 | if (LIBC_UNLIKELY(FPBits(res).is_inf())) |
| 182 | return fputil::set_overflow<double>(out_sign); |
| 183 | return res; |
| 184 | } |
| 185 | |
| 186 | } // namespace pow_internal |
| 187 | } // namespace math |
| 188 | } // namespace LIBC_NAMESPACE_DECL |
| 189 | |
| 190 | #endif // LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_128_H |
| 191 | |