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}