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;