1pub const MAX_EXPANSION_ORIENT2: usize = 8;
57
58pub const MAX_EXPANSION_ORIENT3: usize = 24;
62
63pub const MAX_EXPANSION_INCIRCLE: usize = 96;
67
68pub const MAX_EXPANSION_INSPHERE: usize = 2048;
78
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86pub enum ExpansionError {
87 OutputTooSmall,
89}
90
91impl core::fmt::Display for ExpansionError {
92 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#[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#[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#[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#[inline]
157pub fn two_diff(a: f64, b: f64) -> (f64, f64) {
158 two_sum(a, -b)
159}
160
161pub 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 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
201pub 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 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 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
243pub 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 let mut ei = 0usize; let mut fi = 0usize; let mut hi = 0usize; 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 if from_e {
285 ei = 1;
286 } else {
287 fi = 1;
288 }
289
290 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 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 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 h[hi] = current;
332 hi += 1;
333
334 Ok(hi)
335}
336
337pub 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 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 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 if q != 0.0 || out == 0 {
397 h[out] = q;
398 out += 1;
399 }
400
401 Ok(out)
402}
403
404#[inline]
406pub fn negate_expansion(e: &mut [f64]) {
407 for x in e.iter_mut() {
408 *x = -*x;
409 }
410}
411
412#[derive(Debug, Clone, Copy, PartialEq, Eq)]
418pub enum Sign {
419 Negative = -1,
420 Zero = 0,
421 Positive = 1,
422}
423
424impl Sign {
425 #[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 #[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#[inline]
459pub fn sign_of_expansion(e: &[f64]) -> Sign {
460 if e.is_empty() {
461 return Sign::Zero;
462 }
463 Sign::from_f64(e[e.len() - 1])
466}
467
468#[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#[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#[cfg(test)]
506mod tests {
507 use super::*;
508
509 use num_bigint::BigInt;
518
519 #[derive(Debug, Clone)]
521 struct Exact {
522 mantissa: BigInt,
523 exponent: i32,
524 }
525
526 impl Exact {
527 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 Exact {
543 mantissa: BigInt::from(sign) * BigInt::from(raw_mant),
544 exponent: -1074,
545 }
546 } else {
547 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 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 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 if diff > 0 {
576 hi.mantissa <<= diff;
577 }
578 Exact {
579 mantissa: lo.mantissa + hi.mantissa,
580 exponent: lo.exponent,
581 }
582 }
583
584 fn mul(self, other: Self) -> Self {
586 Exact {
587 mantissa: self.mantissa * other.mantissa,
588 exponent: self.exponent + other.exponent,
589 }
590 }
591
592 fn neg(self) -> Self {
594 Exact {
595 mantissa: -self.mantissa,
596 exponent: self.exponent,
597 }
598 }
599
600 fn equals(&self, other: &Self) -> bool {
603 let a = self.clone().normalize();
605 let b = other.clone().normalize();
606 a.mantissa == b.mantissa && a.exponent == b.exponent
607 }
608
609 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 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 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 #[test]
652 fn two_sum_is_error_free() {
653 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 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 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 #[test]
746 fn grow_expansion_adds_scalar_exactly() {
747 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 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 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 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 let (s, e_err) = two_sum(-1.0, 1.0 + f64::EPSILON);
811 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 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 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 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 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 assert!(n <= e.len());
907 }
908
909 #[test]
910 fn compress_preserves_value() {
911 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 #[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 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 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 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 #[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 #[test]
1047 fn grow_expansion_rejects_small_buffer() {
1048 let e = [1.0, 2.0, 3.0];
1049 let mut h = [0.0f64; 3]; 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]; 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]; 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]; assert_eq!(
1082 compress_expansion(&e, &mut h),
1083 Err(ExpansionError::OutputTooSmall)
1084 );
1085 }
1086
1087 #[test]
1090 fn workspace_constants_are_sized_for_predicates() {
1091 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 #[test]
1103 fn full_pipeline_2x2_determinant_exact() {
1104 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 let mut ad = [0.0f64; 2];
1113 scalar_product(a, d, &mut ad).unwrap();
1114
1115 let mut bc = [0.0f64; 2];
1117 scalar_product(b, c, &mut bc).unwrap();
1118
1119 negate_expansion(&mut bc);
1121
1122 let mut det = [0.0f64; 8];
1124 let n = expansion_sum(&ad, &bc, &mut det).unwrap();
1125
1126 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 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 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 let a = 1e100;
1160 let b = -1e100;
1161 let c = -1e-100;
1162
1163 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 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 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 let mut ab = [0.0f64; 4];
1206 let nab = scale_expansion(&[a], b, &mut ab).unwrap();
1207
1208 let mut cd = [0.0f64; 4];
1210 let ncd = scale_expansion(&[c], d, &mut cd).unwrap();
1211
1212 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 #[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 #[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); 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 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 #[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}