1//===-- Double-precision tan 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-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_TAN_H
10#define LLVM_LIBC_SRC___SUPPORT_MATH_TAN_H
11
12#include "hdr/errno_macros.h"
13#include "range_reduction_double_common.h"
14#include "src/__support/FPUtil/FEnvImpl.h"
15#include "src/__support/FPUtil/FPBits.h"
16#include "src/__support/FPUtil/PolyEval.h"
17#include "src/__support/FPUtil/double_double.h"
18#include "src/__support/FPUtil/dyadic_float.h"
19#include "src/__support/FPUtil/except_value_utils.h"
20#include "src/__support/FPUtil/multiply_add.h"
21#include "src/__support/FPUtil/rounding_mode.h"
22#include "src/__support/macros/config.h"
23#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
24#include "src/__support/macros/properties/cpu_features.h" // LIBC_TARGET_CPU_HAS_FMA
25
26#ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE
27#include "range_reduction_double_fma.h"
28#else
29#include "range_reduction_double_nofma.h"
30#endif // LIBC_TARGET_CPU_HAS_FMA_DOUBLE
31
32namespace LIBC_NAMESPACE_DECL {
33
34namespace math {
35
36namespace tan_internal {
37
38using DoubleDouble = fputil::DoubleDouble;
39using DFloat128 = typename fputil::DyadicFloat<128>;
40
41LIBC_INLINE double tan_eval(const DoubleDouble &u, DoubleDouble &result) {
42 // Evaluate tan(y) = tan(x - k * (pi/128))
43 // We use the degree-9 Taylor approximation:
44 // tan(y) ~ P(y) = y + y^3/3 + 2*y^5/15 + 17*y^7/315 + 62*y^9/2835
45 // Then the error is bounded by:
46 // |tan(y) - P(y)| < 2^-6 * |y|^11 < 2^-6 * 2^-66 = 2^-72.
47 // For y ~ u_hi + u_lo, fully expanding the polynomial and drop any terms
48 // < ulp(u_hi^3) gives us:
49 // P(y) = y + y^3/3 + 2*y^5/15 + 17*y^7/315 + 62*y^9/2835 = ...
50 // ~ u_hi + u_hi^3 * (1/3 + u_hi^2 * (2/15 + u_hi^2 * (17/315 +
51 // + u_hi^2 * 62/2835))) +
52 // + u_lo (1 + u_hi^2 * (1 + u_hi^2 * 2/3))
53 double u_hi_sq = u.hi * u.hi; // Error < ulp(u_hi^2) < 2^(-6 - 52) = 2^-58.
54 // p1 ~ 17/315 + u_hi^2 62 / 2835.
55 double p1 =
56 fputil::multiply_add(x: u_hi_sq, y: 0x1.664f4882c10fap-6, z: 0x1.ba1ba1ba1ba1cp-5);
57 // p2 ~ 1/3 + u_hi^2 2 / 15.
58 double p2 =
59 fputil::multiply_add(x: u_hi_sq, y: 0x1.1111111111111p-3, z: 0x1.5555555555555p-2);
60 // q1 ~ 1 + u_hi^2 * 2/3.
61 double q1 = fputil::multiply_add(x: u_hi_sq, y: 0x1.5555555555555p-1, z: 1.0);
62 double u_hi_3 = u_hi_sq * u.hi;
63 double u_hi_4 = u_hi_sq * u_hi_sq;
64 // p3 ~ 1/3 + u_hi^2 * (2/15 + u_hi^2 * (17/315 + u_hi^2 * 62/2835))
65 double p3 = fputil::multiply_add(x: u_hi_4, y: p1, z: p2);
66 // q2 ~ 1 + u_hi^2 * (1 + u_hi^2 * 2/3)
67 double q2 = fputil::multiply_add(x: u_hi_sq, y: q1, z: 1.0);
68 double tan_lo = fputil::multiply_add(x: u_hi_3, y: p3, z: u.lo * q2);
69 // Overall, |tan(y) - (u_hi + tan_lo)| < ulp(u_hi^3) <= 2^-71.
70 // And the relative errors is:
71 // |(tan(y) - (u_hi + tan_lo)) / tan(y) | <= 2*ulp(u_hi^2) < 2^-64
72 result = fputil::exact_add(a: u.hi, b: tan_lo);
73 return fputil::multiply_add(x: fputil::FPBits<double>(u_hi_3).abs().get_val(),
74 y: 0x1.0p-51, z: 0x1.0p-102);
75}
76
77#ifndef LIBC_MATH_HAS_SKIP_ACCURATE_PASS
78// Accurate evaluation of tan for small u.
79[[maybe_unused]] LIBC_INLINE DFloat128 tan_eval(const DFloat128 &u) {
80 DFloat128 u_sq = fputil::quick_mul(a: u, b: u);
81
82 // tan(x) ~ x + x^3/3 + x^5 * 2/15 + x^7 * 17/315 + x^9 * 62/2835 +
83 // + x^11 * 1382/155925 + x^13 * 21844/6081075 +
84 // + x^15 * 929569/638512875 + x^17 * 6404582/10854718875
85 // Relative errors < 2^-127 for |u| < pi/256.
86 constexpr DFloat128 TAN_COEFFS[] = {
87 {Sign::POS, -127, 0x80000000'00000000'00000000'00000000_u128}, // 1
88 {Sign::POS, -129, 0xaaaaaaaa'aaaaaaaa'aaaaaaaa'aaaaaaab_u128}, // 1
89 {Sign::POS, -130, 0x88888888'88888888'88888888'88888889_u128}, // 2/15
90 {Sign::POS, -132, 0xdd0dd0dd'0dd0dd0d'd0dd0dd0'dd0dd0dd_u128}, // 17/315
91 {Sign::POS, -133, 0xb327a441'6087cf99'6b5dd24e'ec0b327a_u128}, // 62/2835
92 {Sign::POS, -134,
93 0x91371aaf'3611e47a'da8e1cba'7d900eca_u128}, // 1382/155925
94 {Sign::POS, -136,
95 0xeb69e870'abeefdaf'e606d2e4'd1e65fbc_u128}, // 21844/6081075
96 {Sign::POS, -137,
97 0xbed1b229'5baf15b5'0ec9af45'a2619971_u128}, // 929569/638512875
98 {Sign::POS, -138,
99 0x9aac1240'1b3a2291'1b2ac7e3'e4627d0a_u128}, // 6404582/10854718875
100 };
101
102 return fputil::quick_mul(
103 a: u, b: fputil::polyeval(x: u_sq, a0: TAN_COEFFS[0], a: TAN_COEFFS[1], a: TAN_COEFFS[2],
104 a: TAN_COEFFS[3], a: TAN_COEFFS[4], a: TAN_COEFFS[5],
105 a: TAN_COEFFS[6], a: TAN_COEFFS[7], a: TAN_COEFFS[8]));
106}
107
108// Calculation a / b = a * (1/b) for DFloat128.
109// Using the initial approximation of q ~ (1/b), then apply 2 Newton-Raphson
110// iterations, before multiplying by a.
111[[maybe_unused]] LIBC_INLINE DFloat128 newton_raphson_div(const DFloat128 &a,
112 DFloat128 b,
113 double q) {
114 DFloat128 q0(q);
115 LIBC_BIT_CAST_CONSTEXPR_VAR DFloat128 TWO(2.0);
116 b.sign = (b.sign == Sign::POS) ? Sign::NEG : Sign::POS;
117 DFloat128 q1 =
118 fputil::quick_mul(a: q0, b: fputil::quick_add(a: TWO, b: fputil::quick_mul(a: b, b: q0)));
119 DFloat128 q2 =
120 fputil::quick_mul(a: q1, b: fputil::quick_add(a: TWO, b: fputil::quick_mul(a: b, b: q1)));
121 return fputil::quick_mul(a, b: q2);
122}
123#endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS
124
125} // namespace tan_internal
126
127LIBC_INLINE double tan(double x) {
128 using namespace tan_internal;
129 using namespace math::range_reduction_double_internal;
130 using FPBits = typename fputil::FPBits<double>;
131 FPBits xbits(x);
132
133 uint16_t x_e = xbits.get_biased_exponent();
134
135 DoubleDouble y;
136 unsigned k;
137 LargeRangeReduction range_reduction_large{};
138
139 // |x| < 2^16
140 if (LIBC_LIKELY(x_e < FPBits::EXP_BIAS + FAST_PASS_EXPONENT)) {
141 // |x| < 2^-7
142 if (LIBC_UNLIKELY(x_e < FPBits::EXP_BIAS - 7)) {
143 // |x| < 2^-27, |tan(x) - x| < ulp(x)/2.
144 if (LIBC_UNLIKELY(x_e < FPBits::EXP_BIAS - 27)) {
145 // Signed zeros.
146 if (LIBC_UNLIKELY(x == 0.0))
147 return x + x; // Make sure it works with FTZ/DAZ.
148
149#ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE
150 return fputil::multiply_add(x, 0x1.0p-54, x);
151#else
152 if (LIBC_UNLIKELY(x_e < 4)) {
153 // TODO: UB for rounding nearest
154#ifndef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
155 int rounding_mode = fputil::quick_get_round();
156 if ((xbits.sign() == Sign::POS && rounding_mode == FE_UPWARD) ||
157 (xbits.sign() == Sign::NEG && rounding_mode == FE_DOWNWARD))
158 return FPBits(xbits.uintval() + 1).get_val();
159#endif // !LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
160 }
161 return fputil::multiply_add(x, y: 0x1.0p-54, z: x);
162#endif // LIBC_TARGET_CPU_HAS_FMA_DOUBLE
163 }
164 // No range reduction needed.
165 k = 0;
166 y.lo = 0.0;
167 y.hi = x;
168 } else {
169 // Small range reduction.
170 k = range_reduction_small(x, u&: y);
171 }
172 } else {
173 // Inf or NaN
174 if (LIBC_UNLIKELY(x_e > 2 * FPBits::EXP_BIAS)) {
175 if (xbits.is_signaling_nan()) {
176 fputil::raise_except_if_required(FE_INVALID);
177 return FPBits::quiet_nan().get_val();
178 }
179 // tan(+-Inf) = NaN
180 if (xbits.get_mantissa() == 0) {
181 fputil::set_errno_if_required(EDOM);
182 fputil::raise_except_if_required(FE_INVALID);
183 }
184 return x + FPBits::quiet_nan().get_val();
185 }
186
187 // Large range reduction.
188 k = range_reduction_large.fast(x, u&: y);
189 }
190
191 DoubleDouble tan_y;
192 [[maybe_unused]] double err = tan_eval(u: y, result&: tan_y);
193
194 // Look up sin(k * pi/128) and cos(k * pi/128)
195#ifdef LIBC_MATH_HAS_SMALL_TABLES
196 // Memory saving versions. Use 65-entry table:
197 auto get_idx_dd = [](unsigned kk) -> DoubleDouble {
198 unsigned idx = (kk & 64) ? 64 - (kk & 63) : (kk & 63);
199 DoubleDouble ans = SIN_K_PI_OVER_128[idx];
200 if (kk & 128) {
201 ans.hi = -ans.hi;
202 ans.lo = -ans.lo;
203 }
204 return ans;
205 };
206 DoubleDouble msin_k = get_idx_dd(k + 128);
207 DoubleDouble cos_k = get_idx_dd(k + 64);
208#else
209 // Fast look up version, but needs 256-entry table.
210 // cos(k * pi/128) = sin(k * pi/128 + pi/2) = sin((k + 64) * pi/128).
211 DoubleDouble msin_k = SIN_K_PI_OVER_128[(k + 128) & 255];
212 DoubleDouble cos_k = SIN_K_PI_OVER_128[(k + 64) & 255];
213#endif // LIBC_MATH_HAS_SMALL_TABLES
214
215 // After range reduction, k = round(x * 128 / pi) and y = x - k * (pi / 128).
216 // So k is an integer and -pi / 256 <= y <= pi / 256.
217 // Then tan(x) = sin(x) / cos(x)
218 // = sin((k * pi/128 + y) / cos((k * pi/128 + y)
219 // = (cos(y) * sin(k*pi/128) + sin(y) * cos(k*pi/128)) /
220 // / (cos(y) * cos(k*pi/128) - sin(y) * sin(k*pi/128))
221 // = (sin(k*pi/128) + tan(y) * cos(k*pi/128)) /
222 // / (cos(k*pi/128) - tan(y) * sin(k*pi/128))
223 DoubleDouble cos_k_tan_y = fputil::quick_mult(a: tan_y, b: cos_k);
224 DoubleDouble msin_k_tan_y = fputil::quick_mult(a: tan_y, b: msin_k);
225
226 // num_dd = sin(k*pi/128) + tan(y) * cos(k*pi/128)
227 DoubleDouble num_dd = fputil::exact_add<false>(a: cos_k_tan_y.hi, b: -msin_k.hi);
228 // den_dd = cos(k*pi/128) - tan(y) * sin(k*pi/128)
229 DoubleDouble den_dd = fputil::exact_add<false>(a: msin_k_tan_y.hi, b: cos_k.hi);
230 num_dd.lo += cos_k_tan_y.lo - msin_k.lo;
231 den_dd.lo += msin_k_tan_y.lo + cos_k.lo;
232
233#ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS
234 double tan_x = (num_dd.hi + num_dd.lo) / (den_dd.hi + den_dd.lo);
235 return tan_x;
236#else
237 // Accurate test and pass for correctly rounded implementation.
238
239 // Accurate double-double division
240 DoubleDouble tan_x = fputil::div(a: num_dd, b: den_dd);
241
242 // Simple error bound: |1 / den_dd| < 2^(1 + floor(-log2(den_dd)))).
243 uint64_t den_inv = (static_cast<uint64_t>(FPBits::EXP_BIAS + 1)
244 << (FPBits::FRACTION_LEN + 1)) -
245 (FPBits(den_dd.hi).uintval() & FPBits::EXP_MASK);
246
247 // For tan_x = (num_dd + err) / (den_dd + err), the error is bounded by:
248 // | tan_x - num_dd / den_dd | <= err * ( 1 + | tan_x * den_dd | ).
249 double tan_err =
250 err * fputil::multiply_add(x: FPBits(den_inv).get_val(),
251 y: FPBits(tan_x.hi).abs().get_val(), z: 1.0);
252
253 double err_higher = tan_x.lo + tan_err;
254 double err_lower = tan_x.lo - tan_err;
255
256 double tan_upper = tan_x.hi + err_higher;
257 double tan_lower = tan_x.hi + err_lower;
258
259 // Ziv's rounding test.
260 if (LIBC_LIKELY(tan_upper == tan_lower))
261 return tan_upper;
262
263 DFloat128 u_f128;
264 if (LIBC_LIKELY(x_e < FPBits::EXP_BIAS + FAST_PASS_EXPONENT))
265 u_f128 = range_reduction_small_f128(x);
266 else
267 u_f128 = range_reduction_large.accurate();
268
269 DFloat128 tan_u = tan_eval(u: u_f128);
270
271 auto get_sin_k = [](unsigned kk) -> DFloat128 {
272 unsigned idx = (kk & 64) ? 64 - (kk & 63) : (kk & 63);
273 DFloat128 ans = SIN_K_PI_OVER_128_F128[idx];
274 if (kk & 128)
275 ans.sign = Sign::NEG;
276 return ans;
277 };
278
279 // cos(k * pi/128) = sin(k * pi/128 + pi/2) = sin((k + 64) * pi/128).
280 DFloat128 sin_k_f128 = get_sin_k(k);
281 DFloat128 cos_k_f128 = get_sin_k(k + 64);
282 DFloat128 msin_k_f128 = get_sin_k(k + 128);
283
284 // num_f128 = sin(k*pi/128) + tan(y) * cos(k*pi/128)
285 DFloat128 num_f128 =
286 fputil::quick_add(a: sin_k_f128, b: fputil::quick_mul(a: cos_k_f128, b: tan_u));
287 // den_f128 = cos(k*pi/128) - tan(y) * sin(k*pi/128)
288 DFloat128 den_f128 =
289 fputil::quick_add(a: cos_k_f128, b: fputil::quick_mul(a: msin_k_f128, b: tan_u));
290
291 // tan(x) = (sin(k*pi/128) + tan(y) * cos(k*pi/128)) /
292 // / (cos(k*pi/128) - tan(y) * sin(k*pi/128))
293 // TODO: The initial seed 1.0/den_dd.hi for Newton-Raphson reciprocal can be
294 // reused from DoubleDouble fputil::div in the fast pass.
295 DFloat128 result = newton_raphson_div(a: num_f128, b: den_f128, q: 1.0 / den_dd.hi);
296
297 // TODO: Add assertion if Ziv's accuracy tests fail in debug mode.
298 // https://github.com/llvm/llvm-project/issues/96452.
299 return static_cast<double>(result);
300
301#endif // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS
302}
303
304} // namespace math
305
306} // namespace LIBC_NAMESPACE_DECL
307
308#endif // LLVM_LIBC_SRC___SUPPORT_MATH_TAN_H
309