Skip to main content

neco_expr/
float.rs

1use core::cmp::Ordering;
2
3#[cfg(test)]
4use neco_algnum::RepresentationResource;
5use neco_algnum::{AlgnumError, IsolatingInterval};
6use neco_bigint::{
7    BigInt, BigUint, BigintError, Dyadic, DyadicEnclosure, RawRational, ReducedRational, Sign,
8};
9use neco_formsum::{FormSum, FormSumErrorKind, RawFormSum, RawTerm};
10use neco_monomial::RawMonomial;
11
12use crate::{AbsoluteBits, ExactValue, ExprId, IsolationCache, StorageError};
13
14const SIGN_MASK: u64 = 1_u64 << 63;
15const MAX_FINITE_BITS: u64 = 0x7fef_ffff_ffff_ffff;
16const NEGATIVE_KEY_START: u64 = 0x0010_0000_0000_0000;
17const NEGATIVE_COUNT: u64 = 0x7fef_ffff_ffff_ffff;
18const LAST_ORDERED: u64 = NEGATIVE_COUNT + MAX_FINITE_BITS;
19
20#[derive(Debug)]
21pub struct CertifiedF64 {
22    value: f64,
23    enclosure: DyadicEnclosure,
24    absolute_error: Dyadic,
25}
26
27impl CertifiedF64 {
28    pub fn value(&self) -> f64 {
29        self.value
30    }
31
32    pub fn enclosure(&self) -> &DyadicEnclosure {
33        &self.enclosure
34    }
35
36    pub fn absolute_error(&self) -> &Dyadic {
37        &self.absolute_error
38    }
39
40    pub fn enclosure_width(&self) -> Result<Dyadic, BigintError> {
41        self.enclosure.width()
42    }
43
44    pub fn try_clone(&self) -> Result<Self, BigintError> {
45        Ok(Self {
46            value: self.value,
47            enclosure: self.enclosure.try_clone()?,
48            absolute_error: self.absolute_error.try_clone()?,
49        })
50    }
51
52    pub(crate) fn resolve(
53        value: &ExactValue,
54        expr: ExprId,
55        bits: AbsoluteBits,
56        isolation: &mut IsolationCache,
57    ) -> Result<Self, FloatError> {
58        let comparable = ComparableExact::new(value)?;
59        let rounded = nearest_f64(&comparable)?;
60        let enclosure = enclose_exact(value, expr, bits, isolation)?;
61        let exact_float = Dyadic::from_f64_exact(rounded).map_err(FloatError::Bigint)?;
62        let absolute_error =
63            absolute_error(&exact_float, &enclosure).map_err(FloatError::Bigint)?;
64        Ok(Self {
65            value: rounded,
66            enclosure,
67            absolute_error,
68        })
69    }
70
71    pub(crate) fn resolve_for_requirement(
72        value: &ExactValue,
73        expr: ExprId,
74        bits: AbsoluteBits,
75        isolation: &mut IsolationCache,
76    ) -> Result<Self, PrecisionResolutionError> {
77        let resolved =
78            Self::resolve(value, expr, bits, isolation).map_err(PrecisionResolutionError::Float)?;
79        let width =
80            resolved
81                .enclosure
82                .width()
83                .map_err(|error| PrecisionResolutionError::WidthFailure {
84                    requested: bits,
85                    error,
86                })?;
87        let maximum = Dyadic::new(
88            BigInt::one()
89                .map_err(|error| PrecisionResolutionError::Float(FloatError::Bigint(error)))?,
90            bits.get(),
91        );
92        if width > maximum {
93            return Err(PrecisionResolutionError::Width {
94                requested: bits,
95                width,
96            });
97        }
98        Ok(resolved)
99    }
100}
101
102impl PartialEq for CertifiedF64 {
103    fn eq(&self, other: &Self) -> bool {
104        self.value.to_bits() == other.value.to_bits()
105            && self.enclosure == other.enclosure
106            && self.absolute_error == other.absolute_error
107    }
108}
109
110impl Eq for CertifiedF64 {}
111
112#[derive(Clone, Copy, Debug, Eq, PartialEq)]
113pub struct ProjectionPolicy {
114    absolute_bits: AbsoluteBits,
115}
116
117impl ProjectionPolicy {
118    pub const fn new(absolute_bits: AbsoluteBits) -> Self {
119        Self { absolute_bits }
120    }
121
122    pub const fn absolute_bits(self) -> AbsoluteBits {
123        self.absolute_bits
124    }
125}
126
127#[derive(Debug, Eq, PartialEq)]
128pub struct CertifiedScalarProjection {
129    policy: ProjectionPolicy,
130    certified: CertifiedF64,
131}
132
133impl CertifiedScalarProjection {
134    pub const fn policy(&self) -> ProjectionPolicy {
135        self.policy
136    }
137
138    pub fn certified(&self) -> &CertifiedF64 {
139        &self.certified
140    }
141
142    pub fn value(&self) -> f64 {
143        self.certified.value()
144    }
145
146    pub fn enclosure(&self) -> &DyadicEnclosure {
147        self.certified.enclosure()
148    }
149
150    pub fn absolute_error(&self) -> &Dyadic {
151        self.certified.absolute_error()
152    }
153
154    pub fn try_clone(&self) -> Result<Self, ScalarProjectionError> {
155        Ok(Self {
156            policy: self.policy,
157            certified: self
158                .certified
159                .try_clone()
160                .map_err(ScalarProjectionError::Bigint)?,
161        })
162    }
163}
164
165#[derive(Debug, Eq, PartialEq)]
166pub enum ScalarProjectionError {
167    FloatOutOfRange,
168    Bigint(BigintError),
169    Algnum(AlgnumError),
170    Storage(StorageError),
171}
172
173pub fn project_exact_value_f64(
174    value: &ExactValue,
175    policy: ProjectionPolicy,
176) -> Result<CertifiedScalarProjection, ScalarProjectionError> {
177    let comparable = ComparableExact::new(value).map_err(ScalarProjectionError::from_float)?;
178    let rounded = nearest_f64(&comparable).map_err(ScalarProjectionError::from_float)?;
179    let enclosure = enclose_exact_without_cache(value, policy.absolute_bits())
180        .map_err(ScalarProjectionError::from_float)?;
181    let exact_float = Dyadic::from_f64_exact(rounded).map_err(ScalarProjectionError::Bigint)?;
182    let absolute_error =
183        absolute_error(&exact_float, &enclosure).map_err(ScalarProjectionError::Bigint)?;
184    Ok(CertifiedScalarProjection {
185        policy,
186        certified: CertifiedF64 {
187            value: rounded,
188            enclosure,
189            absolute_error,
190        },
191    })
192}
193
194impl ScalarProjectionError {
195    fn from_float(error: FloatError) -> Self {
196        match error {
197            FloatError::OutOfRange => Self::FloatOutOfRange,
198            FloatError::Bigint(error) | FloatError::EnclosureBigint { error, .. } => {
199                Self::Bigint(error)
200            }
201            FloatError::Algnum(error) | FloatError::EnclosureAlgnum { error, .. } => {
202                Self::Algnum(error)
203            }
204            FloatError::Storage(error) => Self::Storage(error),
205        }
206    }
207}
208
209impl core::fmt::Display for ScalarProjectionError {
210    fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
211        match self {
212            Self::FloatOutOfRange => formatter.write_str("exact value is outside finite f64 range"),
213            Self::Bigint(error) => error.fmt(formatter),
214            Self::Algnum(error) => error.fmt(formatter),
215            Self::Storage(error) => error.fmt(formatter),
216        }
217    }
218}
219
220#[cfg(feature = "std")]
221impl std::error::Error for ScalarProjectionError {}
222
223#[derive(Debug, Eq, PartialEq)]
224pub enum EnclosureProjectionError {
225    Bigint(BigintError),
226    InsufficientWidth {
227        requested: AbsoluteBits,
228        width: Dyadic,
229    },
230}
231
232impl core::fmt::Display for EnclosureProjectionError {
233    fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
234        match self {
235            Self::Bigint(error) => error.fmt(formatter),
236            Self::InsufficientWidth { requested, width } => write!(
237                formatter,
238                "enclosure width {width:?} exceeds the maximum width for {requested:?}"
239            ),
240        }
241    }
242}
243
244#[cfg(feature = "std")]
245impl std::error::Error for EnclosureProjectionError {}
246
247pub fn project_enclosure_f64(
248    enclosure: DyadicEnclosure,
249    bits: AbsoluteBits,
250) -> Result<CertifiedF64, EnclosureProjectionError> {
251    let width = enclosure
252        .width()
253        .map_err(EnclosureProjectionError::Bigint)?;
254    let maximum = Dyadic::new(
255        BigInt::one().map_err(EnclosureProjectionError::Bigint)?,
256        bits.get(),
257    );
258    if width > maximum {
259        return Err(EnclosureProjectionError::InsufficientWidth {
260            requested: bits,
261            width,
262        });
263    }
264    let midpoint = enclosure
265        .midpoint()
266        .map_err(EnclosureProjectionError::Bigint)?;
267    let value = midpoint
268        .round_to_f64_ties_even()
269        .map_err(EnclosureProjectionError::Bigint)?;
270    let exact_float = Dyadic::from_f64_exact(value).map_err(EnclosureProjectionError::Bigint)?;
271    let absolute_error =
272        absolute_error(&exact_float, &enclosure).map_err(EnclosureProjectionError::Bigint)?;
273    Ok(CertifiedF64 {
274        value,
275        enclosure,
276        absolute_error,
277    })
278}
279
280#[derive(Debug)]
281pub(crate) enum FloatError {
282    OutOfRange,
283    Bigint(BigintError),
284    Algnum(AlgnumError),
285    EnclosureBigint {
286        requested: AbsoluteBits,
287        error: BigintError,
288    },
289    EnclosureAlgnum {
290        requested: AbsoluteBits,
291        error: AlgnumError,
292    },
293    Storage(StorageError),
294}
295
296pub(crate) enum PrecisionResolutionError {
297    Float(FloatError),
298    Width {
299        requested: AbsoluteBits,
300        width: Dyadic,
301    },
302    WidthFailure {
303        requested: AbsoluteBits,
304        error: BigintError,
305    },
306}
307
308enum ComparableExact {
309    Rational(ReducedRational),
310    FormSum(FormSum),
311    Algebraic(IsolatingInterval),
312}
313
314impl ComparableExact {
315    fn new(value: &ExactValue) -> Result<Self, FloatError> {
316        match value {
317            ExactValue::Monomial(value) => FormSum::from_monomial(value)
318                .map_err(map_formsum_error)
319                .and_then(Self::from_form_sum),
320            ExactValue::FormSum(value) => value
321                .try_clone()
322                .map_err(map_formsum_error)
323                .and_then(Self::from_form_sum),
324            ExactValue::Algebraic(value) => value
325                .enclose(64)
326                .map(Self::Algebraic)
327                .map_err(FloatError::Algnum),
328        }
329    }
330
331    fn from_form_sum(value: FormSum) -> Result<Self, FloatError> {
332        match value.terms() {
333            [] => ReducedRational::from_bigint(BigInt::zero())
334                .map(Self::Rational)
335                .map_err(FloatError::Bigint),
336            [(basis, coefficient)] if basis.factors().is_empty() => coefficient
337                .try_clone()
338                .map(Self::Rational)
339                .map_err(FloatError::Bigint),
340            _ => Ok(Self::FormSum(value)),
341        }
342    }
343
344    fn compare(&self, rhs: &Dyadic) -> Result<Ordering, FloatError> {
345        match self {
346            Self::Rational(value) => compare_rational_dyadic(value, rhs),
347            Self::FormSum(value) => {
348                let rhs = form_sum_from_dyadic(rhs)?;
349                value
350                    .sub(&rhs)
351                    .and_then(|difference| difference.sign())
352                    .map(|sign| match sign {
353                        Sign::Negative => Ordering::Less,
354                        Sign::Zero => Ordering::Equal,
355                        Sign::Positive => Ordering::Greater,
356                    })
357                    .map_err(map_formsum_error)
358            }
359            Self::Algebraic(interval) if interval.enclosure().upper() < rhs => Ok(Ordering::Less),
360            Self::Algebraic(interval) if interval.enclosure().lower() > rhs => {
361                Ok(Ordering::Greater)
362            }
363            Self::Algebraic(interval) => interval
364                .value()
365                .compare_dyadic(rhs)
366                .map_err(FloatError::Algnum),
367        }
368    }
369}
370
371fn compare_rational_dyadic(value: &ReducedRational, rhs: &Dyadic) -> Result<Ordering, FloatError> {
372    let numerator = value.numerator();
373    let left = if rhs.exponent() == 0 || numerator.is_zero() {
374        numerator.try_clone()
375    } else {
376        numerator
377            .magnitude()
378            .shl_bits(rhs.exponent() as usize)
379            .map(|magnitude| BigInt::from_sign_magnitude(numerator.sign(), magnitude))
380    }
381    .map_err(FloatError::Bigint)?;
382    let denominator = value
383        .denominator()
384        .try_clone()
385        .map(|magnitude| BigInt::from_sign_magnitude(Sign::Positive, magnitude))
386        .map_err(FloatError::Bigint)?;
387    let right = rhs
388        .integer()
389        .mul(&denominator)
390        .map_err(FloatError::Bigint)?;
391    Ok(left.cmp(&right))
392}
393
394fn form_sum_from_dyadic(value: &Dyadic) -> Result<FormSum, FloatError> {
395    let denominator = BigUint::one()
396        .and_then(|one| one.shl_bits(value.exponent() as usize))
397        .map_err(FloatError::Bigint)?;
398    let numerator = value.integer().try_clone().map_err(FloatError::Bigint)?;
399    RawFormSum::new(alloc::vec![RawTerm::new(
400        RawRational::new(numerator, denominator),
401        RawMonomial::positive(alloc::vec::Vec::new()),
402    )])
403    .normalize()
404    .map_err(|errors| map_formsum_error(errors.into_parts().0))
405}
406
407fn map_formsum_error(error: FormSumErrorKind) -> FloatError {
408    match error {
409        FormSumErrorKind::Bigint(error) => FloatError::Bigint(error),
410        error => FloatError::Algnum(AlgnumError::FormSum(error)),
411    }
412}
413
414fn nearest_f64(value: &ComparableExact) -> Result<f64, FloatError> {
415    let minimum = Dyadic::from_f64_exact(f64::from_bits(SIGN_MASK | MAX_FINITE_BITS))
416        .map_err(FloatError::Bigint)?;
417    let maximum =
418        Dyadic::from_f64_exact(f64::from_bits(MAX_FINITE_BITS)).map_err(FloatError::Bigint)?;
419    match value.compare(&minimum)? {
420        Ordering::Less => return Err(FloatError::OutOfRange),
421        Ordering::Equal => return Ok(f64::from_bits(SIGN_MASK | MAX_FINITE_BITS)),
422        Ordering::Greater => {}
423    }
424    match value.compare(&maximum)? {
425        Ordering::Greater => return Err(FloatError::OutOfRange),
426        Ordering::Equal => return Ok(f64::from_bits(MAX_FINITE_BITS)),
427        Ordering::Less => {}
428    }
429
430    let mut lower = 0_u64;
431    let mut upper = LAST_ORDERED;
432    while lower < upper {
433        let middle = lower + (upper - lower) / 2 + 1;
434        let candidate = exact_ordered(middle)?;
435        match value.compare(&candidate)? {
436            Ordering::Less => upper = middle - 1,
437            Ordering::Equal => return Ok(f64::from_bits(ordered_to_bits(middle))),
438            Ordering::Greater => lower = middle,
439        }
440    }
441
442    let lower_bits = ordered_to_bits(lower);
443    let upper_bits = ordered_to_bits(lower + 1);
444    let lower_value =
445        Dyadic::from_f64_exact(f64::from_bits(lower_bits)).map_err(FloatError::Bigint)?;
446    let upper_value =
447        Dyadic::from_f64_exact(f64::from_bits(upper_bits)).map_err(FloatError::Bigint)?;
448    let midpoint = lower_value
449        .midpoint(&upper_value)
450        .map_err(FloatError::Bigint)?;
451    let chosen = match value.compare(&midpoint)? {
452        Ordering::Less => lower_bits,
453        Ordering::Greater => upper_bits,
454        Ordering::Equal if lower_bits & 1 == 0 => lower_bits,
455        Ordering::Equal => upper_bits,
456    };
457    Ok(f64::from_bits(if chosen == SIGN_MASK { 0 } else { chosen }))
458}
459
460fn exact_ordered(ordered: u64) -> Result<Dyadic, FloatError> {
461    Dyadic::from_f64_exact(f64::from_bits(ordered_to_bits(ordered))).map_err(FloatError::Bigint)
462}
463
464fn ordered_to_bits(ordered: u64) -> u64 {
465    if ordered < NEGATIVE_COUNT {
466        !(NEGATIVE_KEY_START + ordered)
467    } else {
468        ordered - NEGATIVE_COUNT
469    }
470}
471
472fn enclose_exact(
473    value: &ExactValue,
474    expr: ExprId,
475    bits: AbsoluteBits,
476    isolation: &mut IsolationCache,
477) -> Result<DyadicEnclosure, FloatError> {
478    match value {
479        ExactValue::Algebraic(value) => {
480            if let Some(cached) = isolation.get(expr, bits) {
481                return cached.enclosure().try_clone().map_err(|error| {
482                    FloatError::EnclosureBigint {
483                        requested: bits,
484                        error,
485                    }
486                });
487            }
488            let interval = enclose_algebraic(value, bits.get())
489                .map_err(|error| enclosure_error(error, bits))?;
490            let enclosure =
491                interval
492                    .enclosure()
493                    .try_clone()
494                    .map_err(|error| FloatError::EnclosureBigint {
495                        requested: bits,
496                        error,
497                    })?;
498            isolation
499                .insert(expr, bits, interval)
500                .map_err(FloatError::Storage)?;
501            Ok(enclosure)
502        }
503        _ => enclose_exact_without_cache(value, bits).map_err(|error| enclosure_error(error, bits)),
504    }
505}
506
507fn enclosure_error(error: FloatError, requested: AbsoluteBits) -> FloatError {
508    match error {
509        FloatError::Bigint(error) => FloatError::EnclosureBigint { requested, error },
510        FloatError::Algnum(error) => FloatError::EnclosureAlgnum { requested, error },
511        other => other,
512    }
513}
514
515fn enclose_exact_without_cache(
516    value: &ExactValue,
517    bits: AbsoluteBits,
518) -> Result<DyadicEnclosure, FloatError> {
519    match value {
520        ExactValue::Monomial(value) => {
521            let value = FormSum::from_monomial(value).map_err(map_formsum_error)?;
522            enclose_form_sum(&value, bits.get())
523        }
524        ExactValue::FormSum(value) => enclose_form_sum(value, bits.get()),
525        ExactValue::Algebraic(value) => enclose_algebraic(value, bits.get())?
526            .enclosure()
527            .try_clone()
528            .map_err(FloatError::Bigint),
529    }
530}
531
532fn enclose_form_sum(value: &FormSum, bits: u32) -> Result<DyadicEnclosure, FloatError> {
533    #[cfg(test)]
534    if enclosure_failure_is(EnclosureContact::FormSum) {
535        let required = BigUint::try_from(33_u8).map_err(FloatError::Bigint)?;
536        return Err(FloatError::Bigint(BigintError::ExponentOverflow {
537            required,
538            maximum: 32,
539        }));
540    }
541    value.enclose(bits).map_err(map_formsum_error)
542}
543
544fn enclose_algebraic(
545    value: &neco_algnum::RealAlgebraic,
546    bits: u32,
547) -> Result<IsolatingInterval, FloatError> {
548    #[cfg(test)]
549    ENCLOSURE_CALLS.with(|calls| calls.set(calls.get() + 1));
550    #[cfg(test)]
551    if enclosure_failure_is(EnclosureContact::Algebraic) {
552        let required = BigUint::try_from(41_u8).map_err(FloatError::Bigint)?;
553        let maximum = BigUint::try_from(40_u8).map_err(FloatError::Bigint)?;
554        return Err(FloatError::Algnum(AlgnumError::RepresentationLimit {
555            resource: RepresentationResource::RootDegree,
556            required,
557            maximum,
558        }));
559    }
560    value.enclose(bits).map_err(FloatError::Algnum)
561}
562
563#[cfg(test)]
564#[derive(Clone, Copy, Eq, PartialEq)]
565enum EnclosureContact {
566    FormSum,
567    Algebraic,
568}
569
570#[cfg(test)]
571std::thread_local! {
572    static ENCLOSURE_FAILURE: core::cell::Cell<Option<EnclosureContact>> = const { core::cell::Cell::new(None) };
573    static ENCLOSURE_CALLS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
574}
575
576#[cfg(test)]
577fn enclosure_failure_is(contact: EnclosureContact) -> bool {
578    ENCLOSURE_FAILURE.with(|configured| configured.get() == Some(contact))
579}
580
581#[cfg(test)]
582fn with_enclosure_failure<R>(contact: EnclosureContact, operation: impl FnOnce() -> R) -> R {
583    ENCLOSURE_FAILURE.with(|configured| configured.set(Some(contact)));
584    let result = operation();
585    ENCLOSURE_FAILURE.with(|configured| configured.set(None));
586    result
587}
588
589#[cfg(test)]
590fn with_enclosure_call_count<R>(operation: impl FnOnce() -> R) -> (R, usize) {
591    ENCLOSURE_CALLS.with(|calls| calls.set(0));
592    let result = operation();
593    let calls = ENCLOSURE_CALLS.with(core::cell::Cell::get);
594    (result, calls)
595}
596
597fn absolute_error(value: &Dyadic, enclosure: &DyadicEnclosure) -> Result<Dyadic, BigintError> {
598    let lower = abs_dyadic(&value.sub(enclosure.lower())?)?;
599    let upper = abs_dyadic(&enclosure.upper().sub(value)?)?;
600    Ok(if lower >= upper { lower } else { upper })
601}
602
603fn abs_dyadic(value: &Dyadic) -> Result<Dyadic, BigintError> {
604    let magnitude: BigUint = value.integer().abs()?;
605    Ok(Dyadic::new(
606        BigInt::from_sign_magnitude(Sign::Positive, magnitude),
607        value.exponent(),
608    ))
609}
610
611#[cfg(test)]
612mod tests {
613    use neco_algnum::{AlgnumError, RealAlgebraic, RepresentationResource};
614    use neco_bigint::{BigInt, BigUint, BigintError, Dyadic, RawRational, Sign};
615    use neco_formsum::{FormSum, RawFormSum, RawTerm};
616    use neco_monomial::{Monomial, RawMonomial, RawPower};
617
618    use super::{
619        form_sum_from_dyadic, nearest_f64, ordered_to_bits, with_enclosure_call_count,
620        with_enclosure_failure, CertifiedF64, ComparableExact, EnclosureContact, FloatError,
621        PrecisionResolutionError, LAST_ORDERED, MAX_FINITE_BITS, NEGATIVE_COUNT, SIGN_MASK,
622    };
623    use crate::{
624        project_exact_value_f64, AbsoluteBits, Assignments, AtomId, AtomStore, ConsumerId,
625        ExactValue, ExprGraph, ExprId, ExprNode, IsolationCache, PrecisionRequirements,
626        ProjectionPolicy, ResolveError, Resolver,
627    };
628
629    #[test]
630    fn ordered_bits_exclude_negative_zero() {
631        assert_eq!(ordered_to_bits(NEGATIVE_COUNT - 1), 0x8000_0000_0000_0001);
632        assert_eq!(ordered_to_bits(NEGATIVE_COUNT), 0);
633        assert_eq!(ordered_to_bits(NEGATIVE_COUNT + 1), 1);
634    }
635
636    #[test]
637    fn ordered_bits_cover_signed_normal_subnormal_zero_and_finite_endpoints() {
638        let negative_one_bits = (-1.0_f64).to_bits();
639        let negative_one_ordered = (!negative_one_bits) - super::NEGATIVE_KEY_START;
640        let positive_one_ordered = NEGATIVE_COUNT + 1.0_f64.to_bits();
641        let observations = [
642            ordered_to_bits(0),
643            ordered_to_bits(negative_one_ordered),
644            ordered_to_bits(NEGATIVE_COUNT - 1),
645            ordered_to_bits(NEGATIVE_COUNT),
646            ordered_to_bits(NEGATIVE_COUNT + 1),
647            ordered_to_bits(positive_one_ordered),
648            ordered_to_bits(LAST_ORDERED),
649        ];
650        assert_eq!(
651            observations,
652            [
653                (-f64::MAX).to_bits(),
654                (-1.0_f64).to_bits(),
655                0x8000_0000_0000_0001,
656                0,
657                1,
658                1.0_f64.to_bits(),
659                f64::MAX.to_bits(),
660            ]
661        );
662        assert!(observations.windows(2).all(|pair| {
663            f64::from_bits(pair[0]) < f64::from_bits(pair[1]) || (pair[0] == 0 && pair[1] == 1)
664        }));
665    }
666
667    fn resolve_with_injected_enclosure(
668        value: ExactValue,
669        contact: EnclosureContact,
670    ) -> ResolveError {
671        let mut graph = ExprGraph::new();
672        let expression = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
673        let mut atoms = AtomStore::new();
674        atoms.insert(AtomId::new(0), value).unwrap();
675        let mut requirements = PrecisionRequirements::new();
676        requirements
677            .insert(ConsumerId::new(0), AbsoluteBits::new(20))
678            .unwrap();
679        let mut assignments = Assignments::new();
680        assignments.insert(ConsumerId::new(0), expression).unwrap();
681        let (_, _, resolved) = with_enclosure_failure(contact, || {
682            Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
683        })
684        .unwrap();
685        match resolved.get(ConsumerId::new(0)).unwrap() {
686            Err(error) => match error {
687                ResolveError::Bigint(BigintError::ExponentOverflow { required, maximum }) => {
688                    ResolveError::Bigint(BigintError::ExponentOverflow {
689                        required: required.try_clone().unwrap(),
690                        maximum: *maximum,
691                    })
692                }
693                ResolveError::Algnum(AlgnumError::RepresentationLimit {
694                    resource,
695                    required,
696                    maximum,
697                }) => ResolveError::Algnum(AlgnumError::RepresentationLimit {
698                    resource: *resource,
699                    required: required.try_clone().unwrap(),
700                    maximum: maximum.try_clone().unwrap(),
701                }),
702                _ => panic!("unexpected enclosure error: {error:?}"),
703            },
704            Ok(_) => panic!("injected enclosure failure was not observed"),
705        }
706    }
707
708    #[test]
709    fn form_sum_enclosure_bigint_failure_keeps_the_payload() {
710        assert_eq!(
711            resolve_with_injected_enclosure(
712                ExactValue::FormSum(FormSum::one().unwrap()),
713                EnclosureContact::FormSum,
714            ),
715            ResolveError::Bigint(BigintError::ExponentOverflow {
716                required: BigUint::try_from(33_u8).unwrap(),
717                maximum: 32,
718            })
719        );
720    }
721
722    #[test]
723    fn algebraic_enclosure_failure_keeps_the_payload() {
724        let form = FormSum::one().unwrap();
725        assert_eq!(
726            resolve_with_injected_enclosure(
727                ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap()),
728                EnclosureContact::Algebraic,
729            ),
730            ResolveError::Algnum(AlgnumError::RepresentationLimit {
731                resource: RepresentationResource::RootDegree,
732                required: BigUint::try_from(41_u8).unwrap(),
733                maximum: BigUint::try_from(40_u8).unwrap(),
734            })
735        );
736    }
737
738    #[test]
739    fn high_level_resolution_keeps_representation_limit_as_precision_cause() {
740        let form = FormSum::one().unwrap();
741        let exact = ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap());
742        let mut isolation = IsolationCache::new();
743        let result = with_enclosure_failure(EnclosureContact::Algebraic, || {
744            CertifiedF64::resolve_for_requirement(
745                &exact,
746                ExprId::new(0),
747                AbsoluteBits::new(80),
748                &mut isolation,
749            )
750        });
751        assert!(matches!(
752            result,
753            Err(PrecisionResolutionError::Float(
754                FloatError::EnclosureAlgnum {
755                    requested,
756                    error: AlgnumError::RepresentationLimit { .. },
757                }
758            )) if requested.get() == 80
759        ));
760    }
761
762    #[test]
763    fn algebraic_enclosure_is_computed_once_for_each_expression_and_precision() {
764        let form = FormSum::one().unwrap();
765        let mut graph = ExprGraph::new();
766        let expression = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
767        let mut atoms = AtomStore::new();
768        atoms
769            .insert(
770                AtomId::new(0),
771                ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap()),
772            )
773            .unwrap();
774        let mut requirements = PrecisionRequirements::new();
775        let mut assignments = Assignments::new();
776        for (consumer, bits) in [(0, 20), (1, 20), (2, 40)] {
777            requirements
778                .insert(ConsumerId::new(consumer), AbsoluteBits::new(bits))
779                .unwrap();
780            assignments
781                .insert(ConsumerId::new(consumer), expression)
782                .unwrap();
783        }
784        let (result, calls) = with_enclosure_call_count(|| {
785            Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
786        });
787        assert!(result.is_ok());
788        assert_eq!(calls, 2);
789    }
790
791    #[test]
792    fn scalar_projection_carries_its_policy_value_enclosure_and_error() {
793        let policy = ProjectionPolicy::new(AbsoluteBits::new(20));
794        let exact = ExactValue::FormSum(FormSum::one().unwrap());
795        let projection = project_exact_value_f64(&exact, policy).expect("scalar projection");
796        let selected = neco_bigint::Dyadic::from_f64_exact(projection.value()).unwrap();
797
798        assert_eq!(projection.policy(), policy);
799        assert_eq!(projection.value(), 1.0);
800        assert!(projection.enclosure().contains_dyadic(&selected));
801        let zero = BigInt::zero();
802        assert_eq!(projection.absolute_error().integer(), &zero);
803    }
804
805    fn rational(numerator: i64, denominator: u64) -> FormSum {
806        RawFormSum::new(alloc::vec![RawTerm::new(
807            RawRational::new(
808                BigInt::try_from(numerator).unwrap(),
809                BigUint::try_from(denominator).unwrap(),
810            ),
811            RawMonomial::positive(alloc::vec::Vec::new()),
812        )])
813        .normalize()
814        .unwrap()
815    }
816
817    fn power_of_two(exponent: i32) -> FormSum {
818        let shifted = BigUint::one()
819            .unwrap()
820            .shl_bits(exponent.unsigned_abs() as usize)
821            .unwrap();
822        let (numerator, denominator) = if exponent >= 0 {
823            (
824                BigInt::from_sign_magnitude(Sign::Positive, shifted),
825                BigUint::one().unwrap(),
826            )
827        } else {
828            (BigInt::one().unwrap(), shifted)
829        };
830        RawFormSum::new(alloc::vec![RawTerm::new(
831            RawRational::new(numerator, denominator),
832            RawMonomial::positive(alloc::vec::Vec::new()),
833        )])
834        .normalize()
835        .unwrap()
836    }
837
838    fn float_form_sum(bits: u64) -> FormSum {
839        form_sum_from_dyadic(&Dyadic::from_f64_exact(f64::from_bits(bits)).unwrap()).unwrap()
840    }
841
842    fn scaled(value: &FormSum, numerator: i64, denominator: u64) -> FormSum {
843        value.mul(&rational(numerator, denominator)).unwrap()
844    }
845
846    fn rational_samples() -> alloc::vec::Vec<FormSum> {
847        let mut samples = alloc::vec::Vec::new();
848        for (numerator, denominator) in [
849            (0, 1),
850            (1, 1),
851            (-1, 1),
852            (7, 1),
853            (-123_456_789, 1),
854            (1, 2),
855            (-3, 8),
856            (5, 1024),
857            (1, 3),
858            (-1, 3),
859            (22, 7),
860            (-22, 7),
861            (1, 10),
862            (-1, 10),
863            (9_007_199_254_740_993, 1),
864            (-9_007_199_254_740_993, 1),
865            (9_007_199_254_740_993, 8),
866            (1, 1_000_003),
867        ] {
868            samples.push(rational(numerator, denominator));
869        }
870
871        let tiny = scaled(&power_of_two(-1200), 1, 3);
872        let ordered_bits = [
873            0_u64,
874            1,
875            2,
876            3,
877            0x000f_ffff_ffff_fffe,
878            0x000f_ffff_ffff_ffff,
879            0x0010_0000_0000_0000,
880            0x0010_0000_0000_0001,
881            0x3fef_ffff_ffff_ffff,
882            0x3ff0_0000_0000_0000,
883            0x3ff0_0000_0000_0001,
884            0x3ff0_0000_0000_0002,
885            0x7fef_ffff_ffff_fffd,
886            0x7fef_ffff_ffff_fffe,
887            MAX_FINITE_BITS,
888        ];
889        for bits in ordered_bits {
890            for sign in [0, SIGN_MASK] {
891                let value = float_form_sum(bits | sign);
892                let next = float_form_sum(if bits == MAX_FINITE_BITS {
893                    bits | sign
894                } else {
895                    (bits + 1) | sign
896                });
897                let midpoint = scaled(&value.add(&next).unwrap(), 1, 2);
898                samples.push(value.try_clone().unwrap());
899                samples.push(midpoint.try_clone().unwrap());
900                samples.push(midpoint.add(&tiny).unwrap());
901                samples.push(midpoint.sub(&tiny).unwrap());
902                samples.push(value.add(&tiny).unwrap());
903                samples.push(value.sub(&tiny).unwrap());
904            }
905        }
906
907        let maximum = float_form_sum(MAX_FINITE_BITS);
908        let half_ulp = power_of_two(970);
909        let above_midpoint = maximum.add(&half_ulp).unwrap();
910        for sign in [1, -1] {
911            samples.push(scaled(&above_midpoint, sign, 1));
912            samples.push(scaled(&above_midpoint.add(&tiny).unwrap(), sign, 1));
913            samples.push(scaled(&above_midpoint.sub(&tiny).unwrap(), sign, 1));
914            samples.push(scaled(&maximum.add(&rational(1, 1)).unwrap(), sign, 1));
915            samples.push(scaled(&maximum.sub(&rational(1, 1)).unwrap(), sign, 1));
916            samples.push(scaled(&power_of_two(1024), sign, 1));
917            samples.push(scaled(&power_of_two(1025), sign, 1));
918            samples.push(scaled(&power_of_two(-1075), sign, 1));
919            samples.push(scaled(&power_of_two(-1076), sign, 1));
920            samples.push(scaled(&power_of_two(-1074), sign, 1));
921            samples.push(scaled(&power_of_two(-1075).add(&tiny).unwrap(), sign, 1));
922            samples.push(scaled(&power_of_two(-1075).sub(&tiny).unwrap(), sign, 1));
923            samples.push(scaled(&power_of_two(-1022), sign, 1));
924            samples.push(scaled(&power_of_two(-1023), sign, 1));
925        }
926        samples
927    }
928
929    fn outcome(result: Result<f64, FloatError>) -> Result<u64, &'static str> {
930        match result {
931            Ok(value) => Ok(value.to_bits()),
932            Err(FloatError::OutOfRange) => Err("out of range"),
933            Err(_) => Err("other"),
934        }
935    }
936
937    #[test]
938    fn rational_form_matches_form_sum_comparison_and_nearest() {
939        let probes: alloc::vec::Vec<Dyadic> = [
940            0_u64,
941            1,
942            0x000f_ffff_ffff_ffff,
943            0x0010_0000_0000_0000,
944            0x3ff0_0000_0000_0000,
945            MAX_FINITE_BITS,
946            SIGN_MASK | 1,
947            SIGN_MASK | 0x3ff0_0000_0000_0000,
948            SIGN_MASK | MAX_FINITE_BITS,
949        ]
950        .into_iter()
951        .map(|bits| Dyadic::from_f64_exact(f64::from_bits(bits)).unwrap())
952        .chain([
953            Dyadic::new(BigInt::try_from(3_i32).unwrap(), 7),
954            Dyadic::new(BigInt::try_from(-5_i32).unwrap(), 1100),
955        ])
956        .collect();
957
958        let samples = rational_samples();
959        assert!(samples.len() > 200);
960        for sample in &samples {
961            let fast =
962                ComparableExact::new(&ExactValue::FormSum(sample.try_clone().unwrap())).unwrap();
963            assert!(matches!(fast, ComparableExact::Rational(_)));
964            let general = ComparableExact::FormSum(sample.try_clone().unwrap());
965            for probe in &probes {
966                assert_eq!(
967                    fast.compare(probe).unwrap(),
968                    general.compare(probe).unwrap(),
969                    "{sample:?} {probe:?}"
970                );
971            }
972            assert_eq!(
973                outcome(nearest_f64(&fast)),
974                outcome(nearest_f64(&general)),
975                "{sample:?}"
976            );
977        }
978    }
979
980    #[test]
981    fn monomial_and_zero_select_the_rational_form() {
982        let zero = ComparableExact::new(&ExactValue::Monomial(Monomial::zero())).unwrap();
983        assert!(matches!(zero, ComparableExact::Rational(_)));
984        let one = ComparableExact::new(&ExactValue::Monomial(Monomial::one())).unwrap();
985        assert!(matches!(one, ComparableExact::Rational(_)));
986        assert_eq!(nearest_f64(&one).unwrap().to_bits(), 1.0_f64.to_bits());
987        assert_eq!(nearest_f64(&zero).unwrap().to_bits(), 0);
988
989        let root = RawMonomial::positive(alloc::vec![RawPower::new(
990            BigUint::try_from(2_u32).unwrap(),
991            RawRational::new(BigInt::one().unwrap(), BigUint::try_from(2_u32).unwrap()),
992        )])
993        .normalize()
994        .unwrap();
995        let radical = ComparableExact::new(&ExactValue::Monomial(root)).unwrap();
996        assert!(matches!(radical, ComparableExact::FormSum(_)));
997        let mixed = rational(1, 1)
998            .add(&FormSum::from_monomial(&Monomial::one()).unwrap())
999            .unwrap();
1000        assert!(matches!(
1001            ComparableExact::new(&ExactValue::FormSum(mixed)).unwrap(),
1002            ComparableExact::Rational(_)
1003        ));
1004    }
1005}