1//===-- Implementation header for hypot -------------------------*- C++ -*-===//
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#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_HYPOT_H
10#define LLVM_LIBC_SRC___SUPPORT_MATH_HYPOT_H
11
12#include "hdr/fenv_macros.h"
13#include "hdr/stdint_proxy.h"
14#include "src/__support/FPUtil/FEnvImpl.h"
15#include "src/__support/FPUtil/FPBits.h"
16#include "src/__support/FPUtil/Hypot.h"
17#include "src/__support/FPUtil/double_double.h"
18#include "src/__support/FPUtil/multiply_add.h"
19#include "src/__support/FPUtil/sqrt.h"
20#include "src/__support/macros/attributes.h"
21#include "src/__support/macros/config.h"
22#include "src/__support/macros/optimization.h"
23
24namespace LIBC_NAMESPACE_DECL {
25namespace math {
26
27#ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS
28
29namespace hypot_internal {
30
31// Both input are denormals and non-zero. We scale them up and down by the
32// inverse of the smallest normal number: 2^-1022, so that the correct "hidden"
33// bit position is now 1. And by adding and subtracting 1 from the results, we
34// can emulate the rounding behavior in the denormal range.
35LIBC_INLINE double hypot_denorm(double a, double b) {
36 using fputil::DoubleDouble;
37 constexpr double SCALE = 0x1.0p1022;
38 constexpr double SCALE_BACK = 0x1.0p-1022;
39
40 a *= SCALE;
41 b *= SCALE;
42
43 // See the comments in the main function for the detail explanation of the
44 // computations.
45
46 // sum.hi + sum.lo ~ a^2 + b^2.
47 DoubleDouble a_sq = fputil::exact_mult(a, b: a);
48 DoubleDouble b_sq = fputil::exact_mult(a: b, b);
49 DoubleDouble sum = fputil::exact_add(a: a_sq.hi, b: b_sq.hi);
50 sum.lo += a_sq.lo + b_sq.lo;
51
52 // |sqrt(sum.hi) - r_hi| < 2^-52.
53 double r_hi = fputil::sqrt<double>(x: sum.hi);
54 // r_inv ~ 1 / (2 * r_hi)
55 double r_inv = 0.5 / r_hi;
56 // Adjust correction if needed.
57 DoubleDouble r_h{.lo: 0.0, .hi: r_hi};
58 double correction = 0.0;
59 if (r_hi < 1.0) {
60 // When r_hi < 1, the output is denormal. We mimick rounding in denormal
61 // range with 1.0 + r_hi.
62 r_h = fputil::exact_add(a: 1.0, b: r_hi);
63 correction = 1.0;
64 }
65 // r_hi^2
66 DoubleDouble r_sq = fputil::exact_mult(a: r_hi, b: r_hi);
67 // (hi + lo - r_hi^2)
68 double num_lo = (sum.lo - r_sq.lo) - (r_sq.hi - sum.hi);
69 // (hi + lo - r_hi^2) / (2 * r_hi)
70 double r_lo = fputil::multiply_add(x: num_lo, y: r_inv, z: r_h.lo);
71
72 constexpr double ERR = 0x1.0p-102;
73
74 // Ziv's rounding test.
75 double upper = r_h.hi + (r_lo + ERR);
76 double lower = r_h.hi + (r_lo - ERR);
77
78 if (LIBC_LIKELY(upper == lower)) {
79#ifdef LIBC_MATH_HAS_NO_EXCEPT
80 return (upper - correction) * SCALE_BACK;
81#else
82 // Check to raise underflow correctly.
83 DoubleDouble r = fputil::exact_add(r_h.hi, r_lo);
84 r.hi -= correction;
85 // Raise underflow if needed:
86 if ((r.hi < 1.0 && r.lo != 0.0) || (r.hi == 1.0 && r.lo < 0.0))
87 fputil::raise_underflow_except_if_required<double>();
88
89 return r.hi * SCALE_BACK;
90#endif // LIBC_MATH_HAS_NO_EXCEPT
91 }
92
93 return fputil::hypot(x: a * SCALE_BACK, y: b * SCALE_BACK);
94}
95
96} // namespace hypot_internal
97
98#endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS
99
100LIBC_INLINE double hypot(double x, double y) {
101 using FPBits = fputil::FPBits<double>;
102 using DoubleDouble = fputil::DoubleDouble;
103
104 uint64_t x_u = FPBits(x).uintval();
105 uint64_t y_u = FPBits(y).uintval();
106
107 // Shift the exponent field to the top 11 bits of the lower 32-bit.
108 // Casting it to 32-bit effectively remove the sign bit.
109 uint32_t x_e = static_cast<uint32_t>(x_u >> 31);
110 uint32_t y_e = static_cast<uint32_t>(y_u >> 31);
111
112 // a = maximum_mag(x, y);
113 // b = minimum_mag(x, y);
114 double a, b;
115 uint32_t a_e, b_e;
116
117 if (x_e >= y_e) {
118 a_e = x_e;
119 b_e = y_e;
120 a = x;
121 b = y;
122 } else {
123 a_e = y_e;
124 b_e = x_e;
125 a = y;
126 b = x;
127 }
128
129 double scale = 1.0;
130 double scale_back = 1.0;
131
132 // For a_e, b_e, the top 11 bits are exponent fields.
133 if (LIBC_UNLIKELY(a_e >= ((500U + FPBits::EXP_BIAS) << (32 - 11)))) {
134 // The larger magnitude is above 2^500 (or Inf/NaN), need to scale down to
135 // prevent overflow when squaring.
136 if (a_e >= static_cast<uint32_t>(FPBits::EXP_MASK >> 31)) {
137 // Inf or NaN;
138 FPBits x_bits(x);
139 FPBits y_bits(y);
140 if (x_bits.is_signaling_nan() || y_bits.is_signaling_nan()) {
141 fputil::raise_except_if_required(FE_INVALID);
142 return FPBits::quiet_nan().get_val();
143 }
144 if (x_bits.is_inf() || y_bits.is_inf())
145 return FPBits::inf().get_val();
146 if (x_bits.is_nan())
147 return x;
148 return y;
149 }
150
151 // Check the exponent gap here so that all the follow up pre-scaling and
152 // overflow check won't generate spurious underflow exceptions.
153 if (LIBC_UNLIKELY(a_e - b_e >= (54U << (32 - 11)))) {
154 double x_abs = FPBits(x_u & FPBits::EXP_SIG_MASK).get_val();
155 double y_abs = FPBits(y_u & FPBits::EXP_SIG_MASK).get_val();
156 return x_abs + y_abs;
157 }
158 // Any scaling factor < 2^(-1024/2) = 2^-512 would work.
159 scale = 0x1.0p-600;
160 scale_back = 0x1.0p600;
161 a *= scale;
162 b *= scale;
163 // Check for overflow to raise the exception correctly.
164#if !defined(LIBC_MATH_HAS_NO_EXCEPT)
165 // No overflow when calculating a^2 + b^2.
166 double asq = a * a;
167 double bsq = b * b;
168 double sumsq = asq + bsq;
169 // Overflow happens when:
170 // 2^600 * sqrt(a^2 + b^2) >= 2^1023 * (2 - 2^-53)
171 // Which is equivalent to:
172 // sqrt(a^2 + b^2) >= 2^424 * (1 - 2^-54).
173 // Square both sides:
174 // a^2 + b^2 >= 2^848 * (1 - 2^-53 + 2^-108).
175 // For a fast sufficient condition that can be done in double precision:
176 // a^2 + b^2 >= 2^848.
177 if (sumsq >= 0x1.0p848)
178 return sumsq * scale_back;
179#endif // !LIBC_MATH_HAS_NO_EXCEPT
180 } else if (LIBC_UNLIKELY(b_e <= ((FPBits::EXP_BIAS - 400) << (32 - 11)))) {
181 // The smaller magnitude is below 2^-400 (or 0), need to scale up to prevent
182 // underflow when squaring.
183 if (LIBC_UNLIKELY(a_e < (1U << (32 - 11)))) {
184 // Larger input is denormal, extra care is needed to perform the Ziv's
185 // accuracy test correctly as double-rounding errors might happen.
186 if ((x == 0.0) || (y == 0.0)) {
187 double x_abs = FPBits(x_u & FPBits::EXP_SIG_MASK).get_val();
188 double y_abs = FPBits(y_u & FPBits::EXP_SIG_MASK).get_val();
189 return x_abs + y_abs;
190 }
191#ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS
192 return hypot_internal::hypot_denorm(a, b);
193#endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS
194 }
195 // Any scaling factor > 2^((1072 + 52)/2) = 2^562 would work.
196 scale = 0x1.0p600;
197 scale_back = 0x1.0p-600;
198 a *= scale;
199 b *= scale;
200 }
201
202 // When the gap in the exponent of `a` and `b` is >= 54,
203 // |b| < ufp(a) * 2^(-53) = ulp(a)/2
204 // So:
205 // hypot(x, y) = sqrt(a^2 + b^2)
206 // <= sqrt( (|a| + |b|)^2 )
207 // = |a| + |b|
208 // < |a| + ulp(a)
209 // Hence, we can return:
210 // |a| + |b| = |x| + |y|
211 // to perform correct rounding to all rounding modes.
212 if (LIBC_UNLIKELY(a_e - b_e >= (54U << (32 - 11)))) {
213 double x_abs = FPBits(x_u & FPBits::EXP_SIG_MASK).get_val();
214 double y_abs = FPBits(y_u & FPBits::EXP_SIG_MASK).get_val();
215 return x_abs + y_abs;
216 }
217
218 // sum.hi + sum.lo ~ a^2 + b^2.
219 DoubleDouble a_sq = fputil::exact_mult(a, b: a);
220 DoubleDouble b_sq = fputil::exact_mult(a: b, b);
221 DoubleDouble sum = fputil::exact_add(a: a_sq.hi, b: b_sq.hi);
222 sum.lo += a_sq.lo + b_sq.lo;
223
224 // Let hi = sum.hi and lo = sum.lo.
225 // To compute r_hi + r_lo ~ sqrt(hi + lo):
226 // - First we use fast sqrt instruction to get:
227 // r_hi ~ sqrt(hi)
228 // - Then use Taylor expansion:
229 // f(hi + lo) = f(hi) + f'(hi) * lo + f''(hi) * lo^2 / 2 + ...
230 // with f(x) = sqrt(x):
231 // sqrt(hi + lo) ~ sqrt(hi) + lo / (2 * sqrt(hi)).
232 // - Subtract by r_hi to find the correction term:
233 // sqrt(hi + lo) - r_hi ~ (sqrt(hi) - r_hi) + lo / (2 * sqrt(hi))
234 // - Instead of finding the rounding errors sqrt(hi) - r_hi, we use the
235 // squared residual d = hi - r_hi^2, which can be calculated accurately in
236 // double-double. Then, using the same Taylor approximation of sqrt(x) as
237 // above:
238 // sqrt(hi) - r_hi = sqrt(r_hi^2 + d) - r_hi
239 // ~ sqrt(r_hi^2) + d / (2 * sqrt(r_hi^2)) - r_hi
240 // = d / (2 * r_hi).
241 // - Similarly,
242 // 1 / sqrt(hi) = 1 / sqrt(r_hi^2 + d)
243 // ~ 1 / sqrt(r_hi^2) - d / (2 * (r_hi^2)^(3/2))
244 // = 1 / r_hi - d / (2 * r_hi^3)
245 // - Putting them together, we have the correction term:
246 // sqrt(hi + lo) - r_hi + lo / (2 * sqrt(hi)) ~
247 // ~ (lo + d) / (2 * r_hi) + lo * d / (4 * r_hi^3)
248 // ~ (hi + lo - r_hi^2) / (2 * r_hi).
249 // - When computing hi + lo - r_hi^2, we will pair (hi - r_sq.hi) and
250 // (lo - r_sq.lo), since `r_sq.hi` is very close to `hi`, and the
251 // subtraction is exact.
252 // - Taking intermediate roundings with directed rounding modes into
253 // consideration, the overall errors should be bounded by
254 // (2^-51)^2 = 2^-102.
255
256 // |sqrt(sum.hi) - r_hi| < 2^-52.
257 double r_hi = fputil::sqrt<double>(x: sum.hi);
258 // r_inv ~ 1 / (2 * r_hi)
259 double r_inv = 0.5 / r_hi;
260 // r_hi^2
261 DoubleDouble r_sq = fputil::exact_mult(a: r_hi, b: r_hi);
262 // (hi + lo - r_hi^2)
263 double num_lo = (sum.lo - r_sq.lo) - (r_sq.hi - sum.hi);
264 // (hi + lo - r_hi^2) / (2 * r_hi)
265 double r_lo = num_lo * r_inv;
266
267#ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS
268 // TODO: What's the worst error if we just do:
269 // return sqrt(a*a + b*b) * scale_back;
270 // without all the double-double computations?
271 return (r_hi + r_lo) * scale_back;
272#else
273 constexpr double ERR = 0x1.0p-102;
274
275 // Ziv's rounding test.
276 double upper = r_hi + fputil::multiply_add(x: r_hi, y: ERR, z: r_lo);
277 double lower = r_hi + fputil::sub_multiply(x: r_lo, y: r_hi, z: ERR);
278
279 if (LIBC_LIKELY(upper == lower)) {
280 return upper * scale_back;
281 }
282
283 return fputil::hypot(x, y);
284#endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS
285}
286
287} // namespace math
288} // namespace LIBC_NAMESPACE_DECL
289
290#endif // LLVM_LIBC_SRC___SUPPORT_MATH_HYPOT_H
291