feanor_math/ring.rs
1use std::ops::Deref;
2
3use serde::{Deserialize, Serialize};
4
5use crate::algorithms;
6use crate::homomorphism::*;
7use crate::integer::*;
8use crate::ordered::OrderedRingStore;
9use crate::primitive_int::StaticRing;
10
11/// Describes the context in which to print an algebraic expression.
12/// It is usually used to determine when to use parenthesis during printing.
13///
14/// # Example
15/// ```rust
16/// # use feanor_math::ring::*;
17/// # use feanor_math::rings::poly::*;
18/// # use feanor_math::primitive_int::*;
19/// # use feanor_math::rings::poly::dense_poly::*;
20/// struct CustomDisplay<'a>(
21/// &'a DensePolyRing<StaticRing<i64>>,
22/// &'a El<DensePolyRing<StaticRing<i64>>>,
23/// EnvBindingStrength,
24/// );
25/// impl<'a> std::fmt::Display for CustomDisplay<'a> {
26/// fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
27/// self.0.get_ring().dbg_within(self.1, formatter, self.2)
28/// }
29/// }
30/// let poly_ring = DensePolyRing::new(StaticRing::<i64>::RING, "X");
31/// let f = poly_ring.add(poly_ring.one(), poly_ring.indeterminate());
32/// assert_eq!(
33/// "X + 1",
34/// format!(
35/// "{}",
36/// CustomDisplay(&poly_ring, &f, EnvBindingStrength::Weakest)
37/// )
38/// );
39/// assert_eq!(
40/// "X + 1",
41/// format!("{}", CustomDisplay(&poly_ring, &f, EnvBindingStrength::Sum))
42/// );
43/// assert_eq!(
44/// "(X + 1)",
45/// format!(
46/// "{}",
47/// CustomDisplay(&poly_ring, &f, EnvBindingStrength::Product)
48/// )
49/// );
50/// assert_eq!(
51/// "(X + 1)",
52/// format!(
53/// "{}",
54/// CustomDisplay(&poly_ring, &f, EnvBindingStrength::Power)
55/// )
56/// );
57/// assert_eq!(
58/// "(X + 1)",
59/// format!(
60/// "{}",
61/// CustomDisplay(&poly_ring, &f, EnvBindingStrength::Strongest)
62/// )
63/// );
64/// ```
65#[derive(PartialEq, Eq, Debug, Clone, Copy, PartialOrd, Ord)]
66pub enum EnvBindingStrength {
67 /// The weakest possible binding strength, i.e. never add parenthesis.
68 Weakest,
69 /// Binding strength of addition (and subtraction), i.e. only add parenthesis
70 /// if the expression includes an operation that binds weaker than `+` (I cannot
71 /// think of any example, this seems to be a rare situation).
72 Sum,
73 /// Binding strength of multiplication (and division), i.e. only add parenthesis if
74 /// the expression includes an operation that binds weaker than `*` (Standard example
75 /// would be `+`).
76 Product,
77 /// Binding strength of powering, i.e. only add parenthesis if the expression
78 /// includes an operation that binds weaker than exponentiation (Standard examples would
79 /// be `+` or `*`).
80 Power,
81 /// The strongest possible binding strength, i.e. always add parenthesis.
82 Strongest,
83}
84
85/// Basic trait for objects that have a ring structure. This trait is
86/// implementor-facing, so designed to be used for implementing new
87/// rings.
88///
89/// Implementors of this trait should provide the basic ring operations,
90/// and additionally operators for displaying and equality testing. If
91/// a performance advantage can be achieved by accepting some arguments by
92/// reference instead of by value, the default-implemented functions for
93/// ring operations on references should be overwritten.
94///
95/// # Relationship with [`RingStore`]
96///
97/// Note that usually, this trait will not be used directly, but always
98/// through a [`RingStore`]. In more detail, while this trait
99/// defines the functionality, [`RingStore`] allows abstracting
100/// the storage - everything that allows access to a ring then is a
101/// [`RingStore`], as for example, references or shared pointers
102/// to rings. If you want to use rings directly by value, some technical
103/// details make it necessary to use the no-op container [`RingStore`].
104/// For more detail, see the documentation of [`RingStore`].
105///
106/// # A note on equality
107///
108/// Generally speaking, the notion of being canonically isomorphic
109/// (given by [`CanIsoFromTo`] is often more useful for rings than
110/// equality (defined by [`PartialEq`]).
111///
112/// In particular, being canonically isomorphic means that that there
113/// is a bidirectional mapping of elements `a in Ring1 <-> b in Ring2`
114/// such that `a` and `b` behave exactly the same. This mapping is provided
115/// by the functions of [`CanIsoFromTo`]. Note that every ring is supposed
116/// to be canonically isomorphic to itself, via the identiy mapping.
117///
118/// The notion of equality is stronger than that. In particular, implementors
119/// of [`PartialEq`] must ensure that if rings `R` and `S` are equal, then
120/// they are canonically isomorphic and the canonical isomorphism is given
121/// by bitwise identity map. In particular, elements of `R` and `S` must have
122/// the same type.
123///
124/// Hence, be careful to not mix up elements of different rings, even if they
125/// have the same type. This can easily lead to nasty errors. For example,
126/// consider the following code
127/// ```rust
128/// # use feanor_math::ring::*;
129/// # use feanor_math::homomorphism::*;
130/// # use feanor_math::primitive_int::*;
131/// # use feanor_math::rings::zn::*;
132/// let Z7 = zn_big::Zn::new(StaticRing::<i64>::RING, 7);
133/// let Z11 = zn_big::Zn::new(StaticRing::<i64>::RING, 11);
134/// assert!(Z11.get_ring() != Z7.get_ring());
135/// let neg_one = Z7.int_hom().map(-1);
136/// assert!(!Z11.is_neg_one(&neg_one));
137/// ```
138/// It is even allowed that both rings are isomorphic, and might be expected
139/// to be intuitively "the same", but still they are considered unequal, and
140/// swapping elements leads to incorrect results.
141///
142/// However, swapping elements between rings is well-defined and correct if they are "equal"
143/// as given by `PartialEq` (not just canonically isomorphic)
144/// ```rust
145/// # use feanor_math::ring::*;
146/// # use feanor_math::homomorphism::*;
147/// # use feanor_math::primitive_int::*;
148/// # use feanor_math::rings::zn::*;
149/// let Z11_fst = zn_big::Zn::new(StaticRing::<i64>::RING, 7);
150/// let Z11_snd = Z11_fst.clone();
151/// assert!(Z11_fst.get_ring() == Z11_snd.get_ring());
152/// let neg_one = Z11_fst.int_hom().map(-1);
153/// assert!(Z11_fst.is_neg_one(&neg_one));
154/// ```
155///
156/// # Example
157///
158/// An example implementation of a new, very useless ring type that represents
159/// 32-bit integers stored on the heap.
160/// ```rust
161/// # use feanor_math::ring::*;
162/// # use feanor_math::homomorphism::*;
163/// # use feanor_math::integer::*;
164///
165/// #[derive(PartialEq)]
166/// struct MyRingBase;
167///
168/// impl RingBase for MyRingBase {
169/// type Element = Box<i32>;
170///
171/// fn clone_el(&self, val: &Self::Element) -> Self::Element { val.clone() }
172///
173/// fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { **lhs += *rhs; }
174///
175/// fn negate_inplace(&self, lhs: &mut Self::Element) { **lhs = -**lhs; }
176///
177/// fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { **lhs *= *rhs; }
178///
179/// fn from_int(&self, value: i32) -> Self::Element { Box::new(value) }
180///
181/// fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { **lhs == **rhs }
182///
183/// fn is_commutative(&self) -> bool { true }
184/// fn is_noetherian(&self) -> bool { true }
185/// fn is_approximate(&self) -> bool { false }
186///
187/// fn dbg_within<'a>(
188/// &self,
189/// value: &Self::Element,
190/// out: &mut std::fmt::Formatter<'a>,
191/// _: EnvBindingStrength,
192/// ) -> std::fmt::Result {
193/// write!(out, "{}", **value)
194/// }
195///
196/// fn characteristic<I>(&self, ZZ: I) -> Option<El<I>>
197/// where
198/// I: RingStore + Copy,
199/// I::Type: IntegerRing,
200/// {
201/// Some(ZZ.zero())
202/// }
203/// }
204///
205/// // To use the ring through a RingStore, it is also required to implement CanHomFrom<Self>
206/// // and CanIsoFromTo<Self>.
207///
208/// impl CanHomFrom<MyRingBase> for MyRingBase {
209/// type Homomorphism = ();
210///
211/// fn has_canonical_hom(&self, _from: &MyRingBase) -> Option<()> { Some(()) }
212///
213/// fn map_in(&self, _from: &MyRingBase, el: Self::Element, _: &()) -> Self::Element { el }
214/// }
215///
216/// impl CanIsoFromTo<MyRingBase> for MyRingBase {
217/// type Isomorphism = ();
218///
219/// fn has_canonical_iso(&self, _from: &MyRingBase) -> Option<()> { Some(()) }
220///
221/// fn map_out(&self, _from: &MyRingBase, el: Self::Element, _: &()) -> Self::Element { el }
222/// }
223///
224/// // A type alias for the simple, by-value RingStore.
225/// pub type MyRing = RingValue<MyRingBase>;
226///
227/// impl MyRingBase {
228/// pub const RING: MyRing = RingValue::from(MyRingBase);
229/// }
230///
231/// let ring = MyRingBase::RING;
232/// assert!(ring.eq_el(
233/// &ring.int_hom().map(6),
234/// &ring.mul(ring.int_hom().map(3), ring.int_hom().map(2))
235/// ));
236/// ```
237///
238/// TODO: on next breaking release restrict with `: Debug`
239#[allow(missing_docs)]
240pub trait RingBase: PartialEq {
241 /// Type of elements of the ring
242 type Element: Sized;
243
244 fn clone_el(&self, val: &Self::Element) -> Self::Element;
245 fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { self.add_assign(lhs, self.clone_el(rhs)) }
246 fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element);
247 fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { self.sub_assign(lhs, self.clone_el(rhs)) }
248 fn negate_inplace(&self, lhs: &mut Self::Element);
249 fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element);
250 fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { self.mul_assign(lhs, self.clone_el(rhs)) }
251 fn zero(&self) -> Self::Element { self.from_int(0) }
252 fn one(&self) -> Self::Element { self.from_int(1) }
253 fn neg_one(&self) -> Self::Element { self.from_int(-1) }
254 fn from_int(&self, value: i32) -> Self::Element;
255 fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool;
256 fn is_zero(&self, value: &Self::Element) -> bool { self.eq_el(value, &self.zero()) }
257 fn is_one(&self, value: &Self::Element) -> bool { self.eq_el(value, &self.one()) }
258 fn is_neg_one(&self, value: &Self::Element) -> bool { self.eq_el(value, &self.neg_one()) }
259
260 /// Fused-multiply-add. This computes `summand + lhs * rhs`.
261 fn fma(&self, lhs: &Self::Element, rhs: &Self::Element, summand: Self::Element) -> Self::Element {
262 self.add(summand, self.mul_ref(lhs, rhs))
263 }
264
265 /// Returns whether the ring is commutative, i.e. `a * b = b * a` for all elements `a, b`.
266 /// Note that addition is assumed to be always commutative.
267 fn is_commutative(&self) -> bool;
268
269 /// Returns whether the ring is noetherian, i.e. every ideal is finitely generated.
270 ///
271 /// Rings for which this is not the case are a exceptional situation in computer
272 /// algebra, since they are usually "very large" and hard to work with. Examples for
273 /// non-noetherian rings could be the polynomial ring in infinitely many variables
274 /// `Z[X1, X2, X3, ...]` or the ring of algebraic integers.
275 fn is_noetherian(&self) -> bool;
276
277 /// Returns whether this ring computes with approximations to elements.
278 /// This would usually be the case for rings that are based on `f32` or
279 /// `f64`, to represent real or complex numbers.
280 ///
281 /// Note that these rings cannot provide implementations for [`RingBase::eq_el()`],
282 /// [`RingBase::is_zero()`] etc, and hence are of limited use in this crate.
283 /// Currently, the only way how approximate rings are used is a complex-valued
284 /// fast Fourier transform, via [`crate::rings::float_complex::Complex64`].
285 fn is_approximate(&self) -> bool;
286
287 /// Writes a human-readable representation of `value` to `out`.
288 ///
289 /// Used by [`RingStore::format()`], [`RingStore::println()`] and the implementations of
290 /// [`std::fmt::Debug`] and [`std::fmt::Display`] of [`crate::wrapper::RingElementWrapper`].
291 fn dbg<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
292 self.dbg_within(value, out, EnvBindingStrength::Weakest)
293 }
294
295 /// Writes a human-readable representation of `value` to `out`, taking into account the possible
296 /// context to place parenthesis as needed.
297 ///
298 /// See also [`RingBase::dbg()`] and [`EnvBindingStrength`].
299 ///
300 /// Used by [`RingStore::format()`], [`RingStore::println()`] and the implementations of
301 /// [`std::fmt::Debug`] and [`std::fmt::Display`] of [`crate::wrapper::RingElementWrapper`].
302 fn dbg_within<'a>(
303 &self,
304 value: &Self::Element,
305 out: &mut std::fmt::Formatter<'a>,
306 _env: EnvBindingStrength,
307 ) -> std::fmt::Result;
308
309 fn square(&self, value: &mut Self::Element) { self.mul_assign(value, self.clone_el(value)); }
310
311 fn negate(&self, mut value: Self::Element) -> Self::Element {
312 self.negate_inplace(&mut value);
313 return value;
314 }
315
316 fn sub_assign(&self, lhs: &mut Self::Element, mut rhs: Self::Element) {
317 self.negate_inplace(&mut rhs);
318 self.add_assign(lhs, rhs);
319 }
320
321 fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) { self.mul_assign(lhs, self.from_int(rhs)); }
322
323 fn mul_int(&self, mut lhs: Self::Element, rhs: i32) -> Self::Element {
324 self.mul_assign_int(&mut lhs, rhs);
325 return lhs;
326 }
327
328 fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element { self.mul_int(self.clone_el(lhs), rhs) }
329
330 /// Fused-multiply-add with an integer. This computes `summand + lhs * rhs`.
331 fn fma_int(&self, lhs: &Self::Element, rhs: i32, summand: Self::Element) -> Self::Element {
332 self.add(summand, self.mul_int_ref(lhs, rhs))
333 }
334
335 /// Computes `lhs := rhs - lhs`.
336 fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
337 self.negate_inplace(lhs);
338 self.add_assign(lhs, rhs);
339 }
340
341 /// Computes `lhs := rhs - lhs`.
342 fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
343 self.negate_inplace(lhs);
344 self.add_assign_ref(lhs, rhs);
345 }
346
347 fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
348 let mut result = self.clone_el(lhs);
349 self.add_assign_ref(&mut result, rhs);
350 return result;
351 }
352
353 fn add_ref_fst(&self, lhs: &Self::Element, mut rhs: Self::Element) -> Self::Element {
354 self.add_assign_ref(&mut rhs, lhs);
355 return rhs;
356 }
357
358 fn add_ref_snd(&self, mut lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
359 self.add_assign_ref(&mut lhs, rhs);
360 return lhs;
361 }
362
363 fn add(&self, mut lhs: Self::Element, rhs: Self::Element) -> Self::Element {
364 self.add_assign(&mut lhs, rhs);
365 return lhs;
366 }
367
368 fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
369 let mut result = self.clone_el(lhs);
370 self.sub_assign_ref(&mut result, rhs);
371 return result;
372 }
373
374 fn sub_ref_fst(&self, lhs: &Self::Element, mut rhs: Self::Element) -> Self::Element {
375 self.sub_assign_ref(&mut rhs, lhs);
376 self.negate_inplace(&mut rhs);
377 return rhs;
378 }
379
380 fn sub_ref_snd(&self, mut lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
381 self.sub_assign_ref(&mut lhs, rhs);
382 return lhs;
383 }
384
385 fn sub(&self, mut lhs: Self::Element, rhs: Self::Element) -> Self::Element {
386 self.sub_assign(&mut lhs, rhs);
387 return lhs;
388 }
389
390 fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
391 let mut result = self.clone_el(lhs);
392 self.mul_assign_ref(&mut result, rhs);
393 return result;
394 }
395
396 fn mul_ref_fst(&self, lhs: &Self::Element, mut rhs: Self::Element) -> Self::Element {
397 if self.is_commutative() {
398 self.mul_assign_ref(&mut rhs, lhs);
399 return rhs;
400 } else {
401 let mut result = self.clone_el(lhs);
402 self.mul_assign(&mut result, rhs);
403 return result;
404 }
405 }
406
407 fn mul_ref_snd(&self, mut lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
408 self.mul_assign_ref(&mut lhs, rhs);
409 return lhs;
410 }
411
412 fn mul(&self, mut lhs: Self::Element, rhs: Self::Element) -> Self::Element {
413 self.mul_assign(&mut lhs, rhs);
414 return lhs;
415 }
416
417 /// Raises `x` to the power of an arbitrary, nonnegative integer given by
418 /// a custom integer ring implementation.
419 ///
420 /// Unless overriden by implementors, this uses a square-and-multiply approach
421 /// to achieve running time O(log(power)).
422 ///
423 /// # Panic
424 ///
425 /// This may panic if `power` is negative.
426 fn pow_gen<R: RingStore>(&self, x: Self::Element, power: &El<R>, integers: R) -> Self::Element
427 where
428 R::Type: IntegerRing,
429 {
430 assert!(!integers.is_neg(power));
431 algorithms::sqr_mul::generic_pow_shortest_chain_table(
432 x,
433 power,
434 &integers,
435 |a| {
436 let mut a_copy = self.clone_el(a);
437 self.square(&mut a_copy);
438 Ok(a_copy)
439 },
440 |a, b| Ok(self.mul_ref(a, b)),
441 |a| self.clone_el(a),
442 self.one(),
443 )
444 .unwrap_or_else(|x| x)
445 }
446
447 /// Sums the elements given by the iterator.
448 ///
449 /// The implementation might be as simple as `els.fold(self.zero(), |a, b| self.add(a, b))`, but
450 /// can be more efficient than that in some cases.
451 fn sum<I>(&self, els: I) -> Self::Element
452 where
453 I: IntoIterator<Item = Self::Element>,
454 {
455 els.into_iter().fold(self.zero(), |a, b| self.add(a, b))
456 }
457
458 /// Computes the product of the elements given by the iterator.
459 ///
460 /// The implementation might be as simple as `els.fold(self.one(), |a, b| self.mul(a, b))`, but
461 /// can be more efficient than that in some cases.
462 fn prod<I>(&self, els: I) -> Self::Element
463 where
464 I: IntoIterator<Item = Self::Element>,
465 {
466 els.into_iter().fold(self.one(), |a, b| self.mul(a, b))
467 }
468
469 /// Returns the characteristic of this ring as an element of the given
470 /// implementation of `ZZ`.
471 ///
472 /// If `None` is returned, this means the given integer ring might not be able
473 /// to represent the characteristic. This must never happen if the given implementation
474 /// of `ZZ` allows for unbounded integers (like [`crate::integer::BigIntRing`]).
475 /// In other cases however, we allow to perform the size check heuristically only,
476 /// so this might return `None` even in some cases where the integer ring would in
477 /// fact be able to represent the characteristic.
478 ///
479 /// # Example
480 /// ```rust
481 /// # use feanor_math::ring::*;
482 /// # use feanor_math::primitive_int::*;
483 /// # use feanor_math::rings::zn::*;
484 /// let ZZ = StaticRing::<i16>::RING;
485 /// assert_eq!(Some(0), StaticRing::<i64>::RING.characteristic(&ZZ));
486 /// assert_eq!(
487 /// None,
488 /// zn_64::Zn::new(i16::MAX as u64 + 1).characteristic(&ZZ)
489 /// );
490 /// assert_eq!(
491 /// Some(i16::MAX),
492 /// zn_64::Zn::new(i16::MAX as u64).characteristic(&ZZ)
493 /// );
494 /// ```
495 fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
496 where
497 I::Type: IntegerRing;
498}
499
500/// Used to easily implement functions in the trait definition of
501/// [`RingStore`] and its subtraits to delegate the call to the same
502/// function of the underlying [`RingBase`].
503///
504/// # Example
505/// ```rust
506/// # use feanor_math::ring::*;
507/// # #[macro_use] use feanor_math::delegate;
508///
509/// trait WeirdRingBase: RingBase {
510/// fn foo(&self) -> Self::Element;
511/// }
512///
513/// trait WeirdRingStore: RingStore
514/// where
515/// Self::Type: WeirdRingBase,
516/// {
517/// delegate! { WeirdRingBase, fn foo(&self) -> El<Self> }
518/// }
519/// ```
520///
521/// # Limitations
522///
523/// This macro does not work if the function takes generic parameters.
524/// In this case, write the delegation manually.
525#[macro_export]
526macro_rules! delegate {
527 ($base_trait:ty, fn $name:ident (&self, $($pname:ident: $ptype:ty),*) -> $rtype:ty) => {
528 #[doc = concat!(" See [`", stringify!($base_trait), "::", stringify!($name), "()`]")]
529 fn $name (&self, $($pname: $ptype),*) -> $rtype {
530 <Self::Type as $base_trait>::$name(self.get_ring(), $($pname),*)
531 }
532 };
533 ($base_trait:ty, fn $name:ident (&self) -> $rtype:ty) => {
534 #[doc = concat!(" See [`", stringify!($base_trait), "::", stringify!($name), "()`]")]
535 fn $name (&self) -> $rtype {
536 <Self::Type as $base_trait>::$name(self.get_ring())
537 }
538 };
539}
540
541/// Variant of `assert_eq!` for ring elements, i.e. assert that two ring elements are equal.
542/// Frequently used in tests
543///
544/// # Example
545/// ```rust
546/// # use feanor_math::ring::*;
547/// # use feanor_math::primitive_int::*;
548/// # use feanor_math::assert_el_eq;
549///
550/// assert_el_eq!(StaticRing::<i32>::RING, 3, 3);
551/// // is equivalent to
552/// assert_eq!(3, 3);
553/// ```
554/// If the ring elements are not comparable on their own, this is really useful
555/// ```rust
556/// # use feanor_math::ring::*;
557/// # use feanor_math::homomorphism::*;
558/// # use feanor_math::integer::*;
559/// # use feanor_math::assert_el_eq;
560/// // this does not have an equivalent representation with assert_eq!
561/// assert_el_eq!(
562/// BigIntRing::RING,
563/// BigIntRing::RING.int_hom().map(3),
564/// BigIntRing::RING.int_hom().map(3)
565/// );
566/// ```
567#[macro_export]
568macro_rules! assert_el_eq {
569 ($ring:expr,$lhs:expr,$rhs:expr) => {
570 match (&$ring, &$lhs, &$rhs) {
571 (ring_val, lhs_val, rhs_val) => {
572 assert!(
573 <_ as $crate::ring::RingStore>::eq_el(ring_val, lhs_val, rhs_val),
574 "Assertion failed: {} != {}",
575 <_ as $crate::ring::RingStore>::format(ring_val, lhs_val),
576 <_ as $crate::ring::RingStore>::format(ring_val, rhs_val)
577 );
578 }
579 }
580 };
581}
582
583/// Basic trait for objects that store (in some sense) a ring. It can also
584/// be considered the user-facing trait for rings, so rings are always supposed
585/// to be used through a `RingStore`-object.
586///
587/// This can be a ring-by-value, a reference to a ring, or really any object that
588/// provides access to a [`RingBase`] object.
589///
590/// As opposed to [`RingBase`], which is responsible for the
591/// functionality and ring operations, this trait is solely responsible for
592/// the storage. The two basic implementors are [`RingValue`] and [`RingRef`],
593/// which just wrap a value resp. reference to a [`RingBase`] object.
594/// Building on that, every object that wraps a [`RingStore`] object can implement
595/// again [`RingStore`]. This applies in particular to implementors of
596/// `Deref<Target: RingStore>`, for whom there is a blanket implementation.
597///
598/// # Example
599///
600/// ```rust
601/// # use feanor_math::assert_el_eq;
602/// # use feanor_math::ring::*;
603/// # use feanor_math::primitive_int::*;
604/// # use std::rc::Rc;
605/// fn add_in_ring<R: RingStore>(ring: R, a: El<R>, b: El<R>) -> El<R> { ring.add(a, b) }
606///
607/// let ring: RingValue<StaticRingBase<i64>> = StaticRing::<i64>::RING;
608/// assert_el_eq!(ring, 7, add_in_ring(ring, 3, 4));
609/// assert_el_eq!(ring, 7, add_in_ring(&ring, 3, 4));
610/// assert_el_eq!(ring, 7, add_in_ring(Rc::new(ring), 3, 4));
611/// ```
612///
613/// # What does this do?
614///
615/// We need a framework that allows nesting rings, e.g. to provide a polynomial ring
616/// over a finite field - say `PolyRing<FiniteRing + Field>`. However, the simplest
617/// implementation
618/// ```rust,ignore
619/// struct PolyRing<BaseRing: Ring> { /* omitted */ }
620/// ```
621/// would have the effect that `PolyRing<FiniteRing + Field>` and `PolyRing<&FiniteRing + Field>`
622/// are entirely different types. While implementing relationships between them
623/// is possible, the approach does not scale well when we consider many rings and
624/// multiple layers of nesting.
625///
626/// # Note for implementors
627///
628/// Generally speaking it is not recommended to overwrite any of the default-implementations
629/// of ring functionality, as this is against the spirit of this trait. Instead,
630/// just provide an implementation of `get_ring()` and put ring functionality in
631/// a custom implementation of [`RingBase`].
632pub trait RingStore: Sized {
633 /// The type of the stored ring.
634 type Type: RingBase + ?Sized;
635
636 /// Returns a reference to the stored ring.
637 fn get_ring(&self) -> &Self::Type;
638
639 delegate! { RingBase, fn clone_el(&self, val: &El<Self>) -> El<Self> }
640 delegate! { RingBase, fn add_assign_ref(&self, lhs: &mut El<Self>, rhs: &El<Self>) -> () }
641 delegate! { RingBase, fn add_assign(&self, lhs: &mut El<Self>, rhs: El<Self>) -> () }
642 delegate! { RingBase, fn sub_assign_ref(&self, lhs: &mut El<Self>, rhs: &El<Self>) -> () }
643 delegate! { RingBase, fn sub_self_assign(&self, lhs: &mut El<Self>, rhs: El<Self>) -> () }
644 delegate! { RingBase, fn sub_self_assign_ref(&self, lhs: &mut El<Self>, rhs: &El<Self>) -> () }
645 delegate! { RingBase, fn negate_inplace(&self, lhs: &mut El<Self>) -> () }
646 delegate! { RingBase, fn mul_assign(&self, lhs: &mut El<Self>, rhs: El<Self>) -> () }
647 delegate! { RingBase, fn mul_assign_ref(&self, lhs: &mut El<Self>, rhs: &El<Self>) -> () }
648 delegate! { RingBase, fn zero(&self) -> El<Self> }
649 delegate! { RingBase, fn one(&self) -> El<Self> }
650 delegate! { RingBase, fn neg_one(&self) -> El<Self> }
651 delegate! { RingBase, fn eq_el(&self, lhs: &El<Self>, rhs: &El<Self>) -> bool }
652 delegate! { RingBase, fn is_zero(&self, value: &El<Self>) -> bool }
653 delegate! { RingBase, fn is_one(&self, value: &El<Self>) -> bool }
654 delegate! { RingBase, fn is_neg_one(&self, value: &El<Self>) -> bool }
655 delegate! { RingBase, fn is_commutative(&self) -> bool }
656 delegate! { RingBase, fn is_noetherian(&self) -> bool }
657 delegate! { RingBase, fn negate(&self, value: El<Self>) -> El<Self> }
658 delegate! { RingBase, fn sub_assign(&self, lhs: &mut El<Self>, rhs: El<Self>) -> () }
659 delegate! { RingBase, fn add_ref(&self, lhs: &El<Self>, rhs: &El<Self>) -> El<Self> }
660 delegate! { RingBase, fn add_ref_fst(&self, lhs: &El<Self>, rhs: El<Self>) -> El<Self> }
661 delegate! { RingBase, fn add_ref_snd(&self, lhs: El<Self>, rhs: &El<Self>) -> El<Self> }
662 delegate! { RingBase, fn add(&self, lhs: El<Self>, rhs: El<Self>) -> El<Self> }
663 delegate! { RingBase, fn sub_ref(&self, lhs: &El<Self>, rhs: &El<Self>) -> El<Self> }
664 delegate! { RingBase, fn sub_ref_fst(&self, lhs: &El<Self>, rhs: El<Self>) -> El<Self> }
665 delegate! { RingBase, fn sub_ref_snd(&self, lhs: El<Self>, rhs: &El<Self>) -> El<Self> }
666 delegate! { RingBase, fn sub(&self, lhs: El<Self>, rhs: El<Self>) -> El<Self> }
667 delegate! { RingBase, fn mul_ref(&self, lhs: &El<Self>, rhs: &El<Self>) -> El<Self> }
668 delegate! { RingBase, fn mul_ref_fst(&self, lhs: &El<Self>, rhs: El<Self>) -> El<Self> }
669 delegate! { RingBase, fn mul_ref_snd(&self, lhs: El<Self>, rhs: &El<Self>) -> El<Self> }
670 delegate! { RingBase, fn mul(&self, lhs: El<Self>, rhs: El<Self>) -> El<Self> }
671 delegate! { RingBase, fn square(&self, value: &mut El<Self>) -> () }
672 delegate! { RingBase, fn fma(&self, lhs: &El<Self>, rhs: &El<Self>, summand: El<Self>) -> El<Self> }
673
674 /// Tries to map the given element into this ring.
675 ///
676 /// This will internally construct a homomorphism between the rings, using
677 /// [`CanHomFrom`]. Note that if you want to map many elements between the
678 /// same rings, it may be faster to construct the homomorphism only once using
679 /// [`RingStore::can_hom()`].
680 fn coerce<S>(&self, from: &S, el: El<S>) -> El<Self>
681 where
682 S: RingStore,
683 Self::Type: CanHomFrom<S::Type>,
684 {
685 self.get_ring().map_in(
686 from.get_ring(),
687 el,
688 &self.get_ring().has_canonical_hom(from.get_ring()).unwrap(),
689 )
690 }
691
692 /// Returns the identity map `self -> self`.
693 fn into_identity(self) -> Identity<Self> { Identity::new(self) }
694
695 /// Returns the identity map `self -> self`.
696 fn identity(&self) -> Identity<&Self> { self.into_identity() }
697
698 /// Returns the canonical homomorphism `from -> self`, if it exists,
699 /// moving both rings into the [`CanHom`] object.
700 fn into_can_hom<S>(self, from: S) -> Result<CanHom<S, Self>, (S, Self)>
701 where
702 Self: Sized,
703 S: RingStore,
704 Self::Type: CanHomFrom<S::Type>,
705 {
706 CanHom::new(from, self)
707 }
708
709 /// Returns the canonical isomorphism `from -> self`, if it exists,
710 /// moving both rings into the [`CanHom`] object.
711 fn into_can_iso<S>(self, from: S) -> Result<CanIso<S, Self>, (S, Self)>
712 where
713 Self: Sized,
714 S: RingStore,
715 Self::Type: CanIsoFromTo<S::Type>,
716 {
717 CanIso::new(from, self)
718 }
719
720 /// Returns the canonical homomorphism `from -> self`, if it exists.
721 fn can_hom<'a, S>(&'a self, from: &'a S) -> Option<CanHom<&'a S, &'a Self>>
722 where
723 S: RingStore,
724 Self::Type: CanHomFrom<S::Type>,
725 {
726 self.into_can_hom(from).ok()
727 }
728
729 /// Returns the canonical isomorphism `from -> self`, if it exists.
730 fn can_iso<'a, S>(&'a self, from: &'a S) -> Option<CanIso<&'a S, &'a Self>>
731 where
732 S: RingStore,
733 Self::Type: CanIsoFromTo<S::Type>,
734 {
735 self.into_can_iso(from).ok()
736 }
737
738 /// Returns the homomorphism `Z -> self` that exists for any ring.
739 fn into_int_hom(self) -> IntHom<Self> { IntHom::new(self) }
740
741 /// Returns the homomorphism `Z -> self` that exists for any ring.
742 fn int_hom(&self) -> IntHom<&Self> { self.into_int_hom() }
743
744 /// Computes the sum of all elements returned by the iterator.
745 ///
746 /// This is equivalent to
747 /// ```rust
748 /// # use feanor_math::ring::*;
749 /// # use feanor_math::primitive_int::*;
750 /// # use feanor_math::assert_el_eq;
751 /// fn sum<R, I>(ring: R, els: I) -> El<R>
752 /// where R: RingStore,
753 /// I: IntoIterator<Item = El<R>>
754 /// {
755 /// els.into_iter().fold(ring.zero(), |a, b| ring.add(a, b))
756 /// }
757 /// # assert_el_eq!(StaticRing::<i64>::RING, StaticRing::<i64>::RING.sum([1, 2, 5]), sum(StaticRing::<i64>::RING, [1, 2, 5]))
758 /// ```
759 /// but may be faster.
760 fn sum<I>(&self, els: I) -> El<Self>
761 where
762 I: IntoIterator<Item = El<Self>>,
763 {
764 self.get_ring().sum(els)
765 }
766
767 /// Equivalent of [`RingStore::sum()`] if the producer of the ring elements
768 /// can fail, in which case summation is aborted and the error returned.
769 #[stability::unstable(feature = "enable")]
770 fn try_sum<I, E>(&self, els: I) -> Result<El<Self>, E>
771 where
772 I: IntoIterator<Item = Result<El<Self>, E>>,
773 {
774 let mut error = None;
775 let result = self.get_ring().sum(els.into_iter().map_while(|el| match el {
776 Ok(el) => Some(el),
777 Err(err) => {
778 error = Some(err);
779 None
780 }
781 }));
782 if let Some(err) = error {
783 return Err(err);
784 } else {
785 return Ok(result);
786 }
787 }
788
789 /// Computes the product of all elements returned by the iterator.
790 ///
791 /// This is equivalent to
792 /// ```rust
793 /// # use feanor_math::ring::*;
794 /// # use feanor_math::primitive_int::*;
795 /// # use feanor_math::assert_el_eq;
796 /// fn prod<R, I>(ring: R, els: I) -> El<R>
797 /// where R: RingStore,
798 /// I: IntoIterator<Item = El<R>>
799 /// {
800 /// els.into_iter().fold(ring.one(), |a, b| ring.mul(a, b))
801 /// }
802 /// # assert_el_eq!(StaticRing::<i64>::RING, StaticRing::<i64>::RING.prod([1, 2, 5]), prod(StaticRing::<i64>::RING, [1, 2, 5]))
803 /// ```
804 /// but may be faster.
805 fn prod<I>(&self, els: I) -> El<Self>
806 where
807 I: IntoIterator<Item = El<Self>>,
808 {
809 self.get_ring().prod(els)
810 }
811
812 /// Raises the given element to the given power.
813 fn pow(&self, mut x: El<Self>, power: usize) -> El<Self> {
814 // special cases to increase performance
815 if power == 0 {
816 return self.one();
817 } else if power == 1 {
818 return x;
819 } else if power == 2 {
820 self.square(&mut x);
821 return x;
822 }
823 self.pow_gen(x, &power.try_into().unwrap(), StaticRing::<i64>::RING)
824 }
825
826 /// Raises the given element to the given power, which should be a positive integer
827 /// belonging to an arbitrary [`IntegerRing`].
828 ///
829 /// This can in particular be used to compute exponentiation when the exponent does
830 /// not fit in a `usize`.
831 fn pow_gen<R: RingStore>(&self, x: El<Self>, power: &El<R>, integers: R) -> El<Self>
832 where
833 R::Type: IntegerRing,
834 {
835 self.get_ring().pow_gen(x, power, integers)
836 }
837
838 /// Returns an object that represents the given ring element and implements
839 /// [`std::fmt::Display`], to use as formatting parameter.
840 ///
841 /// # Example
842 /// ```rust
843 /// # use feanor_math::ring::*;
844 /// # use feanor_math::homomorphism::*;
845 /// # use feanor_math::integer::*;
846 /// let ring = BigIntRing::RING;
847 /// let element = ring.int_hom().map(3);
848 /// assert_eq!("3", format!("{}", ring.format(&element)));
849 /// ```
850 fn format<'a>(&'a self, value: &'a El<Self>) -> RingElementDisplayWrapper<'a, Self> {
851 self.format_within(value, EnvBindingStrength::Weakest)
852 }
853
854 /// Returns an object that represents the given ring element and implements
855 /// [`std::fmt::Display`], to use as formatting parameter. As opposed to
856 /// [`RingStore::format()`], this function takes an additional argument to
857 /// specify the context the result is printed in, which is used to determine
858 /// whether to put the value in parenthesis or not.
859 ///
860 /// # Example
861 /// ```rust
862 /// # use feanor_math::ring::*;
863 /// # use feanor_math::homomorphism::*;
864 /// # use feanor_math::integer::*;
865 /// # use feanor_math::rings::poly::dense_poly::*;
866 /// # use feanor_math::primitive_int::*;
867 /// # use feanor_math::rings::poly::*;
868 /// let ring = DensePolyRing::new(StaticRing::<i64>::RING, "X");
869 /// let [f, g] = ring.with_wrapped_indeterminate(|X| [X.clone(), X + 1]);
870 /// assert_eq!(
871 /// "X",
872 /// format!("{}", ring.format_within(&f, EnvBindingStrength::Sum))
873 /// );
874 /// assert_eq!(
875 /// "X",
876 /// format!("{}", ring.format_within(&f, EnvBindingStrength::Product))
877 /// );
878 /// assert_eq!(
879 /// "X + 1",
880 /// format!("{}", ring.format_within(&g, EnvBindingStrength::Sum))
881 /// );
882 /// assert_eq!(
883 /// "(X + 1)",
884 /// format!("{}", ring.format_within(&g, EnvBindingStrength::Product))
885 /// );
886 /// ```
887 fn format_within<'a>(
888 &'a self,
889 value: &'a El<Self>,
890 within: EnvBindingStrength,
891 ) -> RingElementDisplayWrapper<'a, Self> {
892 RingElementDisplayWrapper {
893 ring: self,
894 element: value,
895 within,
896 }
897 }
898
899 /// Prints the given element. Use for quick & dirty debugging.
900 fn println(&self, value: &El<Self>) {
901 println!("{}", self.format(value));
902 }
903
904 /// See [`RingBase::characteristic()`].
905 fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
906 where
907 I::Type: IntegerRing,
908 {
909 self.get_ring().characteristic(ZZ)
910 }
911}
912
913/// [`RingStore`] for [`RingExtension`]s
914pub trait RingExtensionStore: RingStore
915where
916 Self::Type: RingExtension,
917{
918 delegate! { RingExtension, fn base_ring(&self) -> &<Self::Type as RingExtension>::BaseRing }
919
920 /// Returns the inclusion map of the base ring `R -> self`.
921 fn into_inclusion(self) -> Inclusion<Self> { Inclusion::new(self) }
922
923 /// Returns the inclusion map of the base ring `R -> self`.
924 fn inclusion(&self) -> Inclusion<&Self> { self.into_inclusion() }
925}
926
927impl<R: RingStore> RingExtensionStore for R where R::Type: RingExtension {}
928
929/// Wrapper around a ring and one of its elements that implements [`std::fmt::Display`]
930/// and will print the element. Used by [`RingStore::format()`].
931pub struct RingElementDisplayWrapper<'a, R: RingStore + ?Sized> {
932 ring: &'a R,
933 element: &'a El<R>,
934 within: EnvBindingStrength,
935}
936
937impl<'a, R: RingStore + ?Sized> std::fmt::Display for RingElementDisplayWrapper<'a, R> {
938 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
939 self.ring.get_ring().dbg_within(self.element, f, self.within)
940 }
941}
942
943impl<'a, R: RingStore + ?Sized> std::fmt::Debug for RingElementDisplayWrapper<'a, R> {
944 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
945 self.ring.get_ring().dbg_within(self.element, f, self.within)
946 }
947}
948
949/// Trait for rings that are an extension ring of a base ring.
950/// This does not have to be a proper extension in the mathematical
951/// sense, but is in some cases implemented for a wrapper of a ring
952/// object that represents the same ring.
953///
954/// Hence, this is technically just a ring `R` with an injective homomorphism
955/// `BaseRing -> R`, but unlike [`CanHomFrom`], implementors must provide
956/// a reference to `BaseRing` via [`RingExtension::base_ring()`].
957///
958/// # Overlap with [`CanHomFrom`]
959///
960/// There is a certain amount of functionality overlap with [`CanHomFrom`], and
961/// in a perfect world, this trait would also be a subtrait of `CanHomFrom<<Self::BaseRing as
962/// RingStore>::Type>`. However, due to the issue with multiple blanket implementations for
963/// [`CanHomFrom`] (see the docs), this is not the case and in fact there are ring extensions that
964/// do not implement `CanHomFrom<<Self::BaseRing as RingStore>::Type>`.
965pub trait RingExtension: RingBase {
966 /// Type of the base ring;
967 ///
968 /// This is bounded by [`RingStore`] to encourage implementations of [`RingExtension`]
969 /// to store their base ring as a [`RingStore`] ([`RingStore`] is designed exactly for
970 /// this use case). Additionally, it makes using the base ring easier.
971 type BaseRing: RingStore;
972
973 /// Returns a reference to the base ring.
974 fn base_ring(&self) -> &Self::BaseRing;
975
976 /// Maps an element of the base ring into this ring.
977 ///
978 /// This should realize an injective ring homomorphism.
979 /// Instead of calling it directly, consider using it through
980 /// [`RingExtensionStore::inclusion()`].
981 fn from(&self, x: El<Self::BaseRing>) -> Self::Element;
982
983 /// Maps an element of the base ring (given as reference) into this ring.
984 fn from_ref(&self, x: &El<Self::BaseRing>) -> Self::Element { self.from(self.base_ring().get_ring().clone_el(x)) }
985
986 /// Computes `lhs := lhs * rhs`, where `rhs` is mapped into this
987 /// ring via [`RingExtension::from_ref()`]. Note that this may be
988 /// faster than `self.mul_assign(lhs, self.from_ref(rhs))`.
989 fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
990 self.mul_assign(lhs, self.from_ref(rhs));
991 }
992
993 fn fma_base(&self, lhs: &Self::Element, rhs: &El<Self::BaseRing>, summand: Self::Element) -> Self::Element {
994 let mut tmp = self.clone_el(lhs);
995 self.mul_assign_base(&mut tmp, rhs);
996 return self.add(summand, tmp);
997 }
998
999 /// Computes `lhs := lhs * rhs`, where `rhs` is mapped into this ring
1000 /// via the given homomorphism, followed by the inclusion (as specified by
1001 /// [`RingExtension::from_ref()`]).
1002 ///
1003 /// This is designed for the case that an extension ring element is represented
1004 /// as a vector of base ring elements, in which case this function can make
1005 /// use of an optimized [`Homomorphism::mul_assign_map()`] implementation.
1006 #[stability::unstable(feature = "enable")]
1007 fn mul_assign_base_through_hom<S: ?Sized + RingBase, H: Homomorphism<S, <Self::BaseRing as RingStore>::Type>>(
1008 &self,
1009 lhs: &mut Self::Element,
1010 rhs: &S::Element,
1011 hom: H,
1012 ) {
1013 self.mul_assign_base(lhs, &hom.map_ref(rhs));
1014 }
1015}
1016
1017/// Trait for rings that can compute hashes for their elements.
1018/// This should be compatible with [`RingBase::eq_el`] in the usual way.
1019pub trait HashableElRing: RingBase {
1020 /// Hashes the given ring element.
1021 fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H);
1022}
1023
1024/// [`RingStore`] for [`HashableElRing`]s
1025pub trait HashableElRingStore: RingStore
1026where
1027 Self::Type: HashableElRing,
1028{
1029 /// See [`HashableElRing::hash()`].
1030 fn hash<H: std::hash::Hasher>(&self, el: &El<Self>, h: &mut H) { self.get_ring().hash(el, h) }
1031
1032 /// Computes a hash of the given element using some default hasher.
1033 ///
1034 /// This may not be the same in different versions of `feanor-math`.
1035 fn default_hash(&self, el: &El<Self>) -> u64 {
1036 let mut hasher = std::collections::hash_map::DefaultHasher::new();
1037 self.hash(el, &mut hasher);
1038 return <std::collections::hash_map::DefaultHasher as std::hash::Hasher>::finish(&hasher);
1039 }
1040}
1041
1042impl<R> HashableElRingStore for R
1043where
1044 R: RingStore,
1045 R::Type: HashableElRing,
1046{
1047}
1048
1049/// Alias for `<<Self as RingStore>::Type as RingBase>::Element`.
1050pub type El<R> = <<R as RingStore>::Type as RingBase>::Element;
1051
1052/// The most fundamental [`crate::ring::RingStore`]. It is basically
1053/// a no-op container, i.e. stores a [`crate::ring::RingBase`] object
1054/// by value, and allows accessing it.
1055///
1056/// # Why is this necessary?
1057///
1058/// In fact, that we need this trait is just the result of a technical
1059/// detail. We cannot implement
1060/// ```rust,ignore
1061/// impl<R: RingBase> RingStore for R {}
1062/// impl<'a, R: RingStore> RingStore for &'a R {}
1063/// ```
1064/// since this might cause conflicting implementations.
1065/// Instead, we implement
1066/// ```rust,ignore
1067/// impl<R: RingBase> RingStore for RingValue<R> {}
1068/// impl<'a, R: RingStore> RingStore for &'a R {}
1069/// ```
1070/// This causes some inconvenience, as now we cannot chain
1071/// [`crate::ring::RingStore`] in the case of [`crate::ring::RingValue`].
1072/// Furthermore, this trait will be necessary everywhere -
1073/// to define a reference to a ring of type `A`, we now have to
1074/// write `&RingValue<A>`.
1075///
1076/// To simplify this, we propose to use the following simple pattern:
1077/// Create your ring type as
1078/// ```rust,ignore
1079/// struct ABase { ... }
1080/// impl RingBase for ABase { ... }
1081/// ```
1082/// and then provide a type alias
1083/// ```rust,ignore
1084/// type A = RingValue<ABase>;
1085/// ```
1086#[repr(transparent)]
1087#[derive(Copy, Clone, Debug, Serialize, Deserialize)]
1088pub struct RingValue<R: RingBase> {
1089 ring: R,
1090}
1091
1092impl<R: RingBase> RingValue<R> {
1093 /// Wraps the given [`RingBase`] in a [`RingValue`].
1094 ///
1095 /// This is a dedicated function instead of an implementation
1096 /// of [`std::convert::From`] so that we can declare it `const`.
1097 pub const fn from(value: R) -> Self { RingValue { ring: value } }
1098
1099 /// Creates a reference to a [`RingValue`] from a reference
1100 /// to the [`RingBase`].
1101 pub fn from_ref(value: &R) -> &Self { unsafe { std::mem::transmute(value) } }
1102
1103 /// Unwraps the [`RingBase`].
1104 ///
1105 /// The more common case would be to get a reference, which can
1106 /// be done with [`RingStore::get_ring()`].
1107 pub fn into(self) -> R { self.ring }
1108}
1109
1110impl<R: RingBase> RingStore for RingValue<R> {
1111 type Type = R;
1112
1113 fn get_ring(&self) -> &R { &self.ring }
1114}
1115
1116impl<R: RingBase + Default> Default for RingValue<R> {
1117 fn default() -> Self { Self::from(R::default()) }
1118}
1119
1120/// The second most basic [`crate::ring::RingStore`]. Similarly to
1121/// [`crate::ring::RingValue`] it is just a no-op container.
1122///
1123/// # Why do we need this in addition to [`crate::ring::RingValue`]?
1124///
1125/// Before [`RingValue::from_ref()`] was added, this was important to
1126/// allow using a reference to a [`RingBase`] as [`RingStore`]. Since then,
1127/// it indeed has only a marginal importance, but note that it is currently
1128/// the only way of working with unsized rings (an admittedly pretty exotic
1129/// case).
1130#[repr(transparent)]
1131#[derive(Debug)]
1132pub struct RingRef<'a, R: RingBase + ?Sized> {
1133 ring: &'a R,
1134}
1135
1136impl<'a, R: RingBase + ?Sized> Clone for RingRef<'a, R> {
1137 fn clone(&self) -> Self { *self }
1138}
1139
1140impl<'a, R: RingBase + ?Sized> Copy for RingRef<'a, R> {}
1141
1142impl<'a, R: RingBase + ?Sized> RingRef<'a, R> {
1143 /// Creates a new [`RingRef`] from a reference to a [`RingBase`].
1144 pub const fn new(value: &'a R) -> Self { RingRef { ring: value } }
1145
1146 /// Returns the stored reference to the [`RingBase`].
1147 ///
1148 /// This is almost the same as [`RingStore::get_ring()`], except for
1149 /// that the lifetime of the returned reference is not bounded to the
1150 /// lifetime of the [`RingRef`].
1151 pub fn into(self) -> &'a R { self.ring }
1152}
1153
1154impl<'a, R: RingBase + ?Sized> RingStore for RingRef<'a, R> {
1155 type Type = R;
1156
1157 fn get_ring(&self) -> &R { self.ring }
1158}
1159
1160impl<'a, S: Deref> RingStore for S
1161where
1162 S::Target: RingStore,
1163{
1164 type Type = <<S as Deref>::Target as RingStore>::Type;
1165
1166 fn get_ring(&self) -> &Self::Type { (**self).get_ring() }
1167}
1168
1169#[cfg(test)]
1170use std::rc::Rc;
1171
1172#[cfg(test)]
1173use crate::impl_eq_based_self_iso;
1174
1175#[test]
1176fn test_ring_rc_lifetimes() {
1177 let ring = Rc::new(StaticRing::<i32>::RING);
1178 let mut ring_ref = None;
1179 assert!(ring_ref.is_none());
1180 {
1181 ring_ref = Some(ring.get_ring());
1182 }
1183 assert!(ring.get_ring().is_commutative());
1184 assert!(ring_ref.is_some());
1185}
1186
1187#[test]
1188fn test_internal_wrappings_dont_matter() {
1189 #[derive(Clone, PartialEq)]
1190 pub struct ABase;
1191
1192 #[allow(unused)]
1193 #[derive(Clone)]
1194 pub struct BBase<R: RingStore> {
1195 base: R,
1196 }
1197
1198 impl<R: RingStore> PartialEq for BBase<R> {
1199 fn eq(&self, other: &Self) -> bool { self.base.get_ring() == other.base.get_ring() }
1200 }
1201
1202 impl RingBase for ABase {
1203 type Element = i32;
1204
1205 fn clone_el(&self, val: &Self::Element) -> Self::Element { *val }
1206
1207 fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs += rhs; }
1208
1209 fn negate_inplace(&self, lhs: &mut Self::Element) { *lhs = -*lhs; }
1210
1211 fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { *lhs == *rhs }
1212
1213 fn is_commutative(&self) -> bool { true }
1214
1215 fn is_noetherian(&self) -> bool { true }
1216
1217 fn from_int(&self, value: i32) -> Self::Element { value }
1218
1219 fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs *= rhs; }
1220
1221 fn dbg_within<'a>(
1222 &self,
1223 _: &Self::Element,
1224 _: &mut std::fmt::Formatter<'a>,
1225 _: EnvBindingStrength,
1226 ) -> std::fmt::Result {
1227 Ok(())
1228 }
1229
1230 fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
1231 where
1232 I::Type: IntegerRing,
1233 {
1234 Some(ZZ.zero())
1235 }
1236
1237 fn is_approximate(&self) -> bool { false }
1238 }
1239
1240 impl_eq_based_self_iso! { ABase }
1241
1242 impl<R: RingStore> RingBase for BBase<R> {
1243 type Element = i32;
1244
1245 fn clone_el(&self, val: &Self::Element) -> Self::Element { *val }
1246
1247 fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs += rhs; }
1248 fn negate_inplace(&self, lhs: &mut Self::Element) { *lhs = -*lhs; }
1249
1250 fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { *lhs == *rhs }
1251
1252 fn is_commutative(&self) -> bool { true }
1253
1254 fn is_noetherian(&self) -> bool { true }
1255
1256 fn from_int(&self, value: i32) -> Self::Element { value }
1257
1258 fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs *= rhs; }
1259
1260 fn dbg_within<'a>(
1261 &self,
1262 _: &Self::Element,
1263 _: &mut std::fmt::Formatter<'a>,
1264 _: EnvBindingStrength,
1265 ) -> std::fmt::Result {
1266 Ok(())
1267 }
1268
1269 fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
1270 where
1271 I::Type: IntegerRing,
1272 {
1273 Some(ZZ.zero())
1274 }
1275
1276 fn is_approximate(&self) -> bool { false }
1277 }
1278
1279 impl<R: RingStore> CanHomFrom<ABase> for BBase<R> {
1280 type Homomorphism = ();
1281
1282 fn has_canonical_hom(&self, _: &ABase) -> Option<()> { Some(()) }
1283
1284 fn map_in(&self, _: &ABase, el: <ABase as RingBase>::Element, _: &()) -> Self::Element { el }
1285 }
1286
1287 impl<R: RingStore, S: RingStore> CanHomFrom<BBase<S>> for BBase<R>
1288 where
1289 R::Type: CanHomFrom<S::Type>,
1290 {
1291 type Homomorphism = ();
1292
1293 fn has_canonical_hom(&self, _: &BBase<S>) -> Option<()> { Some(()) }
1294
1295 fn map_in(&self, _: &BBase<S>, el: <BBase<S> as RingBase>::Element, _: &()) -> Self::Element { el }
1296 }
1297
1298 impl<R: RingStore> CanIsoFromTo<BBase<R>> for BBase<R>
1299 where
1300 R::Type: CanHomFrom<R::Type>,
1301 {
1302 type Isomorphism = ();
1303
1304 fn has_canonical_iso(&self, _: &BBase<R>) -> Option<()> { Some(()) }
1305
1306 fn map_out(&self, _: &BBase<R>, el: <BBase<R> as RingBase>::Element, _: &()) -> Self::Element { el }
1307 }
1308
1309 type A = RingValue<ABase>;
1310 type B<R> = RingValue<BBase<R>>;
1311
1312 let a: A = RingValue { ring: ABase };
1313 let b1: B<A> = RingValue {
1314 ring: BBase { base: a.clone() },
1315 };
1316 let b2: B<&B<A>> = RingValue {
1317 ring: BBase { base: &b1 },
1318 };
1319 let b3: B<&A> = RingValue {
1320 ring: BBase { base: &a },
1321 };
1322 _ = b1.coerce(&a, 0);
1323 _ = b2.coerce(&a, 0);
1324 _ = b2.coerce(&b1, 0);
1325 _ = b2.coerce(&b3, 0);
1326 _ = (&b2).coerce(&b3, 0);
1327 _ = (&b2).coerce(&&&b3, 0);
1328}
1329
1330#[allow(missing_docs)]
1331#[cfg(any(test, feature = "generic_tests"))]
1332pub mod generic_tests {
1333
1334 use std::cmp::min;
1335
1336 use super::*;
1337 use crate::integer::{BigIntRing, int_cast};
1338
1339 pub fn test_hom_axioms<R: RingStore, S: RingStore, I: Iterator<Item = El<R>>>(from: R, to: S, edge_case_elements: I)
1340 where
1341 S::Type: CanHomFrom<R::Type>,
1342 {
1343 let hom = to.can_hom(&from).unwrap();
1344 crate::homomorphism::generic_tests::test_homomorphism_axioms(hom, edge_case_elements);
1345 }
1346
1347 pub fn test_iso_axioms<R: RingStore, S: RingStore, I: Iterator<Item = El<R>>>(from: R, to: S, edge_case_elements: I)
1348 where
1349 S::Type: CanIsoFromTo<R::Type>,
1350 {
1351 let hom = to.get_ring().has_canonical_hom(from.get_ring()).unwrap();
1352 let iso = to.get_ring().has_canonical_iso(from.get_ring()).unwrap();
1353 let elements = edge_case_elements.collect::<Vec<_>>();
1354
1355 for a in &elements {
1356 let map_in = to.get_ring().map_in_ref(from.get_ring(), a, &hom);
1357 let map_in_out = to.get_ring().map_out(from.get_ring(), to.clone_el(&map_in), &iso);
1358 assert!(
1359 from.eq_el(&map_in_out, &a),
1360 "Bijectivity failed: {} != {} = hom^-1({}) = hom^-1(hom({}))",
1361 from.format(a),
1362 from.format(&map_in_out),
1363 to.format(&map_in),
1364 from.format(a)
1365 );
1366 }
1367 }
1368
1369 pub fn test_self_iso<R: RingStore, I: Iterator<Item = El<R>>>(ring: R, edge_case_elements: I)
1370 where
1371 R::Type: SelfIso,
1372 {
1373 let hom = ring.get_ring().has_canonical_hom(ring.get_ring()).unwrap();
1374 let iso = ring.get_ring().has_canonical_iso(ring.get_ring()).unwrap();
1375 let elements = edge_case_elements.collect::<Vec<_>>();
1376
1377 test_hom_axioms(&ring, &ring, elements.iter().map(|x| ring.clone_el(x)));
1378 test_iso_axioms(&ring, &ring, elements.iter().map(|x| ring.clone_el(x)));
1379
1380 for a in &elements {
1381 assert_el_eq!(ring, a, ring.get_ring().map_in_ref(ring.get_ring(), a, &hom));
1382 assert_el_eq!(
1383 ring,
1384 a,
1385 ring.get_ring().map_out(ring.get_ring(), ring.clone_el(a), &iso)
1386 );
1387 }
1388 }
1389
1390 pub fn test_hash_axioms<R: RingStore, I: Iterator<Item = El<R>>>(ring: R, edge_case_elements: I)
1391 where
1392 R::Type: HashableElRing,
1393 {
1394 let elements = edge_case_elements.collect::<Vec<_>>();
1395
1396 // technically not required, but we should test hash inequality and this really should be
1397 // true
1398 assert_ne!(ring.default_hash(&ring.one()), ring.default_hash(&ring.zero()));
1399
1400 for a in &elements {
1401 for b in &elements {
1402 assert!(!ring.eq_el(a, b) || ring.default_hash(a) == ring.default_hash(b));
1403 }
1404 }
1405
1406 for a in &elements {
1407 for b in &elements {
1408 let expr = ring.sub(ring.mul_ref_fst(a, ring.add_ref_fst(b, ring.one())), ring.mul_ref(a, b));
1409 assert!(ring.default_hash(a) == ring.default_hash(&expr));
1410 }
1411 }
1412 }
1413
1414 pub fn test_ring_axioms<R: RingStore, I: Iterator<Item = El<R>>>(ring: R, edge_case_elements: I) {
1415 let elements = edge_case_elements.collect::<Vec<_>>();
1416 let zero = ring.zero();
1417 let one = ring.one();
1418
1419 assert!(ring.is_zero(&zero));
1420 assert!(ring.is_one(&one));
1421 assert!(ring.is_neg_one(&ring.neg_one()));
1422 assert!(ring.eq_el(&ring.neg_one(), &ring.get_ring().from_int(-1)));
1423 assert!(ring.eq_el(&zero, &ring.get_ring().from_int(0)));
1424 assert!(ring.eq_el(&one, &ring.get_ring().from_int(1)));
1425
1426 // check self-subtraction
1427 for a in &elements {
1428 let a_minus_a = ring.sub(ring.clone_el(a), ring.clone_el(a));
1429 assert!(
1430 ring.eq_el(&zero, &a_minus_a),
1431 "Additive inverse failed: {} - {} = {} != {}",
1432 ring.format_within(a, EnvBindingStrength::Sum),
1433 ring.format_within(a, EnvBindingStrength::Product),
1434 ring.format(&a_minus_a),
1435 ring.format(&zero)
1436 );
1437 }
1438
1439 // check identity elements
1440 for a in &elements {
1441 let a_plus_zero = ring.add(ring.clone_el(a), ring.clone_el(&zero));
1442 assert!(
1443 ring.eq_el(a, &a_plus_zero),
1444 "Additive neutral element failed: {} + {} = {} != {}",
1445 ring.format_within(a, EnvBindingStrength::Sum),
1446 ring.format(&zero),
1447 ring.format(&a_plus_zero),
1448 ring.format(a)
1449 );
1450
1451 let a_times_one = ring.mul(ring.clone_el(a), ring.clone_el(&one));
1452 assert!(
1453 ring.eq_el(a, &a_times_one),
1454 "Multiplicative neutral element failed: {} * {} = {} != {}",
1455 ring.format_within(a, EnvBindingStrength::Product),
1456 ring.format(&one),
1457 ring.format(&a_times_one),
1458 ring.format(a)
1459 );
1460 }
1461
1462 // check commutativity
1463 for a in &elements {
1464 for b in &elements {
1465 {
1466 let ab = ring.add_ref(a, b);
1467 let ba = ring.add_ref(b, a);
1468 assert!(
1469 ring.eq_el(&ab, &ba),
1470 "Additive commutativity failed: {} + {} = {} != {} = {} + {}",
1471 ring.format_within(a, EnvBindingStrength::Sum),
1472 ring.format_within(b, EnvBindingStrength::Sum),
1473 ring.format(&ab),
1474 ring.format(&ba),
1475 ring.format_within(b, EnvBindingStrength::Sum),
1476 ring.format_within(a, EnvBindingStrength::Sum)
1477 );
1478 }
1479
1480 if ring.is_commutative() {
1481 let ab = ring.mul_ref(a, b);
1482 let ba = ring.mul_ref(b, a);
1483 assert!(
1484 ring.eq_el(&ab, &ba),
1485 "Multiplicative commutativity failed: {} * {} = {} != {} = {} * {}",
1486 ring.format_within(a, EnvBindingStrength::Product),
1487 ring.format_within(b, EnvBindingStrength::Product),
1488 ring.format(&ab),
1489 ring.format(&ba),
1490 ring.format_within(b, EnvBindingStrength::Product),
1491 ring.format_within(a, EnvBindingStrength::Product)
1492 );
1493 }
1494 }
1495 }
1496
1497 // check associativity
1498 for a in &elements {
1499 for b in &elements {
1500 for c in &elements {
1501 {
1502 let ab_c = ring.add_ref_snd(ring.add_ref(a, b), c);
1503 let a_bc = ring.add_ref_fst(c, ring.add_ref(b, a));
1504 assert!(
1505 ring.eq_el(&ab_c, &a_bc),
1506 "Additive associativity failed: ({} + {}) + {} = {} != {} = {} + ({} + {})",
1507 ring.format_within(a, EnvBindingStrength::Sum),
1508 ring.format_within(b, EnvBindingStrength::Sum),
1509 ring.format_within(c, EnvBindingStrength::Sum),
1510 ring.format(&ab_c),
1511 ring.format(&a_bc),
1512 ring.format_within(a, EnvBindingStrength::Sum),
1513 ring.format_within(b, EnvBindingStrength::Sum),
1514 ring.format_within(c, EnvBindingStrength::Sum)
1515 );
1516 }
1517 {
1518 let ab_c = ring.mul_ref_snd(ring.mul_ref(a, b), c);
1519 let a_bc = ring.mul_ref_fst(c, ring.mul_ref(b, a));
1520 assert!(
1521 ring.eq_el(&ab_c, &a_bc),
1522 "Multiplicative associativity failed: ({} * {}) * {} = {} != {} = {} * ({} * {})",
1523 ring.format_within(a, EnvBindingStrength::Sum),
1524 ring.format_within(b, EnvBindingStrength::Sum),
1525 ring.format_within(c, EnvBindingStrength::Sum),
1526 ring.format(&ab_c),
1527 ring.format(&a_bc),
1528 ring.format_within(a, EnvBindingStrength::Sum),
1529 ring.format_within(b, EnvBindingStrength::Sum),
1530 ring.format_within(c, EnvBindingStrength::Sum)
1531 );
1532 }
1533 }
1534 }
1535 }
1536
1537 // check distributivity
1538 for a in &elements {
1539 for b in &elements {
1540 for c in &elements {
1541 let ab_c = ring.mul_ref_snd(ring.add_ref(a, b), c);
1542 let ac_bc = ring.add(ring.mul_ref(a, c), ring.mul_ref(b, c));
1543 assert!(
1544 ring.eq_el(&ab_c, &ac_bc),
1545 "Distributivity failed: ({} + {}) * {} = {} != {} = {} * {} + {} * {}",
1546 ring.format_within(a, EnvBindingStrength::Product),
1547 ring.format_within(b, EnvBindingStrength::Sum),
1548 ring.format_within(c, EnvBindingStrength::Sum),
1549 ring.format(&ab_c),
1550 ring.format(&ac_bc),
1551 ring.format_within(a, EnvBindingStrength::Product),
1552 ring.format_within(c, EnvBindingStrength::Product),
1553 ring.format_within(b, EnvBindingStrength::Product),
1554 ring.format_within(c, EnvBindingStrength::Product)
1555 );
1556
1557 let a_bc = ring.mul_ref_fst(a, ring.add_ref(b, c));
1558 let ab_ac = ring.add(ring.mul_ref(a, b), ring.mul_ref(a, c));
1559 assert!(
1560 ring.eq_el(&a_bc, &ab_ac),
1561 "Distributivity failed: {} * ({} + {}) = {} != {} = {} * {} + {} * {}",
1562 ring.format_within(a, EnvBindingStrength::Product),
1563 ring.format_within(b, EnvBindingStrength::Sum),
1564 ring.format_within(c, EnvBindingStrength::Sum),
1565 ring.format(&a_bc),
1566 ring.format(&ab_ac),
1567 ring.format_within(a, EnvBindingStrength::Product),
1568 ring.format_within(b, EnvBindingStrength::Product),
1569 ring.format_within(a, EnvBindingStrength::Product),
1570 ring.format_within(c, EnvBindingStrength::Product)
1571 );
1572 }
1573 }
1574 }
1575
1576 // check fma
1577 for a in &elements {
1578 for b in &elements {
1579 for c in &elements {
1580 let actual = ring.fma(a, b, ring.clone_el(c));
1581 let expected = ring.add(ring.mul_ref(a, b), ring.clone_el(c));
1582 assert!(
1583 ring.eq_el(&expected, &actual),
1584 "FMA failed: fma({}, {}, {}) = {} != {} = ({} * {}) + {}",
1585 ring.format(a),
1586 ring.format(b),
1587 ring.format(c),
1588 ring.format(&actual),
1589 ring.format(&expected),
1590 ring.format_within(a, EnvBindingStrength::Product),
1591 ring.format_within(b, EnvBindingStrength::Product),
1592 ring.format_within(c, EnvBindingStrength::Sum)
1593 );
1594 }
1595
1596 let actual = ring.get_ring().fma_int(a, 2, ring.clone_el(b));
1597 let expected = ring.get_ring().add(ring.get_ring().add_ref(a, a), ring.clone_el(b));
1598 assert!(
1599 ring.eq_el(&expected, &actual),
1600 "Int-FMA failed: int-fma({}, 2, {}) = {} != {} = ({} * 2) + {}",
1601 ring.format(a),
1602 ring.format(b),
1603 ring.format(&actual),
1604 ring.format(&expected),
1605 ring.format_within(a, EnvBindingStrength::Product),
1606 ring.format_within(b, EnvBindingStrength::Sum)
1607 );
1608 }
1609 }
1610
1611 // check powering
1612 for a in &elements {
1613 for n in [0, 1, 2, 3, 7, 8] {
1614 let expected = (0..n).map(|_| a).fold(ring.one(), |x, y| ring.mul_ref_snd(x, y));
1615 let actual = ring.pow(ring.clone_el(a), n);
1616 assert!(
1617 ring.eq_el(&expected, &actual),
1618 "Powering failed: {} * ... * {} = {} != {} = {}^{}",
1619 ring.format_within(a, EnvBindingStrength::Product),
1620 ring.format_within(a, EnvBindingStrength::Product),
1621 ring.format(&expected),
1622 ring.format(&actual),
1623 ring.format_within(a, EnvBindingStrength::Power),
1624 n
1625 );
1626 }
1627 }
1628
1629 // check characteristic
1630 let ZZbig = BigIntRing::RING;
1631 let char = ring.characteristic(&ZZbig).unwrap();
1632
1633 if ZZbig.is_geq(&char, &ZZbig.power_of_two(7)) {
1634 assert_eq!(None, ring.characteristic(&StaticRing::<i8>::RING));
1635 }
1636 if ZZbig.is_geq(&char, &ZZbig.power_of_two(15)) {
1637 assert_eq!(None, ring.characteristic(&StaticRing::<i16>::RING));
1638 }
1639 if ZZbig.is_geq(&char, &ZZbig.power_of_two(31)) {
1640 assert_eq!(None, ring.characteristic(&StaticRing::<i32>::RING));
1641 }
1642 if ZZbig.is_geq(&char, &ZZbig.power_of_two(63)) {
1643 assert_eq!(None, ring.characteristic(&StaticRing::<i64>::RING));
1644 }
1645 if ZZbig.is_geq(&char, &ZZbig.power_of_two(127)) {
1646 assert_eq!(None, ring.characteristic(&StaticRing::<i128>::RING));
1647 }
1648 if ZZbig.is_lt(&char, &ZZbig.power_of_two(31)) {
1649 let char = int_cast(char, &StaticRing::<i32>::RING, &ZZbig);
1650
1651 assert_el_eq!(ring, ring.zero(), ring.get_ring().from_int(char));
1652
1653 if char == 0 {
1654 for i in 1..(1 << 10) {
1655 assert!(!ring.is_zero(&ring.get_ring().from_int(i)));
1656 }
1657 } else {
1658 for i in 1..min(1 << 10, char) {
1659 assert!(!ring.is_zero(&ring.get_ring().from_int(i)));
1660 }
1661 }
1662 }
1663 }
1664}
1665
1666#[test]
1667fn test_environment_binding() {
1668 assert!(EnvBindingStrength::Strongest > EnvBindingStrength::Power);
1669 assert!(EnvBindingStrength::Power > EnvBindingStrength::Product);
1670 assert!(EnvBindingStrength::Product > EnvBindingStrength::Sum);
1671 assert!(EnvBindingStrength::Sum > EnvBindingStrength::Weakest);
1672}