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
33namespace LIBC_NAMESPACE_DECL {
34namespace math {
35namespace pow_internal {
36
37using 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).
44LIBC_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.
97LIBC_COLD LIBC_NOINLINE LIBC_INLINE double
98pow_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