Debian Codegraph @

.cargo/vendor/pxfm/src/cube_roots/rcbrt.rs

raw
1 /*
2 * // Copyright (c) Radzivon Bartoshyk 8/2025. All rights reserved.
3 * //
4 * // Redistribution and use in source and binary forms, with or without modification,
5 * // are permitted provided that the following conditions are met:
6 * //
7 * // 1. Redistributions of source code must retain the above copyright notice, this
8 * // list of conditions and the following disclaimer.
9 * //
10 * // 2. Redistributions in binary form must reproduce the above copyright notice,
11 * // this list of conditions and the following disclaimer in the documentation
12 * // and/or other materials provided with the distribution.
13 * //
14 * // 3. Neither the name of the copyright holder nor the names of its
15 * // contributors may be used to endorse or promote products derived from
16 * // this software without specific prior written permission.
17 * //
18 * // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
22 * // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
24 * // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
25 * // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
26 * // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29 use crate::common::f_fmla;
30 use crate::double_double::DoubleDouble;
31 use crate::exponents::fast_ldexp;
32 use crate::polyeval::f_polyeval6;
33
34 //
35 // // y1 = y0 + 1/3 * y0 * (1 - a * y0 * y0 * y0)
36 // #[inline]
37 // fn raphson_step(x: f64, a: f64) -> f64 {
38 // let h = f_fmla(-a * x, x * x, 1.0);
39 // f_fmla(1. / 3. * h, x, x)
40 // }
41
42 // y1 = y0(k1 − c(k2 − k3c), c = x*y0*y0*y0
43 // k1 = 14/9 , k2 = 7/9 , k3 = 2/9
44 #[inline(always)]
45 fn halleys_div_free(x: f64, a: f64) -> f64 {
46 const K3: f64 = 2. / 9.;
47 const K2: f64 = 7. / 9.;
48 const K1: f64 = 14. / 9.;
49 let c = a * x * x * x;
50 let mut y = f_fmla(-K3, c, K2);
51 y = f_fmla(-c, y, K1);
52 y * x
53 }
54
55 #[inline(always)]
56 #[allow(unused)]
57 fn halleys_div_free_fma(x: f64, a: f64) -> f64 {
58 const K3: f64 = 2. / 9.;
59 const K2: f64 = 7. / 9.;
60 const K1: f64 = 14. / 9.;
61 let c = a * x * x * x;
62 let mut y = f64::mul_add(-K3, c, K2);
63 y = f64::mul_add(-c, y, K1);
64 y * x
65 }
66
67 #[inline(always)]
68 fn rcbrt_gen_impl(a: f64) -> f64 {
69 // Decompose a = m * 2^e, with m in [0.5, 1)
70 let xu = a.to_bits();
71 let exp = ((xu >> 52) & 0x7ff) as i32;
72 let mut e = ((xu >> 52) & 0x7ff) as i32;
73 let mut mant = xu & ((1u64 << 52) - 1);
74
75 if exp == 0x7ff {
76 if a.is_infinite() {
77 return if a.is_sign_negative() { -0.0 } else { 0.0 };
78 }
79 return a + a;
80 }
81 if exp == 0 && a == 0. {
82 return if a.is_sign_negative() {
83 f64::NEG_INFINITY
84 } else {
85 f64::INFINITY
86 };
87 }
88
89 // Normalize subnormal
90 if exp == 0 {
91 let norm = a * f64::from_bits(0x4350000000000000); // * 2^54
92 let norm_bits = norm.to_bits();
93 mant = norm_bits & ((1u64 << 52) - 1);
94 e = ((norm_bits >> 52) & 0x7ff) as i32 - 54;
95 }
96
97 e -= 1023;
98
99 mant |= 0x3ff << 52;
100 let m = f64::from_bits(mant);
101
102 // Polynomial for x^(-1/3) on [1.0; 2.0]
103 // Generated by Sollya:
104 // d = [1.0, 2.0];
105 // f_inv_cbrt = x^(-1/3);
106 // Q = fpminimax(f_inv_cbrt, 5, [|D...|], d, relative, floating);
107 // See ./notes/inv_cbrt.sollya
108
109 let p = f_polyeval6(
110 m,
111 f64::from_bits(0x3ffc7f365bceaf71),
112 f64::from_bits(0xbff90e741fb9c896),
113 f64::from_bits(0x3ff3e68b9b2cd237),
114 f64::from_bits(0xbfe321c5eb24a185),
115 f64::from_bits(0x3fc3fa269b897f69),
116 f64::from_bits(0xbf916d6f13849fd1),
117 );
118
119 // split exponent e = 3*q + r with r in {0,1,2}
120 // use div_euclid/rem_euclid to get r >= 0
121 let q = e.div_euclid(3);
122 let rem_scale = e.rem_euclid(3);
123
124 // 1; 2^{-1/3}; 2^{-2/3}
125 static ESCALE: [u64; 3] = [1.0f64.to_bits(), 0x3fe965fea53d6e3d, 0x3fe428a2f98d728b];
126
127 let z = p * f64::from_bits(ESCALE[rem_scale as usize]);
128
129 let mm = fast_ldexp(m, rem_scale); // bring domain into [1;8]
130
131 // One Halley's method step
132 // then refine in partial double-double precision with Newton-Raphson iteration
133 let y0 = halleys_div_free(z, mm);
134
135 let d2y = DoubleDouble::from_exact_mult(y0, y0);
136 let d3y = DoubleDouble::quick_mult_f64(d2y, y0);
137 let hb = DoubleDouble::quick_mult_f64(d3y, mm);
138
139 let y: f64;
140
141 #[cfg(any(
142 all(
143 any(target_arch = "x86", target_arch = "x86_64"),
144 target_feature = "fma"
145 ),
146 target_arch = "aarch64"
147 ))]
148 {
149 // decompose double-double in linear FMA sums
150 // r = (1.0 - hb.hi - hb.lo) * y0 = y0 - hb.hi * y0 - hb.lo * y0 = fma(-hb.lo, y0, fma(-hb.hi, y0, y0))
151 let r = f_fmla(-hb.lo, y0, f_fmla(hb.hi, -y0, y0));
152 // // y1 = y0 + 1/3 * y0 * (1 - a * y0 * y0 * y0) = y0 + 1/3 * r
153 y = f_fmla(1. / 3., r, y0);
154 }
155 #[cfg(not(any(
156 all(
157 any(target_arch = "x86", target_arch = "x86_64"),
158 target_feature = "fma"
159 ),
160 target_arch = "aarch64"
161 )))]
162 {
163 let m_hb = DoubleDouble::full_add_f64(-hb, 1.0);
164 let r = DoubleDouble::quick_mult_f64(m_hb, y0);
165 y = f_fmla(1. / 3., r.to_f64(), y0);
166 }
167 f64::copysign(fast_ldexp(y, -q), a)
168 }
169
170 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
171 #[target_feature(enable = "avx", enable = "fma")]
172 unsafe fn rcbrt_fma_impl(a: f64) -> f64 {
173 // Decompose a = m * 2^e, with m in [0.5, 1)
174 let xu = a.to_bits();
175 let exp = ((xu >> 52) & 0x7ff) as i32;
176 let mut e = ((xu >> 52) & 0x7ff) as i32;
177 let mut mant = xu & ((1u64 << 52) - 1);
178
179 if exp == 0x7ff {
180 if a.is_infinite() {
181 return if a.is_sign_negative() { -0.0 } else { 0.0 };
182 }
183 return a + a;
184 }
185 if exp == 0 && a == 0. {
186 return if a.is_sign_negative() {
187 f64::NEG_INFINITY
188 } else {
189 f64::INFINITY
190 };
191 }
192
193 // Normalize subnormal
194 if exp == 0 {
195 let norm = a * f64::from_bits(0x4350000000000000); // * 2^54
196 let norm_bits = norm.to_bits();
197 mant = norm_bits & ((1u64 << 52) - 1);
198 e = ((norm_bits >> 52) & 0x7ff) as i32 - 54;
199 }
200
201 e -= 1023;
202
203 mant |= 0x3ff << 52;
204 let m = f64::from_bits(mant);
205
206 // Polynomial for x^(-1/3) on [1.0; 2.0]
207 // Generated by Sollya:
208 // d = [1.0, 2.0];
209 // f_inv_cbrt = x^(-1/3);
210 // Q = fpminimax(f_inv_cbrt, 5, [|D...|], d, relative, floating);
211 // See ./notes/inv_cbrt.sollya
212
213 use crate::polyeval::d_polyeval6;
214 let p = d_polyeval6(
215 m,
216 f64::from_bits(0x3ffc7f365bceaf71),
217 f64::from_bits(0xbff90e741fb9c896),
218 f64::from_bits(0x3ff3e68b9b2cd237),
219 f64::from_bits(0xbfe321c5eb24a185),
220 f64::from_bits(0x3fc3fa269b897f69),
221 f64::from_bits(0xbf916d6f13849fd1),
222 );
223
224 // split exponent e = 3*q + r with r in {0,1,2}
225 // use div_euclid/rem_euclid to get r >= 0
226 let q = e.div_euclid(3);
227 let rem_scale = e.rem_euclid(3);
228
229 // 1; 2^{-1/3}; 2^{-2/3}
230 static ESCALE: [u64; 3] = [1.0f64.to_bits(), 0x3fe965fea53d6e3d, 0x3fe428a2f98d728b];
231
232 let z = p * f64::from_bits(ESCALE[rem_scale as usize]);
233
234 let mm = fast_ldexp(m, rem_scale); // bring domain into [1;8]
235
236 // One Halley's method step
237 // then refine in partial double-double precision with Newton-Raphson iteration
238 let y0 = halleys_div_free_fma(z, mm);
239
240 let d2y = DoubleDouble::from_exact_mult_fma(y0, y0);
241 let d3y = DoubleDouble::quick_mult_f64_fma(d2y, y0);
242 let hb = DoubleDouble::quick_mult_f64_fma(d3y, mm);
243
244 // decompose double-double in linear FMA sums
245 // r = (1.0 - hb.hi - hb.lo) * y0 = y0 - hb.hi * y0 - hb.lo * y0 = fma(-hb.lo, y0, fma(-hb.hi, y0, y0))
246 let r = f64::mul_add(-hb.lo, y0, f64::mul_add(hb.hi, -y0, y0));
247 // // y1 = y0 + 1/3 * y0 * (1 - a * y0 * y0 * y0) = y0 + 1/3 * r
248 let y = f64::mul_add(1. / 3., r, y0);
249 f64::copysign(fast_ldexp(y, -q), a)
250 }
251
252 /// Computes 1/cbrt(x)
253 ///
254 /// ULP 0.5
255 pub fn f_rcbrt(a: f64) -> f64 {
256 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
257 {
258 rcbrt_gen_impl(a)
259 }
260 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
261 {
262 use std::sync::OnceLock;
263 static EXECUTOR: OnceLock<unsafe fn(f64) -> f64> = OnceLock::new();
264 let q = EXECUTOR.get_or_init(|| {
265 if std::arch::is_x86_feature_detected!("avx")
266 && std::arch::is_x86_feature_detected!("fma")
267 {
268 rcbrt_fma_impl
269 } else {
270 fn def_rcbrt(x: f64) -> f64 {
271 rcbrt_gen_impl(x)
272 }
273 def_rcbrt
274 }
275 });
276 unsafe { q(a) }
277 }
278 }
279
280 #[cfg(test)]
281 mod tests {
282 use super::*;
283
284 #[test]
285 fn test_rcbrt() {
286 assert_eq!(f_rcbrt(0.9999999999999717), 1.0000000000000095);
287 assert_eq!(f_rcbrt(-68355745214719140000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.),
288 -0.000000000000000000000000000000000000000002445728958868668);
289 assert_eq!(f_rcbrt(-96105972807656840000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.),
290 -0.0000000000000000000000000000000000000000000000000000000002183148143573148);
291 assert_eq!(f_rcbrt(0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000139491540182158),
292 8949883389846071000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.);
293 assert_eq!(f_rcbrt(0.00008386280387617153), 22.846001824951983);
294 assert_eq!(f_rcbrt(-125.0), -0.2);
295 assert_eq!(f_rcbrt(125.0), 0.2);
296 assert_eq!(f_rcbrt(1.0), 1.0);
297 assert_eq!(f_rcbrt(-1.0), -1.0);
298 assert_eq!(f_rcbrt(0.0), f64::INFINITY);
299 assert_eq!(f_rcbrt(-27.0), -1. / 3.);
300 assert_eq!(
301 f_rcbrt(2417851639214765300000000.),
302 0.000000007450580596938716
303 );
304 assert_eq!(f_rcbrt(27.0), 1. / 3.);
305 assert_eq!(f_rcbrt(64.0), 0.25);
306 assert_eq!(f_rcbrt(-64.0), -0.25);
307 assert_eq!(f_rcbrt(f64::NEG_INFINITY), -0.0);
308 assert_eq!(f_rcbrt(f64::INFINITY), 0.0);
309 assert!(f_rcbrt(f64::NAN).is_nan());
310 }
311 }