| 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 | |
| 31 | namespace LIBC_NAMESPACE_DECL { |
| 32 | namespace math { |
| 33 | namespace pow_internal { |
| 34 | |
| 35 | using 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. |
| 39 | LIBC_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. |
| 79 | LIBC_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) |
| 118 | LIBC_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 | |
| 138 | LIBC_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 | |
| 151 | LIBC_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) |
| 171 | LIBC_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 | |
| 195 | LIBC_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. |
| 214 | LIBC_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. |
| 227 | template <size_t N> |
| 228 | LIBC_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). |
| 241 | template <size_t N> |
| 242 | LIBC_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>. |
| 257 | template <size_t N> |
| 258 | LIBC_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>. |
| 276 | template <size_t N> |
| 277 | LIBC_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). |
| 324 | LIBC_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. |
| 393 | LIBC_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. |
| 486 | LIBC_COLD LIBC_NOINLINE LIBC_INLINE fputil::DyadicFloat<128> |
| 487 | pow_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 | |