Skip to main content

tensor4all_core/any_scalar/
reciprocal.rs

1use anyhow::anyhow;
2
3use super::{AnyScalar, AnyScalarError};
4
5/// Largest exponent magnitude of a real divisor for which `1 / divisor` is
6/// formed directly.
7const DIRECT_RECIPROCAL_EXPONENT: i32 = 500;
8
9/// Magnitude exponent of the scaled divisor `divisor * 2^j` for a large
10/// divisor.
11const LARGE_DIVISOR_TARGET_EXPONENT: i32 = 64;
12
13/// Exponent above which a complex divisor is scaled to the large target, where
14/// `|quotient| * 2^130` cannot overflow.
15const COMPLEX_LARGE_DIVISOR_EXPONENT: i32 = 200;
16
17/// Exact powers of two whose product is `2^k`, each a normal `f64`.
18fn pow2_factors(mut k: i32) -> impl Iterator<Item = f64> {
19    const STEP: i32 = 1000;
20    std::iter::from_fn(move || {
21        if k == 0 {
22            return None;
23        }
24        let j = k.clamp(-STEP, STEP);
25        k -= j;
26        Some(f64::from_bits(((1023 + j) as u64) << 52))
27    })
28}
29
30fn times_pow2(value: &AnyScalar, k: i32) -> AnyScalar {
31    pow2_factors(k).fold(value.clone(), |acc, factor| {
32        acc * AnyScalar::new_real(factor)
33    })
34}
35
36impl AnyScalar {
37    /// Returns whether every nonzero component converts to a normal `f32`, so
38    /// that converting the scalar to single precision only rounds it to 24
39    /// significant bits.
40    ///
41    /// Use it on the factors of [`reciprocal_factors`](Self::reciprocal_factors)
42    /// before applying them to single-precision entries: a factor outside
43    /// this range would become zero or infinite, or lose a component.
44    ///
45    /// # Examples
46    ///
47    /// ```
48    /// use tensor4all_core::AnyScalar;
49    ///
50    /// assert!(AnyScalar::new_real(0.25).is_in_single_precision_range());
51    /// assert!(AnyScalar::new_complex(3.0, 0.0).is_in_single_precision_range());
52    /// assert!(!AnyScalar::new_real(2.0_f64.powi(-199)).is_in_single_precision_range());
53    /// assert!(!AnyScalar::new_complex(1.0, 1e300).is_in_single_precision_range());
54    /// assert!(!AnyScalar::new_real(f64::NAN).is_in_single_precision_range());
55    /// ```
56    pub fn is_in_single_precision_range(&self) -> bool {
57        [self.real(), self.imag()]
58            .into_iter()
59            .all(|component| component == 0.0 || (component as f32).is_normal())
60    }
61
62    /// Returns scalar factors whose product is `1 / self`, ordered so that
63    /// multiplying a value by each in turn divides it by `self` with every
64    /// intermediate before the last product finite when the quotient
65    /// components are, and without forming a component of `1 / self` that
66    /// could underflow. The last product multiplies by a rounded factor, so a
67    /// quotient component within a few units in the last place of `f64::MAX`
68    /// can round to infinity.
69    ///
70    /// Use this instead of multiplying by `1 / self` when `self` may be tiny or
71    /// huge: for `self = 3 * 2^-1070`, `1 / self` overflows although
72    /// `2^-1000 / self` is finite. Apply the factors in order.
73    ///
74    /// - A real divisor whose magnitude is in `[2^-500, 2^500]` gives the single
75    ///   factor `1 / self`.
76    /// - Another real divisor gives exact powers of two `2^j` followed by
77    ///   `1 / (self * 2^j)`, where `|self * 2^j|` is in `[1/4, 1/2)` for a
78    ///   small divisor and in `[2^64, 2^65)` for a large one. Each component
79    ///   of the result is then `fl(x * fl(1 / self))`, with the reciprocal
80    ///   rounded as if the exponent range were unbounded, also when the
81    ///   product is subnormal.
82    /// - An untracked purely imaginary divisor `b i` gives `-i`, which is
83    ///   exact, followed by the factors of the real `b`, so the real-divisor
84    ///   guarantees apply to each component.
85    /// - Another complex divisor gives a real factor last, built from
86    ///   `1 / |self * 2^j|^2` with `|self * 2^j|` in `[1/4, 1/2)` up to
87    ///   `|self| = 2^201` and in `[2^64, 2^65)` above. When `j >= 0`, `2^j`
88    ///   and `conj(self * 2^j)` come first. When `j < 0` and `|self|` is below
89    ///   `2^201`, the factors are `conj(self * 2^j)` and
90    ///   `2^j / |self * 2^j|^2` if scaling `self` down is exact; if it would
91    ///   flush a component, `conj(self)` is applied unscaled instead, as
92    ///   `2^j`, `conj(self)`, `2^j / |self * 2^j|^2`. Above `2^201`,
93    ///   `conj(self)` comes between two powers of two whose product is
94    ///   `2^(2j)`, followed by `1 / |self * 2^j|^2`. No component of `1 / self` or of a
95    ///   scaled-down `self` is formed on its own, and no intermediate
96    ///   component exceeds the largest component of the value or of the
97    ///   quotient, so none overflows unless a quotient component does. The
98    ///   error of each component is a few units in the last place of
99    ///   `|quotient|`. For a real value with a subnormal quotient, the
100    ///   intermediate before the last factor is rounded at subnormal
101    ///   granularity and the last factor can amplify that rounding, so the
102    ///   absolute error is several units of `2^-1074`, and a component that
103    ///   small can round to zero. No worst-case constant is derived; on the
104    ///   tests' sample of complex divisors and subnormal quotients the largest
105    ///   errors are `8 * 2^-1074` when `|self| < 1/2` and `4 * 2^-1074`
106    ///   otherwise, and the tests check that both are attained.
107    ///
108    /// The guarantees are for `f64` and `Complex64` arithmetic. Entries stored
109    /// in single precision convert each factor to `f32`, which keeps the
110    /// guarantees only when every factor passes
111    /// [`is_in_single_precision_range`](Self::is_in_single_precision_range).
112    ///
113    /// A gradient-tracked divisor yields tracked factors.
114    ///
115    /// # Returns
116    ///
117    /// One to five factors, to be applied in order.
118    ///
119    /// # Errors
120    ///
121    /// Returns [`AnyScalarError`] when `self` is zero or has a NaN or infinite
122    /// component.
123    ///
124    /// # Examples
125    ///
126    /// ```
127    /// use tensor4all_core::AnyScalar;
128    ///
129    /// let divide = |value: AnyScalar, divisor: &AnyScalar| {
130    ///     divisor
131    ///         .reciprocal_factors()
132    ///         .unwrap()
133    ///         .into_iter()
134    ///         .fold(value, |acc, factor| acc * factor)
135    /// };
136    ///
137    /// // 3 * 2^-1070 is subnormal and its reciprocal overflows.
138    /// let tiny = AnyScalar::new_real(f64::from_bits(48));
139    /// assert!((1.0 / tiny.real()).is_infinite());
140    /// let quotient = divide(AnyScalar::new_real(2.0_f64.powi(-1000)), &tiny);
141    /// assert_eq!(quotient.real(), 2.0_f64.powi(70) / 3.0);
142    ///
143    /// // (2^600 + 2^-420 i): the imaginary part of the reciprocal is below
144    /// // the smallest subnormal, but that of 2^600 / divisor is -2^-1020.
145    /// let divisor = AnyScalar::new_complex(2.0_f64.powi(600), 2.0_f64.powi(-420));
146    /// let quotient = divide(AnyScalar::new_real(2.0_f64.powi(600)), &divisor);
147    /// assert_eq!(quotient.real(), 1.0);
148    /// assert_eq!(quotient.imag(), -2.0_f64.powi(-1020));
149    ///
150    /// assert!(AnyScalar::new_real(0.0).reciprocal_factors().is_err());
151    /// ```
152    pub fn reciprocal_factors(&self) -> Result<Vec<AnyScalar>, AnyScalarError> {
153        // `f64::max` drops a NaN operand, so check each component.
154        let (re, im) = (self.real(), self.imag());
155        if !(re.is_finite() && im.is_finite()) || self.is_zero() {
156            return Err(anyhow!("cannot divide by {self:?}").into());
157        }
158        // A tracked divisor takes the general path, whose recorded expression
159        // depends on both components.
160        if re == 0.0 && im != 0.0 && !self.tracks_grad() {
161            // 1 / (b i) = -i / b, and multiplying by -i is exact.
162            let mut factors = vec![AnyScalar::new_complex(0.0, -1.0)];
163            factors.extend(self.imag_part().reciprocal_factors()?);
164            return Ok(factors);
165        }
166        let largest = re.abs().max(im.abs());
167        let complex = im != 0.0;
168        let exponent = largest.log2().floor() as i32;
169        if !complex && exponent.abs() <= DIRECT_RECIPROCAL_EXPONENT {
170            return Ok(vec![AnyScalar::new_real(1.0) / self.clone()]);
171        }
172        // `|self| * 2^k` lies in [1, 2) after these loops; each step is exact.
173        let mut k = -exponent;
174        let mut magnitude = times_pow2(self, k).abs();
175        while magnitude >= 2.0 {
176            magnitude *= 0.5;
177            k -= 1;
178        }
179        while magnitude < 1.0 {
180            magnitude *= 2.0;
181            k += 1;
182        }
183        // With `u = |self * 2^j|` and quotient `q`, the last intermediate
184        // before the real reciprocal is `q * u` (real divisor) or `q * u^2`
185        // (complex). For a real divisor and `j > 0` a value is scaled to
186        // `q * u` first, and `u <= 1/2` keeps every intermediate at or below
187        // `q`; for `j <= 0` no step exceeds the value itself, so `u` in
188        // `[1/2, 1)` suffices. A complex factor `w` can grow a component of a
189        // complex value to `|x| |w|`, up to `sqrt(2)` times its largest
190        // component, so a complex divisor keeps `|w| <= 1/2` with `u` in
191        // `[1/4, 1/2)`. The large target `[2^64, 2^65)` loses bits of a scaled
192        // value only for a quotient below `2^-1086`, and those bits stay below
193        // `2^-1139`.
194        let j = if complex {
195            if k >= -COMPLEX_LARGE_DIVISOR_EXPONENT {
196                k - 2
197            } else {
198                k + LARGE_DIVISOR_TARGET_EXPONENT
199            }
200        } else if k > 0 {
201            k - 2
202        } else {
203            k + LARGE_DIVISOR_TARGET_EXPONENT
204        };
205        let scaled = times_pow2(self, j);
206        let pow2 = |k: i32| pow2_factors(k).map(AnyScalar::new_real);
207        let mut factors: Vec<AnyScalar> = Vec::new();
208        if !complex {
209            factors.extend(pow2(j));
210            factors.push(AnyScalar::new_real(1.0) / scaled);
211            return Ok(factors);
212        }
213        // `|self * 2^j|^2` needs only relative precision, so a component of
214        // `self * 2^j` flushed by scaling down does not matter there.
215        let norm_sqr = (&scaled * &scaled.conj()).real_part();
216        if j >= 0 {
217            // Scaling the divisor up is exact.
218            factors.extend(pow2(j));
219            factors.push(scaled.conj());
220        } else {
221            let back = times_pow2(&scaled, -j);
222            if back.real() == re && back.imag() == im && k >= -COMPLEX_LARGE_DIVISOR_EXPONENT {
223                // Scaling the divisor down was exact. `|self * 2^j| < 1/2`
224                // bounds the first intermediate and `2^j / |self * 2^j|^2`
225                // stays normal, so the quotient is rounded once after a
226                // single complex product.
227                factors.push(scaled.conj());
228                factors.push(times_pow2(&(AnyScalar::new_real(1.0) / norm_sqr), j));
229                return Ok(factors);
230            }
231            // Scaling the divisor down can flush a component whose product
232            // with the value is representable, so `conj(self)` is applied
233            // unscaled after `2^(k-2)`, which keeps `|2^(k-2) self|` below
234            // 1/2. The remaining `2^(2j-k+2)` is folded into the real
235            // reciprocal when that stays normal (`j = k - 2`), so the quotient
236            // is rounded once at the end.
237            factors.extend(pow2(k - 2));
238            factors.push(self.conj());
239            let remaining = 2 * j - k + 2;
240            if k >= -COMPLEX_LARGE_DIVISOR_EXPONENT {
241                factors.push(times_pow2(
242                    &(AnyScalar::new_real(1.0) / norm_sqr),
243                    remaining,
244                ));
245                return Ok(factors);
246            }
247            factors.extend(pow2(remaining));
248        }
249        factors.push(AnyScalar::new_real(1.0) / norm_sqr);
250        Ok(factors)
251    }
252}
253
254#[cfg(test)]
255mod tests;