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/// 256-bit accurate path for double-precision pow(x, y).
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_256_H
15#define LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_256_H
16
17#include "src/__support/CPP/bit.h"
18#include "src/__support/FPUtil/dyadic_float.h"
19#include "src/__support/big_int.h"
20#include "src/__support/common.h"
21#include "src/__support/frac128.h"
22#include "src/__support/frac256.h"
23#include "src/__support/frac64.h"
24#include "src/__support/macros/attributes.h"
25#include "src/__support/macros/config.h"
26#include "src/__support/macros/optimization.h"
27#include "src/__support/math/pow_utils.h"
28#include "src/__support/math_extras.h"
29#include "src/__support/sign.h"
30
31namespace LIBC_NAMESPACE_DECL {
32namespace math {
33namespace pow_internal {
34
35using DFloat256 = typename fputil::DyadicFloat<256>;
36
37// Lookup table for -log2(R_1[i]) for i = 0..16 as Frac256 (lsb = 2^-255),
38// where R_1[i] = RD_SMALL_K[i] * 2^-6.
39LIBC_INLINE_VAR constexpr Frac256 LOG2_R1_FRAC256[17] = {
40 // lsb = 2^-255
41 Frac256({0x0000000000000000ULL, 0x0000000000000000ULL,
42 0x0000000000000000ULL, 0x0000000000000000ULL}), // i = 0
43 Frac256({0x9e9fded86733d3caULL, 0xbaad60b1bf6bcd42ULL,
44 0x9da288fc615a727dULL, 0x0beb024b67dda633ULL}), // i = 1
45 Frac256({0x6816ff4ab1e1af50ULL, 0x20909dd35a2a212aULL,
46 0x8720de5377caf325ULL, 0x1563dc29ffacb20cULL}), // i = 2
47 Frac256({0x4627a78c47089d0dULL, 0x4892260a8c79779fULL,
48 0x8fef64f0f62e7b46ULL, 0x1f5fd8a9063e3490ULL}), // i = 3
49 Frac256({0x9d7b13b46dda1849ULL, 0x885dce30d5e9e813ULL,
50 0xc9d0b5ca5a8e7bb5ULL, 0x29edf7659d8b30f1ULL}), // i = 4
51 Frac256({0x4429d9e262f3c8c6ULL, 0xc7395ab7fe8e9835ULL,
52 0xd536fc5bec1a57b8ULL, 0x315130157f7a64ccULL}), // i = 5
53 Frac256({0xe91dc50aab435aa9ULL, 0xe06bcb114a0f1719ULL,
54 0xf6a2b59276887aabULL, 0x3cfbebfca715669dULL}), // i = 6
55 Frac256({0x3ad4311182915175ULL, 0x60c67a245f78bb52ULL,
56 0x8283ccdf555594a0ULL, 0x4531583f9a2be203ULL}), // i = 7
57 Frac256({0xe61b71e474e99f75ULL, 0x75abfd08dec73401ULL,
58 0xd7220e04ebb0e2a4ULL, 0x497028118efabeb7ULL}), // i = 8
59 Frac256({0x2e147034099ccfcfULL, 0xb03b7d7e6bd0493fULL,
60 0xe55be97611f87779ULL, 0x523bbc64c5e64350ULL}), // i = 9
61 Frac256({0xf662658135c18184ULL, 0x5f0bcac4e6cfec7bULL,
62 0x748d68b767f88088ULL, 0x5b77f0a9e3f18cfbULL}), // i = 10
63 Frac256({0xa609c77144ded04cULL, 0xb30a91252b56f94aULL,
64 0x572667587b10ca0dULL, 0x6043e946fd97f5dcULL}), // i = 11
65 Frac256({0x5509d9aded608bccULL, 0xdf7d4115ebc0ee87ULL,
66 0x1ee1343fe7c9cb4aULL, 0x6530a1d24b136c10ULL}), // i = 12
67 Frac256({0x7ea793f02baad929ULL, 0xb0c4015f8fdff17dULL,
68 0xd843902f5aad7542ULL, 0x6f73a77325861c69ULL}), // i = 13
69 Frac256({0xdb6ddbdb00d73945ULL, 0x1ad7c182a716c033ULL,
70 0x99d63ecf5dd4529eULL, 0x74ce04829b7674c1ULL}), // i = 14
71 Frac256({0xfce168eaef943079ULL, 0xce4c86d28e4be331ULL,
72 0xb27e43da520fbdb7ULL, 0x7a514b229c409e33ULL}), // i = 15
73 Frac256({0x0000000000000000ULL, 0x0000000000000000ULL,
74 0x0000000000000000ULL, 0x8000000000000000ULL}), // i = 16
75};
76
77// Lookup table for -log2(R_2[k2]) for k2 = -4..4 as two's-complement Frac256
78// (lsb = 2^-255), where R_2[k2] = (128 - k2) * 2^-7.
79LIBC_INLINE_VAR constexpr Frac256 LOG2_R2_FRAC256[9] = {
80 // lsb = 2^-255
81 Frac256({0xfce168eaef943079ULL, 0xce4c86d28e4be331ULL,
82 0xb27e43da520fbdb7ULL, 0xfa514b229c409e33ULL}), // k2 = -4
83 Frac256({0x59576b46a119898aULL, 0x254008aeb4167a33ULL,
84 0x9faebec15b2e2b43ULL, 0xfbb8cb8abb32fb44ULL}), // k2 = -3
85 Frac256({0x10e7d4a6c2ef9745ULL, 0x3ead121a489569ffULL,
86 0xb23b03bdcfdea0d7ULL, 0xfd230d2f47a5baceULL}), // k2 = -2
87 Frac256({0xa828a9bde1ec7e79ULL, 0xe33209b70d9a5be1ULL,
88 0x071c84ffe86b0bbbULL, 0xfe901af4910f7ae8ULL}), // k2 = -1
89 Frac256({0x0000000000000000ULL, 0x0000000000000000ULL,
90 0x0000000000000000ULL, 0x0000000000000000ULL}), // k2 = 0
91 Frac256({0x6e26f44a7ba5ed8aULL, 0xd4a6b5a62ff68790ULL,
92 0xb5d184a2c615b70aULL, 0x0172c7ba20f73275ULL}), // k2 = 1
93 Frac256({0x262f5ca40b7fa26cULL, 0x3ea8c6b85ced9bdaULL,
94 0xca906c23ef817e0bULL, 0x02e87dd0c3e6aac6ULL}), // k2 = 2
95 Frac256({0x95b7f4fcee92de52ULL, 0xe775fc0ab1c9f028ULL,
96 0x48f836042de0dc32ULL, 0x04612e39315abe0aULL}), // k2 = 3
97 Frac256({0xa3a1e195dfe2d23bULL, 0xfc9f0716c9c77bc6ULL,
98 0x7970e03f821c75d5ULL, 0x05dce53276563557ULL}), // k2 = 4
99};
100
101// Polynomial approximation for log2(1 + dx):
102// For |dx| <= 131 / 32768 < 2^-7.96, we approximate:
103// P(x) ~ log2(1 + x) / (2 * x)
104// then:
105// log2(1 + dx) = 2 * dx * P(dx).
106//
107// Minimax polynomial coefficients generated by Sollya with:
108// > prec = 512;
109// > P = fpminimax(log2(1 + x) / (2 * x), 28, [|256...|], [-131/32768,
110// 131/32768], fixed);
111// > dirtyinfnorm(log2(1 + x) - 2 * x * P, [-131/32768, 131/32768]);
112// 0x1.f78ee...p-271 < 2^-270.
113//
114// Coefficients are stored in 3 precision tiers matching their Horner stages:
115// - Degrees 0..7 in Frac256 (lsb = 2^-256)
116// - Degrees 8..16 in Frac128 (lsb = 2^-128)
117// - Degrees 17..28 in Frac64 (lsb = 2^-64)
118LIBC_INLINE_VAR constexpr Frac256 LOG2_POLY_256[8] = {
119 // lsb = 2^-256
120 Frac256({0x8b25166cd1a13248ULL, 0xeb577aa8dd695a58ULL,
121 0xbe87fed0691d3e88ULL, 0xb8aa3b295c17f0bbULL}), // a_0
122 Frac256({0x45928b3668d0990fULL, 0x75abbd546eb4ad2cULL,
123 0xdf43ff68348e9f44ULL, 0x5c551d94ae0bf85dULL}), // a_1
124 Frac256({0x2e61b22445ceb3f3ULL, 0x4e727e3849cdc8c8ULL,
125 0x3f82aa45785f14d8ULL, 0x3d8e13b87407fae9ULL}), // a_2
126 Frac256({0x22c9459b3f6eb564ULL, 0x3ad5deaa375a5696ULL,
127 0xefa1ffb41a474fa2ULL, 0x2e2a8eca5705fc2eULL}), // a_3
128 Frac256({0x4f076da17511bc00ULL, 0x2f117eee92aeababULL,
129 0x594e6629ae9f72e8ULL, 0x24eed8a1df37fcf2ULL}), // a_4
130 Frac256({0x172f21933a77f0c1ULL, 0x27393f1c24e6e464ULL,
131 0x9fc15522bc2f8a6cULL, 0x1ec709dc3a03fd74ULL}), // a_5
132 Frac256({0x05837685e5671b1aULL, 0x219ec86144339f31ULL,
133 0x645c921dc5df9b38ULL, 0x1a61762a7aded93fULL}), // a_6
134 Frac256({0xfa3f8f34cb3f2ee5ULL, 0x1d6aef551bad2b6aULL,
135 0x77d0ffda0d23a7d1ULL, 0x171547652b82fe17ULL}), // a_7
136};
137
138LIBC_INLINE_VAR constexpr Frac128 LOG2_POLY_128[9] = {
139 // lsb = 2^-128
140 Frac128({0x6a80e36c7d7506f2ULL, 0x1484b13d7c02a8f8ULL}), // a_8
141 Frac128({0x2ca73314d74fb974ULL, 0x12776c50ef9bfe79ULL}), // a_9
142 Frac128({0x5723a2cd20d41cf5ULL, 0x10c9a84994022d28ULL}), // a_10
143 Frac128({0x4fe0aa915e17c536ULL, 0x0f6384ee1d01febaULL}), // a_11
144 Frac128({0x711e274b1bc72c31ULL, 0x0e347ab4698bb00eULL}), // a_12
145 Frac128({0xb22e490ee2efcd9bULL, 0x0d30bb153d6f6c9fULL}), // a_13
146 Frac128({0x731a220de4dfd03eULL, 0x0c4f9d8b4a67fefbULL}), // a_14
147 Frac128({0xbbe87fed0692488aULL, 0x0b8aa3b295c17f0bULL}), // a_15
148 Frac128({0xa1cbc3b1e9a2722bULL, 0x0adcd64dba1f86a1ULL}), // a_16
149};
150
151LIBC_INLINE_VAR constexpr Frac64 LOG2_POLY_64[12] = {
152 // lsb = 2^-64
153 Frac64(0x0a42589ebe01547cULL), // a_17
154 Frac64(0x09b81e0fa687ff32ULL), // a_18
155 Frac64(0x093bb62877cdff3cULL), // a_19
156 Frac64(0x08cb27637e4a486aULL), // a_20
157 Frac64(0x0864d424ca011692ULL), // a_21
158 Frac64(0x080766bf04010878ULL), // a_22
159 Frac64(0x07b1c2770e823fbfULL), // a_23
160 Frac64(0x0762f82060d60050ULL), // a_24
161 Frac64(0x071a3d5995afd976ULL), // a_25
162 Frac64(0x06d6e5744c41469bULL), // a_26
163 Frac64(0x06988c480b11e361ULL), // a_27
164 Frac64(0x06681a21fa0d204cULL), // a_28
165};
166
167// Polynomial coefficients c_k ~ (log(2))^(k+1) / (k+1)! for 2^u - 1 = u * P(u)
168// on |u| < 2^-7.29, stored in 2 precision tiers:
169// - Degrees 0..9 in Frac256 (lsb = 2^-256)
170// - Degrees 10..19 in Frac128 (lsb = 2^-128)
171LIBC_INLINE_VAR constexpr Frac256 EXP2_POLY_256[10] = {
172 // lsb = 2^-256
173 Frac256({0x8a0d175b8baafa2cULL, 0x40f343267298b62dULL,
174 0xc9e3b39803f2f6afULL, 0xb17217f7d1cf79abULL}), // c_0
175 Frac256({0x857d27776272dcddULL, 0x4744ea38619cd3a9ULL,
176 0xde2d60dd92e6bf95ULL, 0x3d7f7bff058b1d50ULL}), // c_1
177 Frac256({0x8ea63315bc46c28dULL, 0x4f5c47444da0110eULL,
178 0x99d3b15d995e96f7ULL, 0x0e35846b82505fc5ULL}), // c_2
179 Frac256({0xd336e12d33c302bfULL, 0xe48f1d4a7cc7223aULL,
180 0x39977c16a7dd58a0ULL, 0x0276556df749cee5ULL}), // c_3
181 Frac256({0x919b86d5480c127eULL, 0xc15db29a5b9c65c3ULL,
182 0x41c5fda69452fb0cULL, 0x005761ff9e299cc4ULL}), // c_4
183 Frac256({0xa92b25fedad56f0dULL, 0x9f6629ff9988f760ULL,
184 0xb7a58544c3591a0fULL, 0x000a184897c363c3ULL}), // c_5
185 Frac256({0xba623264ff59063bULL, 0x959c22a5d1021fdcULL,
186 0x34358a8e643ec734ULL, 0x0000ffe5fe2c4586ULL}), // c_6
187 Frac256({0xfab6439a0b2d00d1ULL, 0x4b0dc341ee20f572ULL,
188 0x23fd8ffe606da77cULL, 0x0000162c0223a5c8ULL}), // c_7
189 Frac256({0xe715fa54922e6ef4ULL, 0x08a319719553744cULL,
190 0x7c3da4a70e5a4ff9ULL, 0x000001b5253d395eULL}), // c_8
191 Frac256({0x308d164959a6077dULL, 0x699c540c1142cae1ULL,
192 0x8ec9f6fda1d952e7ULL, 0x0000001e4cf5158bULL}), // c_9
193};
194
195LIBC_INLINE_VAR constexpr Frac128 EXP2_POLY_128[10] = {
196 // lsb = 2^-128
197 Frac128({0x1bb24c0f57995e47ULL, 0x00000001e8cac735ULL}), // c_10
198 Frac128({0xfc2985e2b5687e18ULL, 0x000000001c3bd650ULL}), // c_11
199 Frac128({0x166d0f96281ac301ULL, 0x0000000001816193ULL}), // c_12
200 Frac128({0x4d5878a973f14362ULL, 0x0000000000131496ULL}), // c_13
201 Frac128({0x421d82010f33d8acULL, 0x000000000000e1b7ULL}), // c_14
202 Frac128({0x44d73cfc59c91c7fULL, 0x00000000000009c7ULL}), // c_15
203 Frac128({0x1112d070969f5587ULL, 0x0000000000000066ULL}), // c_16
204 Frac128({0xee2ed7b686d2bae6ULL, 0x0000000000000003ULL}), // c_17
205 Frac128({0x24b4fd9706b8c9b6ULL, 0x0000000000000000ULL}), // c_18
206 Frac128({0x0145acc4b5051358ULL, 0x0000000000000000ULL}), // c_19
207};
208
209// Exact 2-step integer range reduction for m_x = 1 + x_mant * 2^-52 in [1, 2):
210// idx1 = round(x_mant * 2^-48) in [0, 16], r1 = RD_SMALL_K[idx1] * 2^-6
211// d1 = r1 * m_x - 1 = (mant_x * RD_SMALL_K[idx1] - 2^58) * 2^-58
212// k2 = round(d1 * 2^7) in [-4, 4], r2 = (128 - k2) * 2^-7
213// dx = r1 * r2 * m_x - 1 = dx_int * 2^-65, with |dx| < 2^-7.96.
214LIBC_INLINE int64_t log2_range_reduce(uint64_t x_mant, unsigned &idx1,
215 int &k2) {
216 uint64_t mant_x = x_mant | (1ULL << 52); // lsb = 2^-52
217 idx1 = static_cast<unsigned>((x_mant + (1ULL << 47)) >> 48);
218 int64_t d1 = static_cast<int64_t>(mant_x * RD_SMALL_K[idx1]) -
219 (1LL << 58); // lsb = 2^-58
220 k2 = static_cast<int>((d1 + (1LL << 50)) >> 51); // lsb = 2^-7
221 return static_cast<int64_t>((static_cast<uint64_t>(d1) << 7) -
222 (static_cast<uint64_t>(k2) << 58)) -
223 d1 * k2; // lsb = 2^-65
224}
225
226// Multiply a in-place by 64-bit b and return the high 64-bit word.
227template <size_t N>
228LIBC_ALWAYS_INLINE uint64_t mul_uint64(UInt<N> &a, uint64_t b) {
229 uint64_t carry = 0;
230 for (size_t i = 0; i < N / 64; ++i) {
231 auto prod = multiword::mul2(a.val[i], b);
232 uint64_t c = 0;
233 a.val[i] = add_with_carry<uint64_t>(prod[0], carry, 0, c);
234 carry = prod[1] + c;
235 }
236 return carry;
237}
238
239// Construct a normalized DyadicFloat<N> from a mantissa whose MSB is at bit
240// N - 1 or N - 2 (at most a 1-bit left shift).
241template <size_t N>
242LIBC_ALWAYS_INLINE fputil::DyadicFloat<N> df_norm_1bit(Sign sign, int exp,
243 const UInt<N> &m) {
244 fputil::DyadicFloat<N> r;
245 r.sign = sign;
246 if (m.val[N / 64 - 1] >> 63) {
247 r.exponent = exp;
248 r.mantissa = m;
249 } else {
250 r.exponent = exp - 1;
251 r.mantissa = m + m;
252 }
253 return r;
254}
255
256// Convert an int to a normalized DyadicFloat<N>.
257template <size_t N>
258LIBC_ALWAYS_INLINE fputil::DyadicFloat<N> df_from_int(int x) {
259 fputil::DyadicFloat<N> r;
260 r.mantissa = UInt<N>(0);
261 if (LIBC_UNLIKELY(x == 0)) {
262 r.sign = Sign::POS;
263 r.exponent = 0;
264 return r;
265 }
266 uint32_t m = static_cast<uint32_t>(x < 0 ? -static_cast<int64_t>(x) : x);
267 int lz = cpp::countl_zero(value: m);
268 r.sign = (x < 0) ? Sign::NEG : Sign::POS;
269 r.exponent = 31 - lz - static_cast<int>(N - 1);
270 r.mantissa.val[N / 64 - 1] = static_cast<uint64_t>(m) << (lz + 32);
271 return r;
272}
273
274// Combine integer exponent x_e and fractional mantissa log2_m in (0, 1)
275// (lsb = 2^-(N - 1)) into a normalized DyadicFloat<N>.
276template <size_t N>
277LIBC_INLINE fputil::DyadicFloat<N> combine_log2_df(int x_e,
278 const UInt<N> &log2_m) {
279 Sign sign = Sign::POS;
280 uint32_t m = static_cast<uint32_t>(x_e);
281 UInt<N> frac = log2_m;
282 if (x_e < 0) {
283 sign = Sign::NEG;
284 m = static_cast<uint32_t>(-x_e - 1);
285 frac = (UInt<N>(1) << (N - 1)) - log2_m;
286 }
287
288 fputil::DyadicFloat<N> r;
289 r.sign = sign;
290 if (m == 0) {
291 // Near-1.0 inputs already returned early, so frac > 2^(N - 9) and lz is
292 // strictly in [1, 8].
293 int lz = cpp::countl_zero(frac.val[N / 64 - 1]);
294 int rsh = 64 - lz;
295 r.exponent = -static_cast<int>(N - 1) - lz;
296 r.mantissa.val[0] = frac.val[0] << lz;
297 LIBC_LOOP_NOUNROLL
298 for (size_t i = 1; i < N / 64; ++i)
299 r.mantissa.val[i] = (frac.val[i] << lz) | (frac.val[i - 1] >> rsh);
300 return r;
301 }
302 int bw = 32 - cpp::countl_zero(value: m);
303 r.exponent = -static_cast<int>(N) + bw;
304 if (bw == 1) {
305 r.mantissa = frac;
306 r.mantissa.val[N / 64 - 1] |= 1ULL << 63;
307 return r;
308 }
309 int shr = bw - 1;
310 int shl = 64 - shr;
311 LIBC_LOOP_NOUNROLL
312 for (size_t i = 0; i < N / 64 - 1; ++i)
313 r.mantissa.val[i] = (frac.val[i] >> shr) | (frac.val[i + 1] << shl);
314 r.mantissa.val[N / 64 - 1] =
315 (frac.val[N / 64 - 1] >> shr) | (static_cast<uint64_t>(m) << (64 - bw));
316 return r;
317}
318
319// Accurate log2(x) in 256-bit precision using 2-step integer range reduction:
320// x = 2^x_e * m_x, with 1 <= m_x < 2
321// log2(x) = x_e + (-log2(r1)) + (-log2(r2)) + log2(1 + dx).
322// log2(1 + dx) is evaluated with a degree-28 minimax polynomial using a 3-tier
323// Horner scheme (Frac64, Frac128, and Frac256).
324LIBC_COLD LIBC_INLINE DFloat256 log2_f256(int x_e, uint64_t x_mant) {
325 if (LIBC_UNLIKELY(x_mant == 0))
326 return df_from_int<256>(x: x_e);
327
328 unsigned idx1 = 0;
329 int k2 = 0;
330 int64_t dx_int = log2_range_reduce(x_mant, idx1, k2); // lsb = 2^-65
331 bool dx_is_neg = (dx_int < 0);
332 uint64_t abs_dx =
333 static_cast<uint64_t>(dx_is_neg ? -dx_int : dx_int); // lsb = 2^-65
334
335 Frac64 y64(abs_dx >> 1); // lsb = 2^-64
336 Frac128 y128({abs_dx << 63, abs_dx >> 1}); // lsb = 2^-128
337 Frac256 y({0, 0, abs_dx << 63, abs_dx >> 1}); // lsb = 2^-256
338
339 // Step 1: 64-bit evaluation for degrees 17..28 (|dx|^17 < 2^-135.4):
340 Frac64 p64 = LOG2_POLY_64[11]; // lsb = 2^-64
341 LIBC_LOOP_NOUNROLL
342 for (int k = 10; k >= 0; --k) {
343 Frac64 py = p64 * y64;
344 p64 = dx_is_neg ? (LOG2_POLY_64[k] + py)
345 : (LOG2_POLY_64[k] - py); // lsb = 2^-64
346 }
347
348 // Step 2: 128-bit evaluation for degrees 8..16 (|dx|^8 < 2^-63.7):
349 Frac128 p128({0, p64.val[0]}); // lsb = 2^-128
350 LIBC_LOOP_NOUNROLL
351 for (int k = 8; k >= 0; --k) {
352 Frac128 py = p128 * y128;
353 p128 = dx_is_neg ? (LOG2_POLY_128[k] + py)
354 : (LOG2_POLY_128[k] - py); // lsb = 2^-128
355 }
356
357 // Step 3: 256-bit evaluation for degrees 0..7:
358 Frac256 p({0, 0, p128.val[0], p128.val[1]}); // lsb = 2^-256
359 LIBC_LOOP_NOUNROLL
360 for (int k = 7; k >= 0; --k) {
361 Frac256 py = p * y;
362 p = dx_is_neg ? (LOG2_POLY_256[k] + py)
363 : (LOG2_POLY_256[k] - py); // lsb = 2^-256
364 }
365
366 // Normalize abs_dx before multiplying by p so near-1.0 inputs (x_e - log2(r)
367 // == 0) retain full 256-bit precision without shifting out low bits.
368 int lz = cpp::countl_zero(value: abs_dx);
369 uint64_t norm_dx = abs_dx << lz; // lsb = 2^-(65 + lz)
370 Frac256 norm_log2_1p = Frac256({0, 0, 0, norm_dx}) * p; // lsb = 2^-(256 + lz)
371 if (LIBC_UNLIKELY((x_e == 0 && idx1 == 0 && k2 == 0) ||
372 (x_e == -1 && idx1 == 16 && k2 == 0))) {
373 return df_norm_1bit<256>(sign: dx_is_neg ? Sign::NEG : Sign::POS, exp: -256 - lz,
374 m: UInt<256>(norm_log2_1p.val));
375 }
376
377 Frac256 log2_1p = norm_log2_1p >> static_cast<size_t>(lz + 1); // lsb = 2^-255
378 Frac256 log2_rd =
379 LOG2_R1_FRAC256[idx1] + LOG2_R2_FRAC256[k2 + 4]; // lsb = 2^-255
380 Frac256 log2_m =
381 dx_is_neg ? (log2_rd - log2_1p) : (log2_rd + log2_1p); // lsb = 2^-255
382
383 return combine_log2_df<256>(x_e, log2_m: UInt<256>(log2_m.val));
384}
385
386// Accurate 2^z in 256-bit precision reusing LOG2_R1_FRAC256 and LOG2_R2_FRAC256
387// for range reduction:
388// z = hi - f, with hi = ceil(z) and f in [0, 1)
389// f ~ -log2(R_1[idx1] * R_2[k2])
390// u = (-log2(R_1[idx1]) - log2(R_2[k2])) - f, with |u| < 2^-7.29.
391// Then:
392// 2^z = 2^(hi - 13) * (RD_SMALL_K[idx1] * (128 - k2)) * 2^u.
393LIBC_COLD LIBC_INLINE DFloat256 exp2_f256(const DFloat256 &z) {
394 // Callers guarantee 2^-54 <= |z| < 1076 < 2^11, so e in [-54, 10].
395 int e = z.exponent + 255;
396 int int_z = 0;
397 UInt<256> frac_z;
398 const auto &m = z.mantissa.val;
399 if (e > 0) {
400 int shr = 64 - e;
401 int_z = static_cast<int>(m[3] >> (shr - 1));
402 frac_z = UInt<256>({m[0] << e, (m[1] << e) | (m[0] >> shr),
403 (m[2] << e) | (m[1] >> shr),
404 ((m[3] << e) | (m[2] >> shr)) &
405 0x7fff'ffff'ffff'ffffULL}); // lsb = 2^-255
406 } else if (e == 0) {
407 int_z = 1;
408 frac_z = UInt<256>(
409 {m[0], m[1], m[2], m[3] & 0x7fff'ffff'ffff'ffffULL}); // lsb = 2^-255
410 } else {
411 int shr = -e;
412 int shl = 64 - shr;
413 frac_z =
414 UInt<256>({(m[0] >> shr) | (m[1] << shl), (m[1] >> shr) | (m[2] << shl),
415 (m[2] >> shr) | (m[3] << shl), m[3] >> shr}); // lsb = 2^-255
416 }
417
418 int hi = -int_z;
419 Frac256 f(frac_z.val); // lsb = 2^-255
420 if (z.sign != Sign::NEG) {
421 if (frac_z.is_zero()) {
422 hi = int_z;
423 } else {
424 hi = int_z + 1;
425 f = Frac256(((UInt<256>(1) << 255) - frac_z).val);
426 }
427 }
428
429 // Direct integer index approximation for idx1 = round(16 * (2^f - 1)) in
430 // [0, 16] and k2 = round((f + log2(R_1[idx1])) * 128 * ln(2)) in [-4, 4]:
431 uint64_t q = f.val[3] >> 47; // lsb = 2^-16
432 uint64_t p2 = 15512 + ((q * 4561) >> 16);
433 uint64_t p1 = 45462 + ((q * p2) >> 16);
434 unsigned idx1 = static_cast<unsigned>((q * p1 + (1ULL << 27)) >> 28);
435
436 int64_t rem_hi =
437 static_cast<int64_t>(f.val[3] - LOG2_R1_FRAC256[idx1].val[3]);
438 int k2 = static_cast<int>(((rem_hi >> 32) * 5814539LL + (1LL << 46)) >> 47);
439 if (k2 < -4)
440 k2 = -4;
441 if (k2 > 4)
442 k2 = 4;
443
444 Frac256 log2_rd =
445 LOG2_R1_FRAC256[idx1] + LOG2_R2_FRAC256[k2 + 4]; // lsb = 2^-255
446 Frac256 u_signed = log2_rd - f; // lsb = 2^-255
447 bool u_is_neg = (u_signed.val[3] >> 63) != 0;
448 Frac256 abs_u = u_is_neg ? (Frac256(0) - u_signed) : u_signed;
449 Frac256 u = abs_u << 1; // lsb = 2^-256
450
451 // Step 1: 128-bit evaluation for degrees 10..19:
452 Frac128 u128 = u.to_frac128(); // lsb = 2^-128
453 Frac128 p128 = EXP2_POLY_128[9]; // lsb = 2^-128
454 LIBC_LOOP_NOUNROLL
455 for (int i = 8; i >= 0; --i) {
456 Frac128 pu = p128 * u128;
457 p128 = u_is_neg ? (EXP2_POLY_128[i] - pu)
458 : (EXP2_POLY_128[i] + pu); // lsb = 2^-128
459 }
460
461 // Step 2: 256-bit evaluation for degrees 0..9:
462 Frac256 p({0, 0, p128.val[0], p128.val[1]}); // lsb = 2^-256
463 LIBC_LOOP_NOUNROLL
464 for (int i = 9; i >= 0; --i) {
465 Frac256 pu = p * u;
466 p = u_is_neg ? (EXP2_POLY_256[i] - pu)
467 : (EXP2_POLY_256[i] + pu); // lsb = 2^-256
468 }
469
470 // Reconstruction:
471 // 2^z = 2^(hi - 13) * m_int * (1 +- t)
472 // = 2^hi * (m_int * 2^-13) * (1 +- t).
473 Frac256 t = u * p; // lsb = 2^-256
474 uint64_t m_int =
475 static_cast<uint64_t>(RD_SMALL_K[idx1]) * static_cast<uint64_t>(128 - k2);
476 UInt<256> m_256({0, 0, 0, m_int << 50}); // lsb = 2^-255
477 Frac256 mt = Frac256(m_256.val) * t; // lsb = 2^-255
478 UInt<256> m_final = u_is_neg ? (m_256 - UInt<256>(mt.val))
479 : (m_256 + UInt<256>(mt.val)); // lsb = 2^-255
480
481 return df_norm_1bit<256>(sign: Sign::POS, exp: hi - 255, m: m_final);
482}
483
484// Accurate pow(x, y) evaluating z = y * log2(x) and 2^z in 256-bit precision,
485// folded with sticky bit into a normalized DyadicFloat<128> for rounding.
486LIBC_COLD LIBC_NOINLINE LIBC_INLINE fputil::DyadicFloat<128>
487pow_accurate_256(Sign y_sign, int exp_y, uint64_t mant_y, bool is_neg, int x_e,
488 uint64_t x_mant) {
489 DFloat256 log2_x = log2_f256(x_e, x_mant);
490 uint64_t z_hi = mul_uint64(a&: log2_x.mantissa, b: mant_y);
491 const auto &lm = log2_x.mantissa.val;
492
493 DFloat256 z;
494 z.sign = (y_sign == log2_x.sign) ? Sign::POS : Sign::NEG;
495 if (z_hi >> 63) {
496 z.exponent = log2_x.exponent + exp_y + 1;
497 z.mantissa = UInt<256>({lm[1], lm[2], lm[3], z_hi});
498 } else {
499 z.exponent = log2_x.exponent + exp_y;
500 z.mantissa =
501 UInt<256>({(lm[1] << 1) | (lm[0] >> 63), (lm[2] << 1) | (lm[1] >> 63),
502 (lm[3] << 1) | (lm[2] >> 63), (z_hi << 1) | (lm[3] >> 63)});
503 }
504
505 DFloat256 r = exp2_f256(z);
506 fputil::DyadicFloat<128> r128;
507 r128.sign = is_neg ? Sign::NEG : Sign::POS;
508 r128.exponent = r.exponent + 128;
509 uint64_t sticky = (r.mantissa.val[0] | r.mantissa.val[1]) != 0;
510 r128.mantissa = UInt<128>({r.mantissa.val[2] | sticky, r.mantissa.val[3]});
511 return r128;
512}
513
514} // namespace pow_internal
515} // namespace math
516} // namespace LIBC_NAMESPACE_DECL
517
518#endif // LLVM_LIBC_SRC___SUPPORT_MATH_POW_ACCURATE_256_H
519