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}