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::{BigInt, BigUint, BigintError, Dyadic, DyadicEnclosure, RawRational, Sign};
7use neco_formsum::{FormSum, FormSumErrorKind, RawFormSum, RawTerm};
8use neco_monomial::RawMonomial;
9
10use crate::{AbsoluteBits, ExactValue, ExprId, IsolationCache, StorageError};
11
12const SIGN_MASK: u64 = 1_u64 << 63;
13const MAX_FINITE_BITS: u64 = 0x7fef_ffff_ffff_ffff;
14const NEGATIVE_KEY_START: u64 = 0x0010_0000_0000_0000;
15const NEGATIVE_COUNT: u64 = 0x7fef_ffff_ffff_ffff;
16const LAST_ORDERED: u64 = NEGATIVE_COUNT + MAX_FINITE_BITS;
17
18#[derive(Debug)]
19pub struct CertifiedF64 {
20    value: f64,
21    enclosure: DyadicEnclosure,
22    absolute_error: Dyadic,
23}
24
25impl CertifiedF64 {
26    pub fn value(&self) -> f64 {
27        self.value
28    }
29
30    pub fn enclosure(&self) -> &DyadicEnclosure {
31        &self.enclosure
32    }
33
34    pub fn absolute_error(&self) -> &Dyadic {
35        &self.absolute_error
36    }
37
38    pub fn try_clone(&self) -> Result<Self, BigintError> {
39        Ok(Self {
40            value: self.value,
41            enclosure: self.enclosure.try_clone()?,
42            absolute_error: self.absolute_error.try_clone()?,
43        })
44    }
45
46    pub(crate) fn resolve(
47        value: &ExactValue,
48        expr: ExprId,
49        bits: AbsoluteBits,
50        isolation: &mut IsolationCache,
51    ) -> Result<Self, FloatError> {
52        let comparable = ComparableExact::new(value)?;
53        let rounded = nearest_f64(&comparable)?;
54        let enclosure = enclose_exact(value, expr, bits, isolation)?;
55        let exact_float = Dyadic::from_f64_exact(rounded).map_err(FloatError::Bigint)?;
56        let absolute_error = absolute_error(&exact_float, &enclosure)?;
57        Ok(Self {
58            value: rounded,
59            enclosure,
60            absolute_error,
61        })
62    }
63}
64
65impl PartialEq for CertifiedF64 {
66    fn eq(&self, other: &Self) -> bool {
67        self.value.to_bits() == other.value.to_bits()
68            && self.enclosure == other.enclosure
69            && self.absolute_error == other.absolute_error
70    }
71}
72
73impl Eq for CertifiedF64 {}
74
75#[derive(Clone, Copy, Debug, Eq, PartialEq)]
76pub struct ProjectionPolicy {
77    absolute_bits: AbsoluteBits,
78}
79
80impl ProjectionPolicy {
81    pub const fn new(absolute_bits: AbsoluteBits) -> Self {
82        Self { absolute_bits }
83    }
84
85    pub const fn absolute_bits(self) -> AbsoluteBits {
86        self.absolute_bits
87    }
88}
89
90#[derive(Debug, Eq, PartialEq)]
91pub struct CertifiedScalarProjection {
92    policy: ProjectionPolicy,
93    certified: CertifiedF64,
94}
95
96impl CertifiedScalarProjection {
97    pub const fn policy(&self) -> ProjectionPolicy {
98        self.policy
99    }
100
101    pub fn certified(&self) -> &CertifiedF64 {
102        &self.certified
103    }
104
105    pub fn value(&self) -> f64 {
106        self.certified.value()
107    }
108
109    pub fn enclosure(&self) -> &DyadicEnclosure {
110        self.certified.enclosure()
111    }
112
113    pub fn absolute_error(&self) -> &Dyadic {
114        self.certified.absolute_error()
115    }
116
117    pub fn try_clone(&self) -> Result<Self, ScalarProjectionError> {
118        Ok(Self {
119            policy: self.policy,
120            certified: self
121                .certified
122                .try_clone()
123                .map_err(ScalarProjectionError::Bigint)?,
124        })
125    }
126}
127
128#[derive(Debug, Eq, PartialEq)]
129pub enum ScalarProjectionError {
130    FloatOutOfRange,
131    Bigint(BigintError),
132    Algnum(AlgnumError),
133    Storage(StorageError),
134}
135
136pub fn project_exact_value_f64(
137    value: &ExactValue,
138    policy: ProjectionPolicy,
139) -> Result<CertifiedScalarProjection, ScalarProjectionError> {
140    let comparable = ComparableExact::new(value).map_err(ScalarProjectionError::from_float)?;
141    let rounded = nearest_f64(&comparable).map_err(ScalarProjectionError::from_float)?;
142    let enclosure = enclose_exact_without_cache(value, policy.absolute_bits())
143        .map_err(ScalarProjectionError::from_float)?;
144    let exact_float = Dyadic::from_f64_exact(rounded).map_err(ScalarProjectionError::Bigint)?;
145    let absolute_error =
146        absolute_error(&exact_float, &enclosure).map_err(ScalarProjectionError::from_float)?;
147    Ok(CertifiedScalarProjection {
148        policy,
149        certified: CertifiedF64 {
150            value: rounded,
151            enclosure,
152            absolute_error,
153        },
154    })
155}
156
157impl ScalarProjectionError {
158    fn from_float(error: FloatError) -> Self {
159        match error {
160            FloatError::OutOfRange => Self::FloatOutOfRange,
161            FloatError::Bigint(error) => Self::Bigint(error),
162            FloatError::Algnum(error) => Self::Algnum(error),
163            FloatError::Storage(error) => Self::Storage(error),
164        }
165    }
166}
167
168impl core::fmt::Display for ScalarProjectionError {
169    fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
170        match self {
171            Self::FloatOutOfRange => formatter.write_str("exact value is outside finite f64 range"),
172            Self::Bigint(error) => error.fmt(formatter),
173            Self::Algnum(error) => error.fmt(formatter),
174            Self::Storage(error) => error.fmt(formatter),
175        }
176    }
177}
178
179#[cfg(feature = "std")]
180impl std::error::Error for ScalarProjectionError {}
181
182pub(crate) enum FloatError {
183    OutOfRange,
184    Bigint(BigintError),
185    Algnum(AlgnumError),
186    Storage(StorageError),
187}
188
189enum ComparableExact {
190    FormSum(FormSum),
191    Algebraic(IsolatingInterval),
192}
193
194impl ComparableExact {
195    fn new(value: &ExactValue) -> Result<Self, FloatError> {
196        match value {
197            ExactValue::Monomial(value) => FormSum::from_monomial(value)
198                .map(Self::FormSum)
199                .map_err(map_formsum_error),
200            ExactValue::FormSum(value) => value
201                .try_clone()
202                .map(Self::FormSum)
203                .map_err(map_formsum_error),
204            ExactValue::Algebraic(value) => value
205                .enclose(64)
206                .map(Self::Algebraic)
207                .map_err(FloatError::Algnum),
208        }
209    }
210
211    fn compare(&self, rhs: &Dyadic) -> Result<Ordering, FloatError> {
212        match self {
213            Self::FormSum(value) => {
214                let rhs = form_sum_from_dyadic(rhs)?;
215                value
216                    .sub(&rhs)
217                    .and_then(|difference| difference.sign())
218                    .map(|sign| match sign {
219                        Sign::Negative => Ordering::Less,
220                        Sign::Zero => Ordering::Equal,
221                        Sign::Positive => Ordering::Greater,
222                    })
223                    .map_err(map_formsum_error)
224            }
225            Self::Algebraic(interval) if interval.enclosure().upper() < rhs => Ok(Ordering::Less),
226            Self::Algebraic(interval) if interval.enclosure().lower() > rhs => {
227                Ok(Ordering::Greater)
228            }
229            Self::Algebraic(interval) => interval
230                .value()
231                .compare_dyadic(rhs)
232                .map_err(FloatError::Algnum),
233        }
234    }
235}
236
237fn form_sum_from_dyadic(value: &Dyadic) -> Result<FormSum, FloatError> {
238    let denominator = BigUint::one()
239        .and_then(|one| one.shl_bits(value.exponent() as usize))
240        .map_err(FloatError::Bigint)?;
241    let numerator = value.integer().try_clone().map_err(FloatError::Bigint)?;
242    RawFormSum::new(alloc::vec![RawTerm::new(
243        RawRational::new(numerator, denominator),
244        RawMonomial::positive(alloc::vec::Vec::new()),
245    )])
246    .normalize()
247    .map_err(|errors| map_formsum_error(errors.into_parts().0))
248}
249
250fn map_formsum_error(error: FormSumErrorKind) -> FloatError {
251    match error {
252        FormSumErrorKind::Bigint(error) => FloatError::Bigint(error),
253        error => FloatError::Algnum(AlgnumError::FormSum(error)),
254    }
255}
256
257fn nearest_f64(value: &ComparableExact) -> Result<f64, FloatError> {
258    let minimum = Dyadic::from_f64_exact(f64::from_bits(SIGN_MASK | MAX_FINITE_BITS))
259        .map_err(FloatError::Bigint)?;
260    let maximum =
261        Dyadic::from_f64_exact(f64::from_bits(MAX_FINITE_BITS)).map_err(FloatError::Bigint)?;
262    match value.compare(&minimum)? {
263        Ordering::Less => return Err(FloatError::OutOfRange),
264        Ordering::Equal => return Ok(f64::from_bits(SIGN_MASK | MAX_FINITE_BITS)),
265        Ordering::Greater => {}
266    }
267    match value.compare(&maximum)? {
268        Ordering::Greater => return Err(FloatError::OutOfRange),
269        Ordering::Equal => return Ok(f64::from_bits(MAX_FINITE_BITS)),
270        Ordering::Less => {}
271    }
272
273    let mut lower = 0_u64;
274    let mut upper = LAST_ORDERED;
275    while lower < upper {
276        let middle = lower + (upper - lower) / 2 + 1;
277        let candidate = exact_ordered(middle)?;
278        match value.compare(&candidate)? {
279            Ordering::Less => upper = middle - 1,
280            Ordering::Equal => return Ok(f64::from_bits(ordered_to_bits(middle))),
281            Ordering::Greater => lower = middle,
282        }
283    }
284
285    let lower_bits = ordered_to_bits(lower);
286    let upper_bits = ordered_to_bits(lower + 1);
287    let lower_value =
288        Dyadic::from_f64_exact(f64::from_bits(lower_bits)).map_err(FloatError::Bigint)?;
289    let upper_value =
290        Dyadic::from_f64_exact(f64::from_bits(upper_bits)).map_err(FloatError::Bigint)?;
291    let midpoint = lower_value
292        .midpoint(&upper_value)
293        .map_err(FloatError::Bigint)?;
294    let chosen = match value.compare(&midpoint)? {
295        Ordering::Less => lower_bits,
296        Ordering::Greater => upper_bits,
297        Ordering::Equal if lower_bits & 1 == 0 => lower_bits,
298        Ordering::Equal => upper_bits,
299    };
300    Ok(f64::from_bits(if chosen == SIGN_MASK { 0 } else { chosen }))
301}
302
303fn exact_ordered(ordered: u64) -> Result<Dyadic, FloatError> {
304    Dyadic::from_f64_exact(f64::from_bits(ordered_to_bits(ordered))).map_err(FloatError::Bigint)
305}
306
307fn ordered_to_bits(ordered: u64) -> u64 {
308    if ordered < NEGATIVE_COUNT {
309        !(NEGATIVE_KEY_START + ordered)
310    } else {
311        ordered - NEGATIVE_COUNT
312    }
313}
314
315fn enclose_exact(
316    value: &ExactValue,
317    expr: ExprId,
318    bits: AbsoluteBits,
319    isolation: &mut IsolationCache,
320) -> Result<DyadicEnclosure, FloatError> {
321    match value {
322        ExactValue::Algebraic(value) => {
323            if let Some(cached) = isolation.get(expr, bits) {
324                return cached.enclosure().try_clone().map_err(FloatError::Bigint);
325            }
326            let interval = enclose_algebraic(value, bits.get())?;
327            let enclosure = interval
328                .enclosure()
329                .try_clone()
330                .map_err(FloatError::Bigint)?;
331            isolation
332                .insert(expr, bits, interval)
333                .map_err(FloatError::Storage)?;
334            Ok(enclosure)
335        }
336        _ => enclose_exact_without_cache(value, bits),
337    }
338}
339
340fn enclose_exact_without_cache(
341    value: &ExactValue,
342    bits: AbsoluteBits,
343) -> Result<DyadicEnclosure, FloatError> {
344    match value {
345        ExactValue::Monomial(value) => {
346            let value = FormSum::from_monomial(value).map_err(map_formsum_error)?;
347            enclose_form_sum(&value, bits.get())
348        }
349        ExactValue::FormSum(value) => enclose_form_sum(value, bits.get()),
350        ExactValue::Algebraic(value) => enclose_algebraic(value, bits.get())?
351            .enclosure()
352            .try_clone()
353            .map_err(FloatError::Bigint),
354    }
355}
356
357fn enclose_form_sum(value: &FormSum, bits: u32) -> Result<DyadicEnclosure, FloatError> {
358    #[cfg(test)]
359    if enclosure_failure_is(EnclosureContact::FormSum) {
360        let required = BigUint::try_from(33_u8).map_err(FloatError::Bigint)?;
361        return Err(FloatError::Bigint(BigintError::ExponentOverflow {
362            required,
363            maximum: 32,
364        }));
365    }
366    value.enclose(bits).map_err(map_formsum_error)
367}
368
369fn enclose_algebraic(
370    value: &neco_algnum::RealAlgebraic,
371    bits: u32,
372) -> Result<IsolatingInterval, FloatError> {
373    #[cfg(test)]
374    ENCLOSURE_CALLS.with(|calls| calls.set(calls.get() + 1));
375    #[cfg(test)]
376    if enclosure_failure_is(EnclosureContact::Algebraic) {
377        let required = BigUint::try_from(41_u8).map_err(FloatError::Bigint)?;
378        let maximum = BigUint::try_from(40_u8).map_err(FloatError::Bigint)?;
379        return Err(FloatError::Algnum(AlgnumError::RepresentationLimit {
380            resource: RepresentationResource::RootDegree,
381            required,
382            maximum,
383        }));
384    }
385    value.enclose(bits).map_err(FloatError::Algnum)
386}
387
388#[cfg(test)]
389#[derive(Clone, Copy, Eq, PartialEq)]
390enum EnclosureContact {
391    FormSum,
392    Algebraic,
393}
394
395#[cfg(test)]
396std::thread_local! {
397    static ENCLOSURE_FAILURE: core::cell::Cell<Option<EnclosureContact>> = const { core::cell::Cell::new(None) };
398    static ENCLOSURE_CALLS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
399}
400
401#[cfg(test)]
402fn enclosure_failure_is(contact: EnclosureContact) -> bool {
403    ENCLOSURE_FAILURE.with(|configured| configured.get() == Some(contact))
404}
405
406#[cfg(test)]
407fn with_enclosure_failure<R>(contact: EnclosureContact, operation: impl FnOnce() -> R) -> R {
408    ENCLOSURE_FAILURE.with(|configured| configured.set(Some(contact)));
409    let result = operation();
410    ENCLOSURE_FAILURE.with(|configured| configured.set(None));
411    result
412}
413
414#[cfg(test)]
415fn with_enclosure_call_count<R>(operation: impl FnOnce() -> R) -> (R, usize) {
416    ENCLOSURE_CALLS.with(|calls| calls.set(0));
417    let result = operation();
418    let calls = ENCLOSURE_CALLS.with(core::cell::Cell::get);
419    (result, calls)
420}
421
422fn absolute_error(value: &Dyadic, enclosure: &DyadicEnclosure) -> Result<Dyadic, FloatError> {
423    let lower = abs_dyadic(&value.sub(enclosure.lower()).map_err(FloatError::Bigint)?)?;
424    let upper = abs_dyadic(&enclosure.upper().sub(value).map_err(FloatError::Bigint)?)?;
425    Ok(if lower >= upper { lower } else { upper })
426}
427
428fn abs_dyadic(value: &Dyadic) -> Result<Dyadic, FloatError> {
429    let magnitude: BigUint = value.integer().abs().map_err(FloatError::Bigint)?;
430    Ok(Dyadic::new(
431        BigInt::from_sign_magnitude(Sign::Positive, magnitude),
432        value.exponent(),
433    ))
434}
435
436#[cfg(test)]
437mod tests {
438    use neco_algnum::{AlgnumError, RealAlgebraic, RepresentationResource};
439    use neco_bigint::{BigInt, BigUint, BigintError};
440    use neco_formsum::FormSum;
441
442    use super::{
443        ordered_to_bits, with_enclosure_call_count, with_enclosure_failure, EnclosureContact,
444        LAST_ORDERED, NEGATIVE_COUNT,
445    };
446    use crate::{
447        project_exact_value_f64, AbsoluteBits, Assignments, AtomId, AtomStore, ConsumerId,
448        ExactValue, ExprGraph, ExprNode, PrecisionRequirements, ProjectionPolicy, ResolveError,
449        Resolver,
450    };
451
452    #[test]
453    fn ordered_bits_exclude_negative_zero() {
454        assert_eq!(ordered_to_bits(NEGATIVE_COUNT - 1), 0x8000_0000_0000_0001);
455        assert_eq!(ordered_to_bits(NEGATIVE_COUNT), 0);
456        assert_eq!(ordered_to_bits(NEGATIVE_COUNT + 1), 1);
457    }
458
459    #[test]
460    fn ordered_bits_cover_signed_normal_subnormal_zero_and_finite_endpoints() {
461        let negative_one_bits = (-1.0_f64).to_bits();
462        let negative_one_ordered = (!negative_one_bits) - super::NEGATIVE_KEY_START;
463        let positive_one_ordered = NEGATIVE_COUNT + 1.0_f64.to_bits();
464        let observations = [
465            ordered_to_bits(0),
466            ordered_to_bits(negative_one_ordered),
467            ordered_to_bits(NEGATIVE_COUNT - 1),
468            ordered_to_bits(NEGATIVE_COUNT),
469            ordered_to_bits(NEGATIVE_COUNT + 1),
470            ordered_to_bits(positive_one_ordered),
471            ordered_to_bits(LAST_ORDERED),
472        ];
473        assert_eq!(
474            observations,
475            [
476                (-f64::MAX).to_bits(),
477                (-1.0_f64).to_bits(),
478                0x8000_0000_0000_0001,
479                0,
480                1,
481                1.0_f64.to_bits(),
482                f64::MAX.to_bits(),
483            ]
484        );
485        assert!(observations.windows(2).all(|pair| {
486            f64::from_bits(pair[0]) < f64::from_bits(pair[1]) || (pair[0] == 0 && pair[1] == 1)
487        }));
488    }
489
490    fn resolve_with_injected_enclosure(
491        value: ExactValue,
492        contact: EnclosureContact,
493    ) -> ResolveError {
494        let mut graph = ExprGraph::new();
495        let expression = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
496        let mut atoms = AtomStore::new();
497        atoms.insert(AtomId::new(0), value).unwrap();
498        let mut requirements = PrecisionRequirements::new();
499        requirements
500            .insert(ConsumerId::new(0), AbsoluteBits::new(20))
501            .unwrap();
502        let mut assignments = Assignments::new();
503        assignments.insert(ConsumerId::new(0), expression).unwrap();
504        let (_, _, resolved) = with_enclosure_failure(contact, || {
505            Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
506        })
507        .unwrap();
508        match resolved.get(ConsumerId::new(0)).unwrap() {
509            Err(error) => match error {
510                ResolveError::Bigint(BigintError::ExponentOverflow { required, maximum }) => {
511                    ResolveError::Bigint(BigintError::ExponentOverflow {
512                        required: required.try_clone().unwrap(),
513                        maximum: *maximum,
514                    })
515                }
516                ResolveError::Algnum(AlgnumError::RepresentationLimit {
517                    resource,
518                    required,
519                    maximum,
520                }) => ResolveError::Algnum(AlgnumError::RepresentationLimit {
521                    resource: *resource,
522                    required: required.try_clone().unwrap(),
523                    maximum: maximum.try_clone().unwrap(),
524                }),
525                _ => panic!("unexpected enclosure error: {error:?}"),
526            },
527            Ok(_) => panic!("injected enclosure failure was not observed"),
528        }
529    }
530
531    #[test]
532    fn form_sum_enclosure_bigint_failure_keeps_the_payload() {
533        assert_eq!(
534            resolve_with_injected_enclosure(
535                ExactValue::FormSum(FormSum::one().unwrap()),
536                EnclosureContact::FormSum,
537            ),
538            ResolveError::Bigint(BigintError::ExponentOverflow {
539                required: BigUint::try_from(33_u8).unwrap(),
540                maximum: 32,
541            })
542        );
543    }
544
545    #[test]
546    fn algebraic_enclosure_failure_keeps_the_payload() {
547        let form = FormSum::one().unwrap();
548        assert_eq!(
549            resolve_with_injected_enclosure(
550                ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap()),
551                EnclosureContact::Algebraic,
552            ),
553            ResolveError::Algnum(AlgnumError::RepresentationLimit {
554                resource: RepresentationResource::RootDegree,
555                required: BigUint::try_from(41_u8).unwrap(),
556                maximum: BigUint::try_from(40_u8).unwrap(),
557            })
558        );
559    }
560
561    #[test]
562    fn algebraic_enclosure_is_computed_once_for_each_expression_and_precision() {
563        let form = FormSum::one().unwrap();
564        let mut graph = ExprGraph::new();
565        let expression = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
566        let mut atoms = AtomStore::new();
567        atoms
568            .insert(
569                AtomId::new(0),
570                ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap()),
571            )
572            .unwrap();
573        let mut requirements = PrecisionRequirements::new();
574        let mut assignments = Assignments::new();
575        for (consumer, bits) in [(0, 20), (1, 20), (2, 40)] {
576            requirements
577                .insert(ConsumerId::new(consumer), AbsoluteBits::new(bits))
578                .unwrap();
579            assignments
580                .insert(ConsumerId::new(consumer), expression)
581                .unwrap();
582        }
583        let (result, calls) = with_enclosure_call_count(|| {
584            Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
585        });
586        assert!(result.is_ok());
587        assert_eq!(calls, 2);
588    }
589
590    #[test]
591    fn scalar_projection_carries_its_policy_value_enclosure_and_error() {
592        let policy = ProjectionPolicy::new(AbsoluteBits::new(20));
593        let exact = ExactValue::FormSum(FormSum::one().unwrap());
594        let projection = project_exact_value_f64(&exact, policy).expect("scalar projection");
595        let selected = neco_bigint::Dyadic::from_f64_exact(projection.value()).unwrap();
596
597        assert_eq!(projection.policy(), policy);
598        assert_eq!(projection.value(), 1.0);
599        assert!(projection.enclosure().contains_dyadic(&selected));
600        let zero = BigInt::zero();
601        assert_eq!(projection.absolute_error().integer(), &zero);
602    }
603}