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 exp2(x).
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXP2_ACCURATE_128_H
15#define LLVM_LIBC_SRC___SUPPORT_MATH_EXP2_ACCURATE_128_H
16
17#include "src/__support/FPUtil/FPBits.h"
18#include "src/__support/FPUtil/dyadic_float.h"
19#include "src/__support/FPUtil/polyeval.h"
20#include "src/__support/big_int.h"
21#include "src/__support/common.h"
22#include "src/__support/frac128.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/sign.h"
27#include "src/__support/uint128.h"
28
29namespace LIBC_NAMESPACE_DECL {
30namespace math {
31namespace double_eval {
32
33using DFloat128 = fputil::DyadicFloat<128>;
34
35// Table of 2^(i / 16) with i = 0..15 in 128-bit fixed-point format:
36// Generated by Sollya with:
37// > display = hexadecimal!;
38// > prec = 256;
39// > for i from 0 to 15 do {
40// a = 2^(i / 16);
41// c_int = round(a * 2^127, 256, RN);
42// hi = floor(c_int * 2^(-64));
43// lo = c_int - hi * 2^64;
44// print(" Frac128({", lo, "ULL,", hi, "ULL}), // 2^(", i, "/16)");
45// };
46LIBC_INLINE_VAR constexpr Frac128 EXP2_MID_FRAC128[16] = {
47 // lsb = 2^-127
48 Frac128({0x0000000000000000ULL, 0x8000000000000000ULL}), // 2^(0/16)
49 Frac128({0xc5c95b8c2154c1b2ULL, 0x85aac367cc487b14ULL}), // 2^(1/16)
50 Frac128({0xfbe4628758a53c90ULL, 0x8b95c1e3ea8bd6e6ULL}), // 2^(2/16)
51 Frac128({0x0fd6d8e0ae5ac9d8ULL, 0x91c3d373ab11c336ULL}), // 2^(3/16)
52 Frac128({0x46ad23182e42f6f6ULL, 0x9837f0518db8a96fULL}), // 2^(4/16)
53 Frac128({0xa0911f09ebb9fdd1ULL, 0x9ef5326091a111adULL}), // 2^(5/16)
54 Frac128({0x1cbd7f621710701bULL, 0xa5fed6a9b15138eaULL}), // 2^(6/16)
55 Frac128({0x4980a8c8f59a2ec4ULL, 0xad583eea42a14ac6ULL}), // 2^(7/16)
56 Frac128({0x597d89b3754abe9fULL, 0xb504f333f9de6484ULL}), // 2^(8/16)
57 Frac128({0xa8811fb66d0faf7aULL, 0xbd08a39f580c36beULL}), // 2^(9/16)
58 Frac128({0x3e2ad0c964dd9f37ULL, 0xc5672a115506daddULL}), // 2^(10/16)
59 Frac128({0xe235838f95f2c6edULL, 0xce248c151f8480e3ULL}), // 2^(11/16)
60 Frac128({0x39a68bb9902d3fdeULL, 0xd744fccad69d6af4ULL}), // 2^(12/16)
61 Frac128({0x065895048dd333caULL, 0xe0ccdeec2a94e111ULL}), // 2^(13/16)
62 Frac128({0xd02d75b3706e54fbULL, 0xeac0c6e7dd24392eULL}), // 2^(14/16)
63 Frac128({0x7b9d0c7aed980fc3ULL, 0xf5257d152486cc2cULL}), // 2^(15/16)
64};
65
66// Polynomial approximation for (2^x - 1) / x:
67// For x in [0, 2^-4], we approximate:
68// P(x) ~ (2^x - 1) / x
69// then:
70// 2^x = 1 + x * P(x).
71//
72// Minimax polynomial coefficients generated by Sollya with:
73// > prec = 500;
74// > P = fpminimax((2^x - 1)/x, 14, [|128...|], [2^(-150), 2^(-4)], fixed);
75// > for i from 0 to 14 do {
76// c = coeff(P, i);
77// c_int = round(c * 2^128, 256, RN);
78// hi = floor(c_int * 2^(-64));
79// lo = c_int - hi * 2^64;
80// print("Frac128({", lo, "ULL,", hi, "ULL}), // c_", i);
81// };
82// > dirtyinfnorm(2^x - (1 + x * P), [0, 2^(-4)]);
83// 0x1.278a...p-139 < 2^-138.
84//
85// Expanding P(x) in Horner form:
86// P(x) = c_0 + x * (c_1 + x * (c_2 + ...))
87// where c_k ~ (log(2))^(k+1) / (k+1)! are all positive and in (0, 1).
88LIBC_INLINE_VAR constexpr Frac128 EXP2_POLY_128[15] = {
89 // lsb = 2^-128
90 Frac128({0xc9e3b39803f2f6afULL, 0xb17217f7d1cf79abULL}), // c_0
91 Frac128({0xde2d60dd92e6c1ceULL, 0x3d7f7bff058b1d50ULL}), // c_1
92 Frac128({0x99d3b15d9958cfa0ULL, 0x0e35846b82505fc5ULL}), // c_2
93 Frac128({0x39977c16aee20457ULL, 0x0276556df749cee5ULL}), // c_3
94 Frac128({0x41c5fda1c13b8fb1ULL, 0x005761ff9e299cc4ULL}), // c_4
95 Frac128({0xb7a58759e18c05e7ULL, 0x000a184897c363c3ULL}), // c_5
96 Frac128({0x3434f0e418799c8bULL, 0x0000ffe5fe2c4586ULL}), // c_6
97 Frac128({0x241c41f55c65febbULL, 0x0000162c0223a5c8ULL}), // c_7
98 Frac128({0x77e77364ac415ce2ULL, 0x000001b5253d395eULL}), // c_8
99 Frac128({0xfe79c174054850e2ULL, 0x0000001e4cf5158bULL}), // c_9
100 Frac128({0x29d719d4d61d89c9ULL, 0x00000001e8cac72dULL}), // c_10
101 Frac128({0xd15314bfa6b56886ULL, 0x000000001c3bd6b4ULL}), // c_11
102 Frac128({0xd8de7d5b7789dd3aULL, 0x0000000001815e5dULL}), // c_12
103 Frac128({0x491912c310d5531bULL, 0x0000000000132403ULL}), // c_13
104 Frac128({0x8d1d877caeba1cfcULL, 0x000000000000c220ULL}), // c_14
105};
106
107struct ExpBase192 {
108 int base_exp;
109 UInt<192> log2_b; // lsb = 2^(base_exp - 191)
110};
111
112// log2(e) in 192-bit fixed-point format (lsb = 2^-191), generated by Sollya
113// with:
114// > display = hexadecimal!;
115// > prec = 500;
116// > c = round(log2(exp(1)) * 2^191, 192, RN);
117// > d2 = floor(c * 2^(-128));
118// > c = c - d2 * 2^128;
119// > d1 = floor(c * 2^(-64));
120// > d0 = c - d1 * 2^64;
121// > print("{", d0, ",", d1, ",", d2, "}");
122LIBC_INLINE_VAR constexpr ExpBase192 LOG2_E_192 = {
123 .base_exp: 0,
124 .log2_b: UInt<192>({
125 0xeb577aa8dd695a59ULL,
126 0xbe87fed0691d3e88ULL,
127 0xb8aa3b295c17f0bbULL,
128 }),
129};
130
131// log2(10) in 192-bit fixed-point format (lsb = 2^-190, base_exp = 1),
132// generated by Sollya with:
133// > display = hexadecimal!;
134// > prec = 500;
135// > c = round(log2(10) * 2^190, 192, RN);
136// > d2 = floor(c * 2^(-128));
137// > c = c - d2 * 2^128;
138// > d1 = floor(c * 2^(-64));
139// > d0 = c - d1 * 2^64;
140// > print("{", d0, ",", d1, ",", d2, "}");
141LIBC_INLINE_VAR constexpr ExpBase192 LOG2_10_192 = {
142 .base_exp: 1,
143 .log2_b: UInt<192>({
144 0xd96c55fe37b3ad4fULL,
145 0x492bf6ff4dafdb4cULL,
146 0xd49a784bcd1b8afeULL,
147 }),
148};
149
150// Evaluate 2^(idx * 2^-4 + u) in [1, 2) as Frac128 (lsb = 2^-127) for
151// idx in [0, 15] and u in [0, 2^-4) (lsb = 2^-128).
152LIBC_INLINE Frac128 exp2_eval_frac128(unsigned idx, const Frac128 &u) {
153 // p ~ (2^u - 1) / u
154 Frac128 p = fputil::loop_polyeval(x: u, a: EXP2_POLY_128); // lsb = 2^-128
155
156 // Reconstruction:
157 // u * p ~ 2^u - 1 (lsb = 2^-128)
158 // m = 2^(idx * 2^-4) (lsb = 2^-127)
159 // m + m * (u * p) ~ m * 2^u (lsb = 2^-127)
160 Frac128 m = EXP2_MID_FRAC128[idx]; // lsb = 2^-127
161 return m + m * (u * p); // lsb = 2^-127
162}
163
164// Compute 2^z in 128-bit precision for a DyadicFloat<128> z with leading bit at
165// bit 126 or 127 of z.mantissa, 2^-54 < |z| < 2^11 (z.exponent in
166// [-181, -117]), and optional extra low limb lo (lsb = 2^(z.exponent - 64)):
167// z = k * 2^-4 + u, 0 <= u < 2^-4
168// hi = k >> 4
169// idx = k & 0x0f
170// 2^z = 2^hi * EXP2_MID_FRAC128[idx] * (1 + u * P(u)).
171LIBC_INLINE DFloat128 exp2_df128(const DFloat128 &z, uint64_t lo = 0) {
172 // z.mantissa has lsb = 2^z.exponent, so the 2^-4 bit of |z| is at bit
173 // (-4 - z.exponent) of z.mantissa, leaving
174 // shift = 128 - (-4 - z.exponent) = z.exponent + 132 bits
175 // at or above 2^-4 in z.mantissa.val[1].
176 // After range reduction, 2^-54 < |z| < 2^11 and z.exponent is in
177 // [-181, -117], so shift is in [-49, 15].
178 int shift = z.exponent + 132;
179 int k = 0;
180 UInt<128> frac;
181 if (LIBC_LIKELY(shift > 0)) {
182 // |z| >= 2^-5 (all |z| >= 2^-4, plus 2^-5 <= |z| < 2^-4 with k = 0 when
183 // bit 127 of z.mantissa is 0): split
184 // |z| = k * 2^-4 + frac * 2^-132.
185 // Here shift is in [1, 15] and shr = 64 - shift is in [49, 63], so all
186 // 64-bit shifts below are strictly in [1, 63] (no undefined behavior).
187 int shr = 64 - shift; // in [49, 63]
188 // k = floor(|z| * 2^4)
189 k = static_cast<int>(z.mantissa.val[1] >> shr); // lsb = 2^-4
190 // Shift z.mantissa left by shift and fill the low shift bits from lo:
191 frac = UInt<128>({(z.mantissa.val[0] << shift) | (lo >> shr),
192 (z.mantissa.val[1] << shift) |
193 (z.mantissa.val[0] >> shr)}); // lsb = 2^-132
194 } else {
195 // |z| < 2^-4: k = 0 and frac = |z| * 2^132, with -shift in [0, 49].
196 frac = z.mantissa >> (-shift); // lsb = 2^-132
197 }
198
199 if (z.sign.is_neg()) {
200 if (LIBC_UNLIKELY(frac.is_zero())) {
201 k = -k;
202 } else {
203 // One's-complement negation on frac (differs from two's-complement by
204 // 2^-132 = 2^-4 * lsb(u)):
205 // -|z| ~ (-k - 1) * 2^-4 + (2^-4 - (frac + 1) * 2^-132).
206 frac = ~frac;
207 k = ~k;
208 }
209 }
210
211 // Decompose:
212 // k * 2^-4 = hi + idx * 2^-4
213 // and scale frac from lsb = 2^-132 to u in [0, 2^-4) with lsb = 2^-128:
214 int hi = k >> 4; // lsb = 1
215 unsigned idx = static_cast<unsigned>(k & 0x0f); // lsb = 2^-4
216 Frac128 u((frac >> 4).val); // lsb = 2^-128
217 Frac128 m_final = exp2_eval_frac128(idx, u); // lsb = 2^-127
218
219 // For tiny negative inputs x = -a - a^2 / 2 (where 1 - a is an exact double),
220 // exp(x) = (1 - a) + a^3 / 3 + O(a^4)
221 // is strictly greater than 1 - a by a residual that can be smaller than
222 // 2^-128 (down to ~2^-155 for a = 2^-51).
223 //
224 // When z in (-2^-4, 0) (shift <= 0 and z < 0), the downward truncations of
225 // u, u * p, and m * (u * p) bias m_final by:
226 // (-5, 0) * lsb(m_final).
227 // Adding 5 shifts this error to:
228 // (0, 5) * lsb(m_final),
229 // so 2^-1 * m_final is strictly above 1 - a (preserving a non-zero sticky bit
230 // in all rounding modes).
231 if (shift <= 0 && z.sign.is_neg())
232 m_final += Frac128(5);
233
234 // Since m_final is in [1, 2) with lsb = 2^-127, its leading bit is already
235 // at bit 127, so r is normalized with exponent = hi - 127:
236 DFloat128 r;
237 r.sign = Sign::POS;
238 r.exponent = hi - 127;
239 r.mantissa = UInt<128>(m_final.val);
240 return r;
241}
242
243// Compute b^x (for b = 2, e, or 10) in 128-bit precision using direct base-2
244// 192-bit fixed-point range reduction. Here log2_base->log2_b holds:
245// round(log2(b) * 2^(191 - base_exp)),
246// or log2_base is nullptr when b = 2.
247LIBC_NOINLINE LIBC_INLINE double
248exp_accurate_128(double x, const ExpBase192 *log2_base = nullptr) {
249 using FPBits = fputil::FPBits<double>;
250 FPBits xbits(x);
251 int exp_x = xbits.get_exponent();
252
253 // Normalize |x|'s 53-bit mantissa to [2^63, 2^64):
254 uint64_t mant_x = (xbits.get_mantissa() | (1ULL << 52)) << 11;
255
256 DFloat128 z;
257 z.sign = xbits.sign();
258 uint64_t w0 = 0;
259
260 if (log2_base != nullptr) {
261 // 1-limb x 3-limb product:
262 // mant_x has lsb = 2^(exp_x - 63)
263 // log2_base->log2_b has lsb = 2^(base_exp - 191)
264 // p = mant_x * log2_base->log2_b has lsb = 2^(exp_x + base_exp - 254)
265 UInt<256> p = log2_base->log2_b.ful_mul(other: UInt<64>(mant_x));
266 // Extract the top 192 bits (p.val[3], p.val[2], p.val[1]) as
267 // (z.mantissa, w0):
268 z.exponent = exp_x + log2_base->base_exp - 126;
269 z.mantissa = UInt<128>({p.val[2], p.val[3]}); // lsb = 2^z.exponent
270 w0 = p.val[1]; // lsb = 2^(z.exponent - 64)
271 } else {
272 // For b = 2, log2(b) = 1, so z = x directly:
273 z.exponent = exp_x - 127;
274 z.mantissa = UInt<128>({0, mant_x}); // lsb = 2^(exp_x - 127)
275 }
276
277 return static_cast<double>(exp2_df128(z, lo: w0));
278}
279
280} // namespace double_eval
281} // namespace math
282} // namespace LIBC_NAMESPACE_DECL
283
284#endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXP2_ACCURATE_128_H
285