Skip to main content

qualia_core_db/specialized_libs/computational_geometry/
expansion.rs

1//! Zero-heap expansion arithmetic — the exact-fallback foundation.
2//!
3//! This is P1.3 in the computational-geometry execution plan. It implements
4//! Shewchuk-style adaptive-precision floating-point arithmetic using
5//! **error-free transformations** and **expansions** (sorted, non-overlapping
6//! sequences of `f64` values that exactly represent a real number).
7//!
8//! ## Why this exists
9//!
10//! The filtered `f64` predicates in [`super::primitives`] are fast and exact
11//! on the `f32`-sourced `Tensor10D` path (because `f32 → f64` promotion makes
12//! the products exact). But for general `f64` inputs — and for cascaded
13//! constructions where errors accumulate — the filtered path can mis-sign
14//! near-degenerate cases. The exact-fallback ladder (P1.4–P1.7) needs a
15//! zero-heap way to compute the exact sign of a determinant. This module
16//! provides the arithmetic primitives that ladder is built from.
17//!
18//! ## Zero-heap contract
19//!
20//! Every function takes caller-supplied `&mut [f64]` output buffers. No
21//! `Vec`, `String`, or `Box` is allocated in any operation. The caller sizes
22//! buffers using the [`MAX_EXPANSION_*`] constants. If a buffer is too small,
23//! the operation returns [`ExpansionError::OutputTooSmall`] — fail-closed,
24//! never silent truncation.
25//!
26//! ## Expansion invariant
27//!
28//! An expansion `e = [e0, e1, ..., e_{n-1}]` is a sequence of `f64` values
29//! such that:
30//!
31//! 1. **Non-overlapping:** the components do not overlap in their bit ranges
32//!    (no component's significant bits overlap with another's).
33//! 2. **Sorted by magnitude:** `|e0| <= |e1| <= ... <= |e_{n-1}|`.
34//! 3. **Exact sum:** `sum(e_i)` equals the exact real-number result of the
35//!    operation that produced the expansion.
36//!
37//! The sign of an expansion is the sign of its largest-magnitude component
38//! (the last one), because the non-overlapping property guarantees no smaller
39//! component can change it.
40//!
41//! ## References
42//!
43//! The algorithms are from Jonathan Richard Shewchuk, "Adaptive Precision
44//! Floating-Point Arithmetic and Fast Robust Geometric Predicates" (1996,
45//! Discrete & Computational Geometry). The implementation is original Rust,
46//! adapted for the zero-heap caller-buffered contract. No third-party
47//! source code is used — the algorithms are public-knowledge
48//! numerical methods.
49
50// ──────────────────────────────────────────────────────────────────────────
51//  Workspace size constants
52// ──────────────────────────────────────────────────────────────────────────
53
54/// Maximum expansion length for the `orient2d` predicate (2×2 determinant
55/// of differences: 2 terms × 2-component products, summed → length ≤ 8).
56pub const MAX_EXPANSION_ORIENT2: usize = 8;
57
58/// Maximum expansion length for the `orient3d` predicate (3×3 determinant
59/// of differences: 6 terms × 3-component products, summed → length ≤ 24
60/// without compression; with compression the actual length is smaller).
61pub const MAX_EXPANSION_ORIENT3: usize = 24;
62
63/// Maximum expansion length for the `incircle` predicate (3×3 determinant
64/// with squared-distance entries: 6 terms × products of up to 4-component
65/// expansions, summed → length ≤ 96 without compression).
66pub const MAX_EXPANSION_INCIRCLE: usize = 96;
67
68/// Maximum expansion length for the `insphere` predicate (5×5 determinant
69/// with squared-distance entries: 120 terms × products of up to 6-component
70/// expansions, summed → length ≤ 2048 without compression; with aggressive
71/// zero-elimination the actual length is much smaller, but this bound
72/// ensures the workspace is always sufficient).
73///
74/// This is the coordination point called out in the execution plan: the
75/// P1.3 workspace must be sized for P1.6's insphere determinant. A 2048-f64
76/// workspace is 16 KB — well within the 42 MB Sentinel ceiling.
77pub const MAX_EXPANSION_INSPHERE: usize = 2048;
78
79// ──────────────────────────────────────────────────────────────────────────
80//  Error type
81// ──────────────────────────────────────────────────────────────────────────
82
83/// Errors from expansion arithmetic operations. All are fail-closed: the
84/// caller must provide sufficiently large buffers.
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86pub enum ExpansionError {
87    /// The output buffer is too small for the operation.
88    OutputTooSmall,
89}
90
91impl core::fmt::Display for ExpansionError {
92    /// Formats the expansion-arithmetic error as a human-readable message.
93    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
94        match self {
95            ExpansionError::OutputTooSmall => {
96                write!(f, "expansion output buffer too small")
97            }
98        }
99    }
100}
101
102impl std::error::Error for ExpansionError {}
103
104// ──────────────────────────────────────────────────────────────────────────
105//  Error-free transformations (length-1 → length-2)
106// ──────────────────────────────────────────────────────────────────────────
107
108/// Error-free addition: `a + b = s + e` where `s = round(a + b)` and `e` is
109/// the exact rounding error.
110///
111/// Knuth's algorithm (TAOCP Vol. 2, §4.2.2, Theorem B). Works for any `a, b`
112/// regardless of relative magnitude. Six floating-point operations.
113#[inline]
114pub fn two_sum(a: f64, b: f64) -> (f64, f64) {
115    let s = a + b;
116    let a_prime = s - b;
117    let b_prime = s - a_prime;
118    let da = a - a_prime;
119    let db = b - b_prime;
120    let e = da + db;
121    (s, e)
122}
123
124/// Error-free addition with precondition `|a| >= |b|`: `a + b = s + e`.
125///
126/// Faster than [`two_sum`] (three operations instead of six) but requires
127/// `|a| >= |b|`. If the precondition is violated the result is still a valid
128/// expansion but may not be error-free. Use [`two_sum`] when the relative
129/// magnitudes are unknown.
130#[inline]
131pub fn fast_two_sum(a: f64, b: f64) -> (f64, f64) {
132    debug_assert!(
133        a.abs() >= b.abs(),
134        "fast_two_sum precondition violated: |a| must be >= |b|"
135    );
136    let s = a + b;
137    let e = b - (s - a);
138    (s, e)
139}
140
141/// Error-free multiplication: `a * b = p + e` where `p = round(a * b)` and
142/// `e` is the exact rounding error.
143///
144/// Uses `fma` (fused multiply-add) when available: `e = fma(a, b, -p)`.
145/// On targets without hardware FMA this is still correct (the `mul_add`
146/// intrinsic produces the mathematically exact result on all IEEE-754
147/// platforms that Rust targets — it is the compiler's job to lower it).
148#[inline]
149pub fn two_product(a: f64, b: f64) -> (f64, f64) {
150    let p = a * b;
151    let e = a.mul_add(b, -p);
152    (p, e)
153}
154
155/// Error-free subtraction: `a - b = s + e`. Equivalent to `two_sum(a, -b)`.
156#[inline]
157pub fn two_diff(a: f64, b: f64) -> (f64, f64) {
158    two_sum(a, -b)
159}
160
161// ──────────────────────────────────────────────────────────────────────────
162//  Expansion operations
163// ──────────────────────────────────────────────────────────────────────────
164
165/// Grow an expansion by adding a scalar: `h = e + b`.
166///
167/// `e` is the input expansion (length `elen`), `b` is the scalar, `h` is the
168/// output buffer (must have length `>= elen + 1`). Returns the number of
169/// components written to `h` (always `elen + 1`).
170///
171/// Implements Shewchuk's `grow_expansion` (§2.4): a single pass that merges
172/// `b` into a non-overlapping, increasing-magnitude expansion using
173/// [`two_sum`]. The nonzero output components retain that invariant. Zero
174/// components are retained to preserve the `elen + 1` return contract; remove
175/// them before using a last-component sign test.
176///
177/// # Errors
178/// Returns [`ExpansionError::OutputTooSmall`] if `h.len() < elen + 1`.
179pub fn grow_expansion(e: &[f64], b: f64, h: &mut [f64]) -> Result<usize, ExpansionError> {
180    let elen = e.len();
181    if h.len() < elen + 1 {
182        return Err(ExpansionError::OutputTooSmall);
183    }
184
185    // Carry the running SUM and emit its low error. Carrying the error
186    // instead preserves the total but loses the non-overlap invariant.
187    let mut q = b;
188    for (i, &component) in e.iter().enumerate() {
189        let (sum, error) = two_sum(q, component);
190        h[i] = error;
191        q = sum;
192    }
193    h[elen] = q;
194    Ok(elen + 1)
195}
196
197#[cfg(test)]
198#[path = "expansion_grow_tests.rs"]
199mod grow_normalization_tests;
200
201/// Scale an expansion by a scalar: `h = e * b`.
202///
203/// `e` is the input expansion (length `elen`), `b` is the scalar, `h` is the
204/// output buffer (must have length `>= 2 * elen`). Returns the number of
205/// components written to `h` (at most `2 * elen`).
206///
207/// Implements Shewchuk's `scale_expansion` (§2.5): each component `e[i]` is
208/// split into `(e[i] * b, error)` via [`two_product`], and the errors are
209/// accumulated into the output using [`two_sum`], maintaining the
210/// non-overlapping + sorted invariant.
211///
212/// # Errors
213/// Returns [`ExpansionError::OutputTooSmall`] if `h.len() < 2 * elen`.
214pub fn scale_expansion(e: &[f64], b: f64, h: &mut [f64]) -> Result<usize, ExpansionError> {
215    let elen = e.len();
216    if h.len() < 2 * elen {
217        return Err(ExpansionError::OutputTooSmall);
218    }
219    if elen == 0 {
220        return Ok(0);
221    }
222
223    // First component: two_product(e[0], b) → (product, error).
224    let (p0, err0) = two_product(e[0], b);
225    h[0] = p0;
226    h[1] = err0;
227    let mut hlen = 2;
228
229    for i in 1..elen {
230        let (pi, ei) = two_product(e[i], b);
231        // Merge the error from the previous step with the product of the
232        // current step, then append the new error.
233        let (s0, e0) = two_sum(h[hlen - 1], pi);
234        h[hlen - 1] = s0;
235        let (s1, e1) = two_sum(e0, ei);
236        h[hlen] = s1;
237        h[hlen + 1] = e1;
238        hlen += 2;
239    }
240    Ok(hlen)
241}
242
243/// Add two expansions: `h = e + f`.
244///
245/// `e` and `f` are input expansions, `h` is the output buffer (must have
246/// length `>= e.len() + f.len()`). Returns the number of components written
247/// to `h` (at most `e.len() + f.len()`).
248///
249/// Implements Shewchuk's `expansion_sum` (§2.6): a merge that processes both
250/// expansions in order of increasing magnitude, using [`two_sum`] to maintain
251/// the non-overlapping + sorted invariant.
252///
253/// # Errors
254/// Returns [`ExpansionError::OutputTooSmall`] if `h.len() < e.len() + f.len()`.
255pub fn expansion_sum(e: &[f64], f: &[f64], h: &mut [f64]) -> Result<usize, ExpansionError> {
256    let elen = e.len();
257    let flen = f.len();
258    if h.len() < elen + flen {
259        return Err(ExpansionError::OutputTooSmall);
260    }
261    if elen == 0 {
262        h[..flen].copy_from_slice(f);
263        return Ok(flen);
264    }
265    if flen == 0 {
266        h[..elen].copy_from_slice(e);
267        return Ok(elen);
268    }
269
270    // Merge the two expansions like a merge-sort, feeding components through
271    // two_sum to maintain the non-overlapping invariant.
272    let mut ei = 0usize; // index into e
273    let mut fi = 0usize; // index into f
274    let mut hi = 0usize; // index into h
275
276    // Pick the smaller-magnitude first component to start.
277    let (mut current, from_e) = if e[0].abs() <= f[0].abs() {
278        (e[0], true)
279    } else {
280        (f[0], false)
281    };
282
283    // Advance past the consumed component.
284    if from_e {
285        ei = 1;
286    } else {
287        fi = 1;
288    }
289
290    // Merge remaining components.
291    while ei < elen && fi < flen {
292        let next_e = e[ei];
293        let next_f = f[fi];
294        let (val, take_e) = if next_e.abs() <= next_f.abs() {
295            (next_e, true)
296        } else {
297            (next_f, false)
298        };
299
300        let (s, err) = two_sum(current, val);
301        h[hi] = s;
302        hi += 1;
303        current = err;
304
305        if take_e {
306            ei += 1;
307        } else {
308            fi += 1;
309        }
310    }
311
312    // Drain remaining from e.
313    while ei < elen {
314        let (s, err) = two_sum(current, e[ei]);
315        h[hi] = s;
316        hi += 1;
317        current = err;
318        ei += 1;
319    }
320
321    // Drain remaining from f.
322    while fi < flen {
323        let (s, err) = two_sum(current, f[fi]);
324        h[hi] = s;
325        hi += 1;
326        current = err;
327        fi += 1;
328    }
329
330    // Append the final accumulated error.
331    h[hi] = current;
332    hi += 1;
333
334    Ok(hi)
335}
336
337/// Compress an expansion: eliminate near-zero and zero components, producing
338/// a minimal-length expansion with the same exact value.
339///
340/// `e` is the input expansion, `h` is the output buffer (must have length
341/// `>= e.len()`). Returns the number of components written to `h`.
342///
343/// Implements Shewchuk's `compress` (§2.7): a two-pass accumulation that
344/// merges adjacent components, eliminating zeros and reducing the expansion
345/// to its minimal non-overlapping form.
346///
347/// # Errors
348/// Returns [`ExpansionError::OutputTooSmall`] if `h.len() < e.len()`.
349pub fn compress_expansion(e: &[f64], h: &mut [f64]) -> Result<usize, ExpansionError> {
350    let elen = e.len();
351    if h.len() < elen {
352        return Err(ExpansionError::OutputTooSmall);
353    }
354    if elen == 0 {
355        return Ok(0);
356    }
357    if elen == 1 {
358        h[0] = e[0];
359        return Ok(1);
360    }
361
362    // Pass 1: top-down accumulation.
363    // Process e from the largest component (e[elen-1]) down to the smallest.
364    // We use two_sum (not fast_two_sum) because the running accumulator Q
365    // may not satisfy |Q| >= |e[i]| in all cases (e.g., when components
366    // have different signs and cancel). two_sum is always error-free.
367    let mut bottom = e[elen - 1];
368    for i in (0..elen - 1).rev() {
369        let (s, err) = two_sum(bottom, e[i]);
370        h[i + 1] = s;
371        bottom = err;
372    }
373    h[0] = bottom;
374
375    // Pass 2: bottom-up compression.
376    // Q is the running sum (the largest component). At each step,
377    // two_sum(Q, h[i]) produces (sum, error). The error is the smaller
378    // part — output it if non-zero. Q becomes the sum for the next step.
379    // This produces a sorted-by-increasing-magnitude expansion where
380    // each error component is smaller than the running sum.
381    let mut q = h[0];
382    let mut out = 0usize;
383
384    for i in 1..elen {
385        let (s, err) = two_sum(q, h[i]);
386        if err != 0.0 {
387            h[out] = err;
388            out += 1;
389        }
390        q = s;
391    }
392
393    // Output the final sum (the largest-magnitude component).
394    // Even if it's zero, output it if there are no other components
395    // (a zero expansion is [0.0] with length 1, not length 0).
396    if q != 0.0 || out == 0 {
397        h[out] = q;
398        out += 1;
399    }
400
401    Ok(out)
402}
403
404/// Negate an expansion in place: each component negated.
405#[inline]
406pub fn negate_expansion(e: &mut [f64]) {
407    for x in e.iter_mut() {
408        *x = -*x;
409    }
410}
411
412// ──────────────────────────────────────────────────────────────────────────
413//  Sign determination
414// ──────────────────────────────────────────────────────────────────────────
415
416/// Three-valued sign of a real number.
417#[derive(Debug, Clone, Copy, PartialEq, Eq)]
418pub enum Sign {
419    Negative = -1,
420    Zero = 0,
421    Positive = 1,
422}
423
424impl Sign {
425    /// Classifies an `f64` as `Negative`, `Zero`, or `Positive`. NaN maps to
426    /// `Zero` (it fails both comparisons); `-0.0` also maps to `Zero`.
427    #[inline]
428    pub fn from_f64(x: f64) -> Self {
429        if x > 0.0 {
430            Sign::Positive
431        } else if x < 0.0 {
432            Sign::Negative
433        } else {
434            Sign::Zero
435        }
436    }
437
438    /// Flip the sign.
439    #[inline]
440    pub fn flip(self) -> Self {
441        match self {
442            Sign::Positive => Sign::Negative,
443            Sign::Negative => Sign::Positive,
444            Sign::Zero => Sign::Zero,
445        }
446    }
447}
448
449/// Determine the exact sign of an expansion.
450///
451/// For a properly-formed (non-overlapping, sorted by magnitude) expansion,
452/// the sign is determined by the **last** (largest-magnitude) component.
453/// The non-overlapping property guarantees that no smaller component can
454/// change the sign.
455///
456/// Returns [`Sign::Zero`] if the expansion is empty or all components are
457/// exactly zero.
458#[inline]
459pub fn sign_of_expansion(e: &[f64]) -> Sign {
460    if e.is_empty() {
461        return Sign::Zero;
462    }
463    // The expansion is sorted by increasing magnitude, so the last component
464    // has the largest magnitude and determines the sign.
465    Sign::from_f64(e[e.len() - 1])
466}
467
468// ──────────────────────────────────────────────────────────────────────────
469//  Convenience: scalar product of two f64 as a length-2 expansion
470// ──────────────────────────────────────────────────────────────────────────
471
472/// Exact product of two scalars, written into a 2-element buffer.
473///
474/// Convenience wrapper around [`two_product`] that writes the result into
475/// a caller-supplied buffer. `h` must have length `>= 2`.
476#[inline]
477pub fn scalar_product(a: f64, b: f64, h: &mut [f64]) -> Result<usize, ExpansionError> {
478    if h.len() < 2 {
479        return Err(ExpansionError::OutputTooSmall);
480    }
481    let (p, e) = two_product(a, b);
482    h[0] = p;
483    h[1] = e;
484    Ok(2)
485}
486
487/// Exact sum of two scalars, written into a 2-element buffer.
488///
489/// Convenience wrapper around [`two_sum`]. `h` must have length `>= 2`.
490#[inline]
491pub fn scalar_sum(a: f64, b: f64, h: &mut [f64]) -> Result<usize, ExpansionError> {
492    if h.len() < 2 {
493        return Err(ExpansionError::OutputTooSmall);
494    }
495    let (s, e) = two_sum(a, b);
496    h[0] = s;
497    h[1] = e;
498    Ok(2)
499}
500
501// ──────────────────────────────────────────────────────────────────────────
502//  Tests
503// ──────────────────────────────────────────────────────────────────────────
504
505#[cfg(test)]
506mod tests {
507    use super::*;
508
509    // ── Test-only exact arithmetic cross-check ───────────────────────────
510    //
511    // Every finite f64 can be represented exactly as `m * 2^e` where m is
512    // a signed integer (the mantissa, up to 53 bits) and e is the exponent.
513    // We use BigInt for the mantissa to handle arbitrary exponent differences
514    // without overflow. This is test-only code — the expansion arithmetic
515    // itself is zero-heap; the cross-check uses heap allocation freely.
516
517    use num_bigint::BigInt;
518
519    /// An exact real number: value = mantissa * 2^exponent.
520    #[derive(Debug, Clone)]
521    struct Exact {
522        mantissa: BigInt,
523        exponent: i32,
524    }
525
526    impl Exact {
527        /// Convert an f64 to its exact representation.
528        fn from_f64(x: f64) -> Self {
529            if x == 0.0 {
530                return Exact {
531                    mantissa: BigInt::from(0),
532                    exponent: 0,
533                };
534            }
535            let bits = x.to_bits();
536            let sign: i8 = if bits >> 63 != 0 { -1 } else { 1 };
537            let raw_exp = ((bits >> 52) & 0x7FF) as i32;
538            let raw_mant = bits & 0x000F_FFFF_FFFF_FFFF;
539
540            if raw_exp == 0 {
541                // Subnormal: value = sign * raw_mant * 2^(-1074)
542                Exact {
543                    mantissa: BigInt::from(sign) * BigInt::from(raw_mant),
544                    exponent: -1074,
545                }
546            } else {
547                // Normalized: value = sign * (2^52 + raw_mant) * 2^(raw_exp - 1023 - 52)
548                Exact {
549                    mantissa: BigInt::from(sign)
550                        * (BigInt::from(1u64 << 52) + BigInt::from(raw_mant)),
551                    exponent: raw_exp - 1023 - 52,
552                }
553            }
554        }
555
556        /// Exact addition. Aligns exponents, adds mantissas.
557        fn add(self, other: Self) -> Self {
558            if self.mantissa == 0.into() {
559                return other;
560            }
561            if other.mantissa == 0.into() {
562                return self;
563            }
564            // Determine which has the smaller exponent. Compute diff
565            // before moving values into the tuple.
566            let (lo, mut hi) = if self.exponent <= other.exponent {
567                (self, other)
568            } else {
569                (other, self)
570            };
571            let diff = hi.exponent - lo.exponent;
572
573            // Align to the smaller exponent by shifting the larger-exponent
574            // mantissa left. This preserves exactness (no precision loss).
575            if diff > 0 {
576                hi.mantissa <<= diff;
577            }
578            Exact {
579                mantissa: lo.mantissa + hi.mantissa,
580                exponent: lo.exponent,
581            }
582        }
583
584        /// Exact multiplication.
585        fn mul(self, other: Self) -> Self {
586            Exact {
587                mantissa: self.mantissa * other.mantissa,
588                exponent: self.exponent + other.exponent,
589            }
590        }
591
592        /// Exact negation.
593        fn neg(self) -> Self {
594            Exact {
595                mantissa: -self.mantissa,
596                exponent: self.exponent,
597            }
598        }
599
600        /// Compare two exact values. Returns true if they represent the same
601        /// real number.
602        fn equals(&self, other: &Self) -> bool {
603            // Normalize: remove factors of 2 from the mantissa.
604            let a = self.clone().normalize();
605            let b = other.clone().normalize();
606            a.mantissa == b.mantissa && a.exponent == b.exponent
607        }
608
609        /// Normalize: remove trailing zeros from the mantissa.
610        fn normalize(mut self) -> Self {
611            if self.mantissa == 0.into() {
612                return Exact {
613                    mantissa: BigInt::from(0),
614                    exponent: 0,
615                };
616            }
617            let zero = BigInt::from(0);
618            let one = BigInt::from(1);
619            while (&self.mantissa & &one) == zero {
620                self.mantissa >>= 1;
621                self.exponent += 1;
622            }
623            self
624        }
625
626        /// Sign of the exact value.
627        fn sign(&self) -> Sign {
628            use std::cmp::Ordering;
629            match self.mantissa.cmp(&BigInt::from(0)) {
630                Ordering::Greater => Sign::Positive,
631                Ordering::Less => Sign::Negative,
632                Ordering::Equal => Sign::Zero,
633            }
634        }
635    }
636
637    /// Convert an expansion (sum of f64s) to its exact value.
638    fn expansion_to_exact(e: &[f64]) -> Exact {
639        let mut acc = Exact {
640            mantissa: BigInt::from(0),
641            exponent: 0,
642        };
643        for &x in e {
644            acc = acc.add(Exact::from_f64(x));
645        }
646        acc
647    }
648
649    // ── Error-free transformation tests ──────────────────────────────────
650
651    #[test]
652    fn two_sum_is_error_free() {
653        // a + b = s + e, and s + e == a + b exactly.
654        // Avoid overflow cases (1e308+1e308 → inf).
655        let cases: [(f64, f64); 7] = [
656            (1.0, 2.0),
657            (1e100, 1e-100),
658            (1.0, f64::EPSILON),
659            (1e200, 1e200),
660            (-1.0, 1.0 + f64::EPSILON),
661            (0.1, 0.2),
662            (1e300, -1e300 + 1.0),
663        ];
664        for &(a, b) in &cases {
665            let (s, e) = two_sum(a, b);
666            let exact_a = Exact::from_f64(a);
667            let exact_b = Exact::from_f64(b);
668            let exact_sum = exact_a.add(exact_b);
669            let exact_result = Exact::from_f64(s).add(Exact::from_f64(e));
670            assert!(
671                exact_sum.equals(&exact_result),
672                "two_sum({a}, {b}): s={s}, e={e} — exact mismatch"
673            );
674        }
675    }
676
677    #[test]
678    fn fast_two_sum_matches_two_sum_when_precondition_holds() {
679        let cases: [(f64, f64); 5] = [
680            (2.0, 1.0),
681            (1e100, 1.0),
682            (1.0, f64::EPSILON),
683            (1e308, 1e300),
684            (-2.0, -1.0),
685        ];
686        for &(a, b) in &cases {
687            assert!(a.abs() >= b.abs(), "precondition");
688            let (s1, e1) = two_sum(a, b);
689            let (s2, e2) = fast_two_sum(a, b);
690            // Both are error-free, so s1+e1 == s2+e2 exactly.
691            // They may not be bit-identical (different algorithms), but the
692            // exact values must match.
693            let exact1 = Exact::from_f64(s1).add(Exact::from_f64(e1));
694            let exact2 = Exact::from_f64(s2).add(Exact::from_f64(e2));
695            assert!(
696                exact1.equals(&exact2),
697                "fast_two_sum({a}, {b}): results differ from two_sum"
698            );
699        }
700    }
701
702    #[test]
703    fn two_product_is_error_free() {
704        // Avoid overflow (f64::MAX * 2 → inf).
705        let cases: [(f64, f64); 7] = [
706            (2.0, 3.0),
707            (1e100, 1e-100),
708            (1.0, f64::EPSILON),
709            (0.1, 0.1),
710            (1e154, 1e154),
711            (-2.0, 3.0),
712            (1e200, 1e-200),
713        ];
714        for &(a, b) in &cases {
715            let (p, e) = two_product(a, b);
716            let exact_a = Exact::from_f64(a);
717            let exact_b = Exact::from_f64(b);
718            let exact_prod = exact_a.mul(exact_b);
719            let exact_result = Exact::from_f64(p).add(Exact::from_f64(e));
720            assert!(
721                exact_prod.equals(&exact_result),
722                "two_product({a}, {b}): p={p}, e={e} — exact mismatch"
723            );
724        }
725    }
726
727    #[test]
728    fn two_diff_is_error_free() {
729        let cases = [(3.0, 1.0), (1e100, 1e100 - 1.0), (1.0, 1.0 + f64::EPSILON)];
730        for &(a, b) in &cases {
731            let (s, e) = two_diff(a, b);
732            let exact_a = Exact::from_f64(a);
733            let exact_b = Exact::from_f64(b);
734            let exact_diff = exact_a.add(exact_b.neg());
735            let exact_result = Exact::from_f64(s).add(Exact::from_f64(e));
736            assert!(
737                exact_diff.equals(&exact_result),
738                "two_diff({a}, {b}): s={s}, e={e} — exact mismatch"
739            );
740        }
741    }
742
743    // ── Expansion operation tests ────────────────────────────────────────
744
745    #[test]
746    fn grow_expansion_adds_scalar_exactly() {
747        // e = [1.0, f64::EPSILON/2] (a length-2 expansion representing
748        // 1 + eps/2). Adding 2.0 should give 3 + eps/2 exactly.
749        let e = [1.0, f64::EPSILON / 2.0];
750        let mut h = [0.0f64; 4];
751        let n = grow_expansion(&e, 2.0, &mut h).unwrap();
752        assert_eq!(n, 3);
753
754        let exact_e = Exact::from_f64(e[0]).add(Exact::from_f64(e[1]));
755        let exact_result = exact_e.add(Exact::from_f64(2.0));
756        let exact_h = expansion_to_exact(&h[..n]);
757        assert!(
758            exact_h.equals(&exact_result),
759            "grow_expansion: exact mismatch"
760        );
761    }
762
763    #[test]
764    fn grow_expansion_adversarial_cancellation() {
765        // Add a tiny number to a large one, then add the negative of the
766        // large one. The expansion should preserve the tiny number exactly.
767        let big = 1e100;
768        let tiny = 1e-100;
769        let mut e = [0.0f64; 1];
770        e[0] = big;
771        let mut h1 = [0.0f64; 2];
772        let n1 = grow_expansion(&e[..1], tiny, &mut h1).unwrap();
773        assert_eq!(n1, 2);
774
775        // Now add -big. The result should be exactly tiny.
776        let mut h2 = [0.0f64; 4];
777        let n2 = grow_expansion(&h1[..n1], -big, &mut h2).unwrap();
778        assert_eq!(n2, 3);
779
780        let exact_result = expansion_to_exact(&h2[..n2]);
781        let exact_tiny = Exact::from_f64(tiny);
782        assert!(
783            exact_result.equals(&exact_tiny),
784            "grow_expansion adversarial: expected exactly {tiny}, got {:?}",
785            &h2[..n2]
786        );
787    }
788
789    #[test]
790    fn scale_expansion_multiplies_exactly() {
791        // e = [1.0, f64::EPSILON/2], scale by 3.0.
792        let e = [1.0, f64::EPSILON / 2.0];
793        let mut h = [0.0f64; 8];
794        let n = scale_expansion(&e, 3.0, &mut h).unwrap();
795        assert!(n <= 4);
796
797        let exact_e = Exact::from_f64(e[0]).add(Exact::from_f64(e[1]));
798        let exact_result = exact_e.mul(Exact::from_f64(3.0));
799        let exact_h = expansion_to_exact(&h[..n]);
800        assert!(
801            exact_h.equals(&exact_result),
802            "scale_expansion: exact mismatch"
803        );
804    }
805
806    #[test]
807    fn scale_expansion_adversarial() {
808        // Scale a cancellation-prone expansion by a large factor.
809        // e = [1.0, -1.0 + eps] (represents eps). Scale by 1e50.
810        let (s, e_err) = two_sum(-1.0, 1.0 + f64::EPSILON);
811        // s should be ~eps, e_err should be the residual.
812        let e = [s, e_err];
813        let mut h = [0.0f64; 8];
814        let n = scale_expansion(&e, 1e50, &mut h).unwrap();
815        assert!(n <= 4);
816
817        let exact_e = Exact::from_f64(e[0]).add(Exact::from_f64(e[1]));
818        let exact_result = exact_e.mul(Exact::from_f64(1e50));
819        let exact_h = expansion_to_exact(&h[..n]);
820        assert!(
821            exact_h.equals(&exact_result),
822            "scale_expansion adversarial: exact mismatch"
823        );
824    }
825
826    #[test]
827    fn expansion_sum_adds_exactly() {
828        // e = [1.0, eps], f = [2.0, eps/2]. Sum = 3.0 + 1.5*eps.
829        let e = [1.0, f64::EPSILON];
830        let f = [2.0, f64::EPSILON / 2.0];
831        let mut h = [0.0f64; 8];
832        let n = expansion_sum(&e, &f, &mut h).unwrap();
833        assert!(n <= 4);
834
835        let exact_e = Exact::from_f64(e[0]).add(Exact::from_f64(e[1]));
836        let exact_f = Exact::from_f64(f[0]).add(Exact::from_f64(f[1]));
837        let exact_result = exact_e.add(exact_f);
838        let exact_h = expansion_to_exact(&h[..n]);
839        assert!(
840            exact_h.equals(&exact_result),
841            "expansion_sum: exact mismatch"
842        );
843    }
844
845    #[test]
846    fn expansion_sum_adversarial_cancellation() {
847        // e = [big, tiny], f = [-big, tiny]. Sum = 2*tiny.
848        let big = 1e100;
849        let tiny = 1e-100;
850        let (s1, e1) = two_sum(big, tiny);
851        let e = [s1, e1];
852        let (s2, e2) = two_sum(-big, tiny);
853        let f = [s2, e2];
854
855        let mut h = [0.0f64; 8];
856        let n = expansion_sum(&e, &f, &mut h).unwrap();
857
858        let exact_e = Exact::from_f64(e[0]).add(Exact::from_f64(e[1]));
859        let exact_f = Exact::from_f64(f[0]).add(Exact::from_f64(f[1]));
860        let exact_result = exact_e.add(exact_f);
861        let exact_h = expansion_to_exact(&h[..n]);
862        assert!(
863            exact_h.equals(&exact_result),
864            "expansion_sum adversarial: expected {:?}, got {:?}",
865            exact_result,
866            exact_h
867        );
868
869        // The exact result should be 2*tiny.
870        let exact_2tiny = Exact::from_f64(2.0).mul(Exact::from_f64(tiny));
871        assert!(
872            exact_h.equals(&exact_2tiny),
873            "expansion_sum adversarial: expected exactly 2*tiny"
874        );
875    }
876
877    #[test]
878    fn expansion_sum_empty_operands() {
879        let e: [f64; 0] = [];
880        let f = [1.0, 2.0];
881        let mut h = [0.0f64; 4];
882        let n = expansion_sum(&e, &f, &mut h).unwrap();
883        assert_eq!(n, 2);
884        assert_eq!(&h[..n], &f[..]);
885
886        let n = expansion_sum(&f, &e, &mut h).unwrap();
887        assert_eq!(n, 2);
888        assert_eq!(&h[..n], &f[..]);
889    }
890
891    #[test]
892    fn compress_removes_zeros() {
893        // Create a valid expansion with some zero components.
894        // Sorted by increasing magnitude: [0.0, eps, 0.0, 1.0]
895        // (zeros are valid in a Shewchuk expansion — they're smaller than
896        // any non-zero component).
897        let e = [0.0, f64::EPSILON, 0.0, 1.0];
898        let mut h = [0.0f64; 4];
899        let n = compress_expansion(&e, &mut h).unwrap();
900        assert!(n <= 4);
901
902        let exact_e = expansion_to_exact(&e);
903        let exact_h = expansion_to_exact(&h[..n]);
904        assert!(exact_h.equals(&exact_e), "compress: value changed");
905        // The compressed version should not be longer than the input.
906        assert!(n <= e.len());
907    }
908
909    #[test]
910    fn compress_preserves_value() {
911        // A non-trivial expansion sorted by increasing magnitude:
912        // [eps/4, eps/2, eps, 1.0].
913        let e = [f64::EPSILON / 4.0, f64::EPSILON / 2.0, f64::EPSILON, 1.0];
914        let mut h = [0.0f64; 4];
915        let n = compress_expansion(&e, &mut h).unwrap();
916
917        let exact_e = expansion_to_exact(&e);
918        let exact_h = expansion_to_exact(&h[..n]);
919        assert!(
920            exact_h.equals(&exact_e),
921            "compress: value changed for non-trivial expansion"
922        );
923    }
924
925    #[test]
926    fn compress_single_element() {
927        let e = [42.0];
928        let mut h = [0.0f64; 1];
929        let n = compress_expansion(&e, &mut h).unwrap();
930        assert_eq!(n, 1);
931        assert_eq!(h[0], 42.0);
932    }
933
934    #[test]
935    fn compress_empty() {
936        let e: [f64; 0] = [];
937        let mut h = [0.0f64; 0];
938        let n = compress_expansion(&e, &mut h).unwrap();
939        assert_eq!(n, 0);
940    }
941
942    // ── Sign determination tests ─────────────────────────────────────────
943
944    #[test]
945    fn sign_of_expansion_classifies_correctly() {
946        assert_eq!(sign_of_expansion(&[1.0]), Sign::Positive);
947        assert_eq!(sign_of_expansion(&[-1.0]), Sign::Negative);
948        assert_eq!(sign_of_expansion(&[0.0]), Sign::Zero);
949        assert_eq!(sign_of_expansion(&[]), Sign::Zero);
950
951        // The last (largest) component determines the sign.
952        assert_eq!(sign_of_expansion(&[1.0, 2.0]), Sign::Positive);
953        assert_eq!(sign_of_expansion(&[2.0, -1.0]), Sign::Negative);
954        assert_eq!(sign_of_expansion(&[f64::EPSILON, 1.0]), Sign::Positive);
955        assert_eq!(sign_of_expansion(&[f64::EPSILON, -1.0]), Sign::Negative);
956    }
957
958    #[test]
959    fn sign_of_cancellation_expansion() {
960        // [big, -big + tiny] → the last component is -big+tiny which is
961        // negative (since tiny << big). But the exact value is tiny (positive).
962        // This is NOT a properly-formed expansion (the components overlap),
963        // so sign_of_expansion would give the wrong answer. This test
964        // demonstrates why we need compress before checking sign.
965        //
966        // With a properly-formed expansion (after grow_expansion), the
967        // last component carries the true sign.
968        let big = 1e100;
969        let tiny = 1e-100;
970        let mut e = [0.0f64; 1];
971        e[0] = big;
972        let mut h1 = [0.0f64; 2];
973        let n1 = grow_expansion(&e[..1], tiny, &mut h1).unwrap();
974        let mut h2 = [0.0f64; 4];
975        let n2 = grow_expansion(&h1[..n1], -big, &mut h2).unwrap();
976
977        // After compress, the expansion should be [tiny] (or [tiny, 0.0]).
978        let mut h3 = [0.0f64; 4];
979        let n3 = compress_expansion(&h2[..n2], &mut h3).unwrap();
980
981        let sign = sign_of_expansion(&h3[..n3]);
982        assert_eq!(
983            sign,
984            Sign::Positive,
985            "sign should be positive (tiny > 0) after compress"
986        );
987    }
988
989    // ── Determinism tests ────────────────────────────────────────────────
990
991    #[test]
992    fn grow_expansion_is_deterministic() {
993        let e = [1.0, f64::EPSILON, 1e-300];
994        let mut h1 = [0.0f64; 4];
995        let mut h2 = [0.0f64; 4];
996        let n1 = grow_expansion(&e, 3.14, &mut h1).unwrap();
997        let n2 = grow_expansion(&e, 3.14, &mut h2).unwrap();
998        assert_eq!(n1, n2);
999        for i in 0..n1 {
1000            assert_eq!(h1[i].to_bits(), h2[i].to_bits(), "bit mismatch at {i}");
1001        }
1002    }
1003
1004    #[test]
1005    fn scale_expansion_is_deterministic() {
1006        let e = [1.0, f64::EPSILON, 1e-300, 0.0];
1007        let mut h1 = [0.0f64; 8];
1008        let mut h2 = [0.0f64; 8];
1009        let n1 = scale_expansion(&e, 2.718, &mut h1).unwrap();
1010        let n2 = scale_expansion(&e, 2.718, &mut h2).unwrap();
1011        assert_eq!(n1, n2);
1012        for i in 0..n1 {
1013            assert_eq!(h1[i].to_bits(), h2[i].to_bits(), "bit mismatch at {i}");
1014        }
1015    }
1016
1017    #[test]
1018    fn expansion_sum_is_deterministic() {
1019        let e = [1.0, f64::EPSILON, 1e-200];
1020        let f = [2.0, -f64::EPSILON, 1e-250];
1021        let mut h1 = [0.0f64; 8];
1022        let mut h2 = [0.0f64; 8];
1023        let n1 = expansion_sum(&e, &f, &mut h1).unwrap();
1024        let n2 = expansion_sum(&e, &f, &mut h2).unwrap();
1025        assert_eq!(n1, n2);
1026        for i in 0..n1 {
1027            assert_eq!(h1[i].to_bits(), h2[i].to_bits(), "bit mismatch at {i}");
1028        }
1029    }
1030
1031    #[test]
1032    fn compress_is_deterministic() {
1033        let e = [1.0, f64::EPSILON, 0.0, 2.0, f64::EPSILON / 2.0];
1034        let mut h1 = [0.0f64; 5];
1035        let mut h2 = [0.0f64; 5];
1036        let n1 = compress_expansion(&e, &mut h1).unwrap();
1037        let n2 = compress_expansion(&e, &mut h2).unwrap();
1038        assert_eq!(n1, n2);
1039        for i in 0..n1 {
1040            assert_eq!(h1[i].to_bits(), h2[i].to_bits(), "bit mismatch at {i}");
1041        }
1042    }
1043
1044    // ── Bounds checking tests ────────────────────────────────────────────
1045
1046    #[test]
1047    fn grow_expansion_rejects_small_buffer() {
1048        let e = [1.0, 2.0, 3.0];
1049        let mut h = [0.0f64; 3]; // need 4
1050        assert_eq!(
1051            grow_expansion(&e, 4.0, &mut h),
1052            Err(ExpansionError::OutputTooSmall)
1053        );
1054    }
1055
1056    #[test]
1057    fn scale_expansion_rejects_small_buffer() {
1058        let e = [1.0, 2.0, 3.0];
1059        let mut h = [0.0f64; 5]; // need 6
1060        assert_eq!(
1061            scale_expansion(&e, 2.0, &mut h),
1062            Err(ExpansionError::OutputTooSmall)
1063        );
1064    }
1065
1066    #[test]
1067    fn expansion_sum_rejects_small_buffer() {
1068        let e = [1.0, 2.0];
1069        let f = [3.0, 4.0, 5.0];
1070        let mut h = [0.0f64; 4]; // need 5
1071        assert_eq!(
1072            expansion_sum(&e, &f, &mut h),
1073            Err(ExpansionError::OutputTooSmall)
1074        );
1075    }
1076
1077    #[test]
1078    fn compress_rejects_small_buffer() {
1079        let e = [1.0, 2.0, 3.0];
1080        let mut h = [0.0f64; 2]; // need 3
1081        assert_eq!(
1082            compress_expansion(&e, &mut h),
1083            Err(ExpansionError::OutputTooSmall)
1084        );
1085    }
1086
1087    // ── Workspace size constant tests ────────────────────────────────────
1088
1089    #[test]
1090    fn workspace_constants_are_sized_for_predicates() {
1091        // The constants must be large enough for the predicate determinants.
1092        // These are lower bounds on the expansion length without compression;
1093        // the constants must be >= these.
1094        assert!(MAX_EXPANSION_ORIENT2 >= 8);
1095        assert!(MAX_EXPANSION_ORIENT3 >= 24);
1096        assert!(MAX_EXPANSION_INCIRCLE >= 96);
1097        assert!(MAX_EXPANSION_INSPHERE >= 2048);
1098    }
1099
1100    // ── Full pipeline test: determinant-like computation ──────────────────
1101
1102    #[test]
1103    fn full_pipeline_2x2_determinant_exact() {
1104        // det = a*d - b*c, computed via expansion arithmetic.
1105        // This is the orient2d determinant pattern.
1106        let a = 1.0;
1107        let b = 1.0 + f64::EPSILON;
1108        let c = 1.0 - f64::EPSILON;
1109        let d = 1.0;
1110
1111        // ad = two_product(a, d) → length-2
1112        let mut ad = [0.0f64; 2];
1113        scalar_product(a, d, &mut ad).unwrap();
1114
1115        // bc = two_product(b, c) → length-2
1116        let mut bc = [0.0f64; 2];
1117        scalar_product(b, c, &mut bc).unwrap();
1118
1119        // negate bc
1120        negate_expansion(&mut bc);
1121
1122        // det = ad + (-bc) = ad - bc
1123        let mut det = [0.0f64; 8];
1124        let n = expansion_sum(&ad, &bc, &mut det).unwrap();
1125
1126        // Compress
1127        let mut compressed = [0.0f64; 8];
1128        let cn = compress_expansion(&det[..n], &mut compressed).unwrap();
1129
1130        let sign = sign_of_expansion(&compressed[..cn]);
1131
1132        // Exact: a*d - b*c = 1 - (1+eps)(1-eps) = 1 - (1 - eps²) = eps² > 0
1133        let exact_ad = Exact::from_f64(a).mul(Exact::from_f64(d));
1134        let exact_bc = Exact::from_f64(b).mul(Exact::from_f64(c));
1135        let exact_det = exact_ad.add(exact_bc.neg());
1136        let exact_sign = exact_det.sign();
1137
1138        assert_eq!(
1139            sign, exact_sign,
1140            "2x2 determinant sign mismatch: expansion says {sign:?}, exact says {exact_sign:?}"
1141        );
1142
1143        // Also verify the exact value matches
1144        let exact_h = expansion_to_exact(&compressed[..cn]);
1145        assert!(
1146            exact_h.equals(&exact_det),
1147            "2x2 determinant exact value mismatch"
1148        );
1149    }
1150
1151    #[test]
1152    fn full_pipeline_3term_sum_adversarial() {
1153        // Three terms that cancel, computed via expansion arithmetic.
1154        // a = 1e100, b = -1e100 (as f64, -1e100 + 1e-100 is just -1e100
1155        // because 1e-100 is below the ULP of 1e100), c = -1e-100.
1156        // Exact result: a + b + c = 1e100 + (-1e100) + (-1e-100) = -1e-100.
1157        // The expansion should preserve the tiny -1e-100 value exactly,
1158        // even though it's far below the ULP of the intermediate 1e100.
1159        let a = 1e100;
1160        let b = -1e100;
1161        let c = -1e-100;
1162
1163        // Start with a as a length-1 expansion
1164        let e = [a];
1165        let mut h1 = [0.0f64; 2];
1166        let n1 = grow_expansion(&e, b, &mut h1).unwrap();
1167
1168        let mut h2 = [0.0f64; 4];
1169        let n2 = grow_expansion(&h1[..n1], c, &mut h2).unwrap();
1170
1171        let mut h3 = [0.0f64; 4];
1172        let n3 = compress_expansion(&h2[..n2], &mut h3).unwrap();
1173
1174        let exact_a = Exact::from_f64(a);
1175        let exact_b = Exact::from_f64(b);
1176        let exact_c = Exact::from_f64(c);
1177        let exact_result = exact_a.add(exact_b).add(exact_c);
1178        let exact_h = expansion_to_exact(&h3[..n3]);
1179
1180        assert!(
1181            exact_h.equals(&exact_result),
1182            "3-term adversarial sum: exact mismatch — expected {:?}, got {:?}",
1183            exact_result,
1184            exact_h
1185        );
1186
1187        // The exact result should be -1e-100 (negative, not zero).
1188        assert_eq!(
1189            exact_result.sign(),
1190            Sign::Negative,
1191            "3-term adversarial sum: expected negative (-1e-100)"
1192        );
1193    }
1194
1195    #[test]
1196    fn full_pipeline_scale_then_sum() {
1197        // Compute (a*b + c*d) using scale + sum, the pattern used in
1198        // determinant computation.
1199        let a = 1.0;
1200        let b = 1.0 + f64::EPSILON;
1201        let c = 1.0 - f64::EPSILON;
1202        let d = 1.0 + 2.0 * f64::EPSILON;
1203
1204        // ab = scale([a], b) → length-2
1205        let mut ab = [0.0f64; 4];
1206        let nab = scale_expansion(&[a], b, &mut ab).unwrap();
1207
1208        // cd = scale([c], d) → length-2
1209        let mut cd = [0.0f64; 4];
1210        let ncd = scale_expansion(&[c], d, &mut cd).unwrap();
1211
1212        // result = ab + cd
1213        let mut result = [0.0f64; 8];
1214        let n = expansion_sum(&ab[..nab], &cd[..ncd], &mut result).unwrap();
1215
1216        let exact_ab = Exact::from_f64(a).mul(Exact::from_f64(b));
1217        let exact_cd = Exact::from_f64(c).mul(Exact::from_f64(d));
1218        let exact_result = exact_ab.add(exact_cd);
1219        let exact_h = expansion_to_exact(&result[..n]);
1220
1221        assert!(
1222            exact_h.equals(&exact_result),
1223            "scale+sum pipeline: exact mismatch"
1224        );
1225    }
1226
1227    // ── Negate test ──────────────────────────────────────────────────────
1228
1229    #[test]
1230    fn negate_flips_sign() {
1231        let mut e = [1.0, -2.0, 3.0];
1232        negate_expansion(&mut e);
1233        assert_eq!(e, [-1.0, 2.0, -3.0]);
1234    }
1235
1236    // ── Convenience wrapper tests ────────────────────────────────────────
1237
1238    #[test]
1239    fn scalar_product_writes_two_components() {
1240        let mut h = [0.0f64; 2];
1241        let n = scalar_product(3.0, 7.0, &mut h).unwrap();
1242        assert_eq!(n, 2);
1243        assert_eq!(h[0], 21.0); // exact product, no error
1244        assert_eq!(h[1], 0.0);
1245    }
1246
1247    #[test]
1248    fn scalar_sum_writes_two_components() {
1249        let mut h = [0.0f64; 2];
1250        let n = scalar_sum(1e100, 1e-100, &mut h).unwrap();
1251        assert_eq!(n, 2);
1252        // The sum is 1e100 (rounded), the error is 1e-100.
1253        assert_eq!(h[0], 1e100);
1254    }
1255
1256    #[test]
1257    fn scalar_product_rejects_small_buffer() {
1258        let mut h = [0.0f64; 1];
1259        assert_eq!(
1260            scalar_product(1.0, 2.0, &mut h),
1261            Err(ExpansionError::OutputTooSmall)
1262        );
1263    }
1264
1265    // ── Sign enum tests ──────────────────────────────────────────────────
1266
1267    #[test]
1268    fn sign_flip() {
1269        assert_eq!(Sign::Positive.flip(), Sign::Negative);
1270        assert_eq!(Sign::Negative.flip(), Sign::Positive);
1271        assert_eq!(Sign::Zero.flip(), Sign::Zero);
1272    }
1273
1274    #[test]
1275    fn sign_from_f64() {
1276        assert_eq!(Sign::from_f64(1.0), Sign::Positive);
1277        assert_eq!(Sign::from_f64(-1.0), Sign::Negative);
1278        assert_eq!(Sign::from_f64(0.0), Sign::Zero);
1279        assert_eq!(Sign::from_f64(1e-300), Sign::Positive);
1280        assert_eq!(Sign::from_f64(-1e-300), Sign::Negative);
1281    }
1282}