439 lines · cpp
1//===-- Implementation of sqrtf128 function -------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "src/math/sqrtf128.h"10#include "src/__support/CPP/bit.h"11#include "src/__support/FPUtil/FEnvImpl.h"12#include "src/__support/FPUtil/FPBits.h"13#include "src/__support/FPUtil/rounding_mode.h"14#include "src/__support/common.h"15#include "src/__support/macros/optimization.h"16#include "src/__support/uint128.h"17 18// Compute sqrtf128 with correct rounding for all rounding modes using integer19// arithmetic by Alexei Sibidanov (sibid@uvic.ca):20// https://github.com/sibidanov/llvm-project/tree/as_sqrt_v221// https://github.com/sibidanov/llvm-project/tree/as_sqrt_v322// TODO: Update the reference once Alexei's implementation is in the CORE-MATH23// project. https://github.com/llvm/llvm-project/issues/12679424 25// Let the input be expressed as x = 2^e * m_x,26// - Step 1: Range reduction27// Let x_reduced = 2^(e % 2) * m_x,28// Then sqrt(x) = 2^(e / 2) * sqrt(x_reduced), with29// 1 <= x_reduced < 4.30// - Step 2: Polynomial approximation31// Approximate 1/sqrt(x_reduced) using polynomial approximation with the32// result errors bounded by:33// |r0 - 1/sqrt(x_reduced)| < 2^-32.34// The computations are done in uint64_t.35// - Step 3: First Newton iteration36// Let the scaled error defined by:37// h0 = r0^2 * x_reduced - 1.38// Then we compute the first Newton iteration:39// r1 = r0 - r0 * h0 / 2.40// The result is then bounded by:41// |r1 - 1 / sqrt(x_reduced)| < 2^-62.42// - Step 4: Second Newton iteration43// We calculate the scaled error from Step 3:44// h1 = r1^2 * x_reduced - 1.45// Then the second Newton iteration is computed by:46// r2 = x_reduced * (r1 - r1 * h0 / 2)47// ~ x_reduced * (1/sqrt(x_reduced)) = sqrt(x_reduced)48// - Step 5: Perform rounding test and correction if needed.49// Rounding correction is done by computing the exact rounding errors:50// x_reduced - r2^2.51 52namespace LIBC_NAMESPACE_DECL {53 54using FPBits = fputil::FPBits<float128>;55 56namespace {57 58template <typename T, typename U = T> static inline constexpr T prod_hi(T, U);59 60// Get high part of integer multiplications.61// Use template to prevent implicit conversion.62template <>63inline constexpr uint64_t prod_hi<uint64_t>(uint64_t x, uint64_t y) {64 return static_cast<uint64_t>(65 (static_cast<UInt128>(x) * static_cast<UInt128>(y)) >> 64);66}67 68// Get high part of unsigned 128x64 bit multiplication.69template <>70inline constexpr UInt128 prod_hi<UInt128, uint64_t>(UInt128 x, uint64_t y) {71 uint64_t x_lo = static_cast<uint64_t>(x);72 uint64_t x_hi = static_cast<uint64_t>(x >> 64);73 UInt128 xyl = static_cast<UInt128>(x_lo) * static_cast<UInt128>(y);74 UInt128 xyh = static_cast<UInt128>(x_hi) * static_cast<UInt128>(y);75 return xyh + (xyl >> 64);76}77 78// Get high part of signed 64x64 bit multiplication.79template <> inline constexpr int64_t prod_hi<int64_t>(int64_t x, int64_t y) {80 return static_cast<int64_t>(81 (static_cast<Int128>(x) * static_cast<Int128>(y)) >> 64);82}83 84// Get high 128-bit part of unsigned 128x128 bit multiplication.85template <> inline constexpr UInt128 prod_hi<UInt128>(UInt128 x, UInt128 y) {86 uint64_t x_lo = static_cast<uint64_t>(x);87 uint64_t x_hi = static_cast<uint64_t>(x >> 64);88 uint64_t y_lo = static_cast<uint64_t>(y);89 uint64_t y_hi = static_cast<uint64_t>(y >> 64);90 91 UInt128 xh_yh = static_cast<UInt128>(x_hi) * static_cast<UInt128>(y_hi);92 UInt128 xh_yl = static_cast<UInt128>(x_hi) * static_cast<UInt128>(y_lo);93 UInt128 xl_yh = static_cast<UInt128>(x_lo) * static_cast<UInt128>(y_hi);94 95 xh_yh += xh_yl >> 64;96 97 return xh_yh + (xl_yh >> 64);98}99 100// Get high 128-bit part of mixed sign 128x128 bit multiplication.101template <>102inline constexpr Int128 prod_hi<Int128, UInt128>(Int128 x, UInt128 y) {103 UInt128 mask = static_cast<UInt128>(x >> 127);104 UInt128 negative_part = y & mask;105 UInt128 prod = prod_hi(static_cast<UInt128>(x), y);106 return static_cast<Int128>(prod - negative_part);107}108 109// Newton-Raphson first order step to improve accuracy of the result.110// For the initial approximation r0 ~ 1/sqrt(x), let111// h = r0^2 * x - 1112// be its scaled error. Then the first-order Newton-Raphson iteration is:113// r1 = r0 - r0 * h / 2114// which has error bounded by:115// |r1 - 1/sqrt(x)| < h^2 / 2.116LIBC_INLINE uint64_t rsqrt_newton_raphson(uint64_t m, uint64_t r) {117 uint64_t r2 = prod_hi(r, r);118 // h = r0^2*x - 1.119 int64_t h = static_cast<int64_t>(prod_hi(m, r2) + r2);120 // hr = r * h / 2121 int64_t hr = prod_hi(h, static_cast<int64_t>(r >> 1));122 return r - hr;123}124 125#ifdef LIBC_MATH_HAS_SMALL_TABLES126// Degree-12 minimax polynomials for 1/sqrt(x) on [1, 2].127constexpr uint32_t RSQRT_COEFFS[12] = {128 0xb5947a4a, 0x2d651e32, 0x9ad50532, 0x2d28d093, 0x0d8be653, 0x04239014,129 0x01492449, 0x0066ff7d, 0x001e74a1, 0x000984cc, 0x00049abc, 0x00018340,130};131 132LIBC_INLINE uint64_t rsqrt_approx(uint64_t m) {133 int64_t x = static_cast<uint64_t>(m) ^ (uint64_t(1) << 63);134 int64_t x_26 = x >> 2;135 int64_t z = x >> 31;136 137 if (LIBC_UNLIKELY(z <= -4294967296))138 return ~(m >> 1);139 140 uint64_t x2 = static_cast<uint64_t>(z) * static_cast<uint64_t>(z);141 uint64_t x2_26 = x2 >> 5;142 x2 >>= 32;143 // Calculate the odd part of the polynomial using Horner's method.144 uint64_t c0 = RSQRT_COEFFS[8] + ((x2 * RSQRT_COEFFS[10]) >> 32);145 uint64_t c1 = RSQRT_COEFFS[6] + ((x2 * c0) >> 32);146 uint64_t c2 = RSQRT_COEFFS[4] + ((x2 * c1) >> 32);147 uint64_t c3 = RSQRT_COEFFS[2] + ((x2 * c2) >> 32);148 uint64_t c4 = RSQRT_COEFFS[0] + ((x2 * c3) >> 32);149 uint64_t odd =150 static_cast<uint64_t>((x >> 34) * static_cast<int64_t>(c4 >> 3)) + x_26;151 // Calculate the even part of the polynomial using Horner's method.152 uint64_t d0 = RSQRT_COEFFS[9] + ((x2 * RSQRT_COEFFS[11]) >> 32);153 uint64_t d1 = RSQRT_COEFFS[7] + ((x2 * d0) >> 32);154 uint64_t d2 = RSQRT_COEFFS[5] + ((x2 * d1) >> 32);155 uint64_t d3 = RSQRT_COEFFS[3] + ((x2 * d2) >> 32);156 uint64_t d4 = RSQRT_COEFFS[1] + ((x2 * d3) >> 32);157 uint64_t even = 0xd105eb806655d608ul + ((x2 * d4) >> 6) + x2_26;158 159 uint64_t r = even - odd; // error < 1.5e-10160 // Newton-Raphson first order step to improve accuracy of the result to almost161 // 64 bits.162 return rsqrt_newton_raphson(m, r);163}164 165#else166// Cubic minimax polynomials for 1/sqrt(x) on [1 + k/64, 1 + (k + 1)/64]167// for k = 0..63.168constexpr uint32_t RSQRT_COEFFS[64][4] = {169 {0xffffffff, 0xfffff780, 0xbff55815, 0x9bb5b6e7},170 {0xfc0bd889, 0xfa1d6e7d, 0xb8a95a89, 0x938bf8f0},171 {0xf82ec882, 0xf473bea9, 0xb1bf4705, 0x8bed0079},172 {0xf467f280, 0xeefff2a1, 0xab309d4a, 0x84cdb431},173 {0xf0b6848c, 0xe9bf46f4, 0xa4f76232, 0x7e24037b},174 {0xed19b75e, 0xe4af2628, 0x9f0e1340, 0x77e6ca62},175 {0xe990cdad, 0xdfcd2521, 0x996f9b96, 0x720db8df},176 {0xe61b138e, 0xdb16ffde, 0x94174a00, 0x6c913cff},177 {0xe2b7dddf, 0xd68a967b, 0x8f00c812, 0x676a6f92},178 {0xdf6689b7, 0xd225ea80, 0x8a281226, 0x62930308},179 {0xdc267bea, 0xcde71c63, 0x8589702c, 0x5e05343e},180 {0xd8f7208e, 0xc9cc6948, 0x81216f2e, 0x59bbbcf8},181 {0xd5d7ea91, 0xc5d428ee, 0x7cecdb76, 0x55b1c7d6},182 {0xd2c8534e, 0xc1fccbc9, 0x78e8bb45, 0x51e2e592},183 {0xcfc7da32, 0xbe44d94a, 0x75124a0a, 0x4e4b0369},184 {0xccd6045f, 0xbaaaee41, 0x7166f40f, 0x4ae66284},185 {0xc9f25c5c, 0xb72dbb69, 0x6de45288, 0x47b19045},186 {0xc71c71c7, 0xb3cc040f, 0x6a882804, 0x44a95f5f},187 {0xc453d90f, 0xb0849cd4, 0x67505d2a, 0x41cae1a0},188 {0xc1982b2e, 0xad566a85, 0x643afdc8, 0x3f13625c},189 {0xbee9056f, 0xaa406113, 0x6146361f, 0x3c806169},190 {0xbc46092e, 0xa7418293, 0x5e70506d, 0x3a0f8e8e},191 {0xb9aedba5, 0xa458de58, 0x5bb7b2b1, 0x37bec572},192 {0xb72325b7, 0xa1859022, 0x591adc9a, 0x358c09e2},193 {0xb4a293c2, 0x9ec6bf52, 0x569865a7, 0x33758476},194 {0xb22cd56d, 0x9c1b9e36, 0x542efb6a, 0x31797f8a},195 {0xafc19d86, 0x9983695c, 0x51dd5ffb, 0x2f96647a},196 {0xad60a1d1, 0x96fd66f7, 0x4fa2687c, 0x2dcab91f},197 {0xab099ae9, 0x9488e64b, 0x4d7cfbc9, 0x2c151d8a},198 {0xa8bc441a, 0x92253f20, 0x4b6c1139, 0x2a7449ef},199 {0xa6785b42, 0x8fd1d14a, 0x496eaf82, 0x28e70cc3},200 {0xa43da0ae, 0x8d8e042a, 0x4783eba7, 0x276c4900},201 {0xa20bd701, 0x8b594648, 0x45aae80a, 0x2602f493},202 {0x9fe2c315, 0x89330ce4, 0x43e2d382, 0x24aa16ec},203 {0x9dc22be4, 0x871ad399, 0x422ae88c, 0x2360c7af},204 {0x9ba9da6c, 0x85101c05, 0x40826c88, 0x22262d7b},205 {0x99999999, 0x83126d70, 0x3ee8af07, 0x20f97cd2},206 {0x97913630, 0x81215480, 0x3d5d0922, 0x1fd9f714},207 {0x95907eb8, 0x7f3c62ef, 0x3bdedce0, 0x1ec6e994},208 {0x93974369, 0x7d632f45, 0x3a6d94a9, 0x1dbfacbb},209 {0x91a55615, 0x7b955498, 0x3908a2be, 0x1cc3a33b},210 {0x8fba8a1c, 0x79d2724e, 0x37af80bf, 0x1bd23960},211 {0x8dd6b456, 0x781a2be4, 0x3661af39, 0x1aeae458},212 {0x8bf9ab07, 0x766c28ba, 0x351eb539, 0x1a0d21a2},213 {0x8a2345cc, 0x74c813dd, 0x33e61feb, 0x19387676},214 {0x88535d90, 0x732d9bdc, 0x32b7823a, 0x186c6f3e},215 {0x8689cc7e, 0x719c7297, 0x3192747d, 0x17a89f21},216 {0x84c66df1, 0x70144d19, 0x30769424, 0x16ec9f89},217 {0x83091e6a, 0x6e94e36c, 0x2f63836f, 0x16380fbf},218 {0x8151bb87, 0x6d1df079, 0x2e58e925, 0x158a9484},219 {0x7fa023f1, 0x6baf31de, 0x2d567053, 0x14e3d7ba},220 {0x7df43758, 0x6a4867d3, 0x2c5bc811, 0x1443880e},221 {0x7c4dd664, 0x68e95508, 0x2b68a346, 0x13a958ab},222 {0x7aace2b0, 0x6791be86, 0x2a7cb871, 0x131500ee},223 {0x79113ebc, 0x66416b95, 0x2997c17a, 0x12863c29},224 {0x777acde8, 0x64f825a1, 0x28b97b82, 0x11fcc95c},225 {0x75e9746a, 0x63b5b822, 0x27e1a6b4, 0x11786b03},226 {0x745d1746, 0x6279f081, 0x2710061d, 0x10f8e6da},227 {0x72d59c46, 0x61449e06, 0x26445f86, 0x107e05ac},228 {0x7152e9f4, 0x601591be, 0x257e7b4d, 0x10079327},229 {0x6fd4e793, 0x5eec9e6b, 0x24be2445, 0x0f955da9},230 {0x6e5b7d16, 0x5dc9986e, 0x24032795, 0x0f273620},231 {0x6ce6931d, 0x5cac55b7, 0x234d5496, 0x0ebcefdb},232 {0x6b7612ec, 0x5b94adb2, 0x229c7cbc, 0x0e56606e},233};234 235// Approximate rsqrt with cubic polynomials.236// The range [1,2] is splitted into 64 equal sub-ranges and the reciprocal237// square root is approximated by a cubic polynomial by the minimax method in238// each subrange. The approximation accuracy fits into 32-33 bits and thus it is239// natural to round coefficients into 32 bit. The constant coefficient can be240// rounded to 33 bits since the most significant bit is always 1 and implicitly241// assumed in the table.242LIBC_INLINE uint64_t rsqrt_approx(uint64_t m) {243 // ULP(m) = 2^-64.244 // Use the top 6 bits as index for looking up polynomial coeffs.245 uint64_t indx = m >> 58;246 247 uint64_t c0 = static_cast<uint64_t>(RSQRT_COEFFS[indx][0]);248 c0 <<= 31; // to 64 bit with the space for the implicit bit249 c0 |= 1ull << 63; // add implicit bit250 251 uint64_t c1 = static_cast<uint64_t>(RSQRT_COEFFS[indx][1]);252 c1 <<= 25; // to 64 bit format253 254 uint64_t c2 = static_cast<uint64_t>(RSQRT_COEFFS[indx][2]);255 uint64_t c3 = static_cast<uint64_t>(RSQRT_COEFFS[indx][3]);256 257 uint64_t d = (m << 6) >> 32; // local coordinate in the subrange [0, 2^32]258 uint64_t d2 = (d * d) >> 32; // square of the local coordinate259 uint64_t re = c0 + (d2 * c2 >> 13); // even part of the polynomial (positive)260 uint64_t ro = d * ((c1 + ((d2 * c3) >> 19)) >> 26) >>261 6; // odd part of the polynomial (negative)262 uint64_t r = re - ro; // maximal error < 1.55e-10 and it is less than 2^-32263 // Newton-Raphson first order step to improve accuracy of the result to almost264 // 64 bits.265 r = rsqrt_newton_raphson(m, r);266 // Adjust in the unlucky case x~1;267 if (LIBC_UNLIKELY(!r))268 --r;269 return r;270}271#endif // LIBC_MATH_HAS_SMALL_TABLES272 273} // anonymous namespace274 275LLVM_LIBC_FUNCTION(float128, sqrtf128, (float128 x)) {276 using FPBits = fputil::FPBits<float128>;277 // Get rounding mode.278 uint32_t rm = fputil::get_round();279 280 FPBits xbits(x);281 UInt128 x_u = xbits.uintval();282 // Bring leading bit of the mantissa to the highest bit.283 // ulp(x_frac) = 2^-128.284 UInt128 x_frac = xbits.get_mantissa() << (FPBits::EXP_LEN + 1);285 286 int sign_exp = static_cast<int>(x_u >> FPBits::FRACTION_LEN);287 288 if (LIBC_UNLIKELY(sign_exp == 0 || sign_exp >= 0x7fff)) {289 // Special cases: NAN, inf, negative numbers290 if (sign_exp >= 0x7fff) {291 // x = -0 or x = inf292 if (xbits.is_zero() || xbits == xbits.inf())293 return x;294 // x is nan295 if (xbits.is_nan()) {296 // pass through quiet nan297 if (xbits.is_quiet_nan())298 return x;299 // transform signaling nan to quiet and return300 return xbits.quiet_nan().get_val();301 }302 // x < 0 or x = -inf303 fputil::set_errno_if_required(EDOM);304 fputil::raise_except_if_required(FE_INVALID);305 return xbits.quiet_nan().get_val();306 }307 // Now x is subnormal or x = +0.308 309 // x is +0.310 if (x_frac == 0)311 return x;312 313 // Normalize subnormal inputs.314 sign_exp = -cpp::countl_zero(x_frac);315 int normal_shifts = 1 - sign_exp;316 x_frac <<= normal_shifts;317 }318 319 // For sign_exp = biased exponent of x = real_exponent + 16383,320 // let f be the real exponent of the output:321 // f = floor(real_exponent / 2)322 // Then:323 // floor((sign_exp + 1) / 2) = f + 8192324 // Hence, the biased exponent of the final result is:325 // f + 16383 = floor((sign_exp + 1) / 2) + 8191.326 // Since the output mantissa will include the hidden bit, we can define the327 // output exponent part:328 // e2 = floor((sign_exp + 1) / 2) + 8190329 unsigned i = static_cast<unsigned>(1 - (sign_exp & 1));330 uint32_t q2 = (sign_exp + 1) >> 1;331 // Exponent of the final result332 uint32_t e2 = q2 + 8190;333 334 constexpr uint64_t RSQRT_2[2] = {~0ull,335 0xb504f333f9de6484 /* 2^64/sqrt(2) */};336 337 // Approximate 1/sqrt(1 + x_frac)338 // Error: |r_1 - 1/sqrt(x)| < 2^-62.339 uint64_t r1 = rsqrt_approx(static_cast<uint64_t>(x_frac >> 64));340 // Adjust for the even/odd exponent.341 uint64_t r2 = prod_hi(r1, RSQRT_2[i]);342 unsigned shift = 2 - i;343 344 // Normalized input:345 // 1 <= x_reduced < 4346 UInt128 x_reduced = (x_frac >> shift) | (UInt128(1) << (126 + i));347 // With r2 ~ 1/sqrt(x) up to 2^-63, we perform another round of Newton-Raphson348 // iteration:349 // r3 = r2 - r2 * h / 2,350 // for h = r2^2 * x - 1.351 // Then:352 // sqrt(x) = x * (1 / sqrt(x))353 // ~ x * r3354 // = x * (r2 - r2 * h / 2)355 // = (x * r2) - (x * r2) * h / 2356 UInt128 sx = prod_hi(x_reduced, r2);357 UInt128 h = prod_hi(sx, r2) << 2;358 UInt128 ds = static_cast<UInt128>(prod_hi(static_cast<Int128>(h), sx));359 UInt128 v = (sx << 1) - ds;360 361 uint32_t nrst = rm == FE_TONEAREST;362 // The result lies within (-2,5) of true square root so we now363 // test that we can correctly round the result taking into account364 // the rounding mode.365 // Check the lowest 14 bits (by clearing and sign-extending the top366 // 32 - 14 = 18 bits).367 int dd = (static_cast<int>(v) << 18) >> 18;368 369 if (LIBC_UNLIKELY(dd < 4 && dd >= -8)) { // can round correctly?370 // m is almost the final result it can be only 1 ulp off so we371 // just need to test both possibilities. We square it and372 // compare with the initial argument.373 UInt128 m = v >> 15;374 UInt128 m2 = m * m;375 // The difference of the squared result and the argument376 Int128 t0 = static_cast<Int128>(m2 - (x_reduced << 98));377 if (t0 == 0) {378 // the square root is exact379 v = m << 15;380 } else {381 // Add +-1 ulp to m depend on the sign of the difference. Here382 // we do not need to square again since (m+1)^2 = m^2 + 2*m +383 // 1 so just need to add shifted m and 1.384 Int128 t1 = t0;385 Int128 sgn = t0 >> 127; // sign of the difference386 Int128 m_xor_sgn = static_cast<Int128>(m << 1) ^ sgn;387 t1 -= m_xor_sgn;388 t1 += Int128(1) + sgn;389 390 Int128 sgn1 = t1 >> 127;391 if (LIBC_UNLIKELY(sgn == sgn1)) {392 t0 = t1;393 v -= sgn << 15;394 t1 -= m_xor_sgn;395 t1 += Int128(1) + sgn;396 }397 398 if (t1 == 0) {399 // 1 ulp offset brings again an exact root400 v = (m - static_cast<UInt128>((sgn << 1) + 1)) << 15;401 } else {402 t1 += t0;403 Int128 side = t1 >> 127; // select what is closer m or m+-1404 v &= ~UInt128(0) << 15; // wipe the fractional bits405 v -= ((sgn & side) | (~sgn & 1)) << (15 + static_cast<int>(side));406 v |= 1; // add sticky bit since we cannot have an exact mid-point407 // situation408 }409 }410 }411 412 unsigned frac = static_cast<unsigned>(v) & 0x7fff; // fractional part413 unsigned rnd; // round bit414 if (LIBC_LIKELY(nrst != 0)) {415 rnd = frac >> 14; // round to nearest tie to even416 } else if (rm == FE_UPWARD) {417 rnd = !!frac; // round up418 } else {419 rnd = 0; // round down or round to zero420 }421 422 v >>= 15; // position mantissa423 v += rnd; // round424 425 // Set inexact flag only if square root is inexact426 // TODO: We will have to raise FE_INEXACT most of the time, but this427 // operation is very costly, especially in x86-64, since technically, it428 // needs to synchronize both SSE and x87 flags. Need to investigate429 // further to see how we can make this performant.430 // https://github.com/llvm/llvm-project/issues/126753431 432 // if(frac) fputil::raise_except_if_required(FE_INEXACT);433 434 v += static_cast<UInt128>(e2) << FPBits::FRACTION_LEN; // place exponent435 return cpp::bit_cast<float128>(v);436}437 438} // namespace LIBC_NAMESPACE_DECL439