Trait RingBase 

pub trait RingBase: PartialEq {
    type Element: Sized;

    // Required methods
    fn clone_el(&self, val: &Self::Element) -> Self::Element;
    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element);
    fn negate_inplace(&self, lhs: &mut Self::Element);
    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element);
    fn from_int(&self, value: i32) -> Self::Element;
    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool;
    fn is_commutative(&self) -> bool;
    fn is_noetherian(&self) -> bool;
    fn is_approximate(&self) -> bool;
    fn dbg_within<'a>(
        &self,
        value: &Self::Element,
        out: &mut Formatter<'a>,
        _env: EnvBindingStrength,
    ) -> Result;
    fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
       where I::Type: IntegerRing;

    // Provided methods
    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { ... }
    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { ... }
    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { ... }
    fn zero(&self) -> Self::Element { ... }
    fn one(&self) -> Self::Element { ... }
    fn neg_one(&self) -> Self::Element { ... }
    fn is_zero(&self, value: &Self::Element) -> bool { ... }
    fn is_one(&self, value: &Self::Element) -> bool { ... }
    fn is_neg_one(&self, value: &Self::Element) -> bool { ... }
    fn fma(
        &self,
        lhs: &Self::Element,
        rhs: &Self::Element,
        summand: Self::Element,
    ) -> Self::Element { ... }
    fn dbg<'a>(&self, value: &Self::Element, out: &mut Formatter<'a>) -> Result { ... }
    fn square(&self, value: &mut Self::Element) { ... }
    fn negate(&self, value: Self::Element) -> Self::Element { ... }
    fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { ... }
    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) { ... }
    fn mul_int(&self, lhs: Self::Element, rhs: i32) -> Self::Element { ... }
    fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element { ... }
    fn fma_int(
        &self,
        lhs: &Self::Element,
        rhs: i32,
        summand: Self::Element,
    ) -> Self::Element { ... }
    fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { ... }
    fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { ... }
    fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element { ... }
    fn add_ref_fst(
        &self,
        lhs: &Self::Element,
        rhs: Self::Element,
    ) -> Self::Element { ... }
    fn add_ref_snd(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> Self::Element { ... }
    fn add(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { ... }
    fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element { ... }
    fn sub_ref_fst(
        &self,
        lhs: &Self::Element,
        rhs: Self::Element,
    ) -> Self::Element { ... }
    fn sub_ref_snd(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> Self::Element { ... }
    fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { ... }
    fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element { ... }
    fn mul_ref_fst(
        &self,
        lhs: &Self::Element,
        rhs: Self::Element,
    ) -> Self::Element { ... }
    fn mul_ref_snd(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> Self::Element { ... }
    fn mul(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { ... }
    fn pow_gen<R: RingStore>(
        &self,
        x: Self::Element,
        power: &El<R>,
        integers: R,
    ) -> Self::Element
       where R::Type: IntegerRing { ... }
    fn sum<I>(&self, els: I) -> Self::Element
       where I: IntoIterator<Item = Self::Element> { ... }
    fn prod<I>(&self, els: I) -> Self::Element
       where I: IntoIterator<Item = Self::Element> { ... }
}

Basic trait for objects that have a ring structure. This trait is implementor-facing, so designed to be used for implementing new rings.

Implementors of this trait should provide the basic ring operations, and additionally operators for displaying and equality testing. If a performance advantage can be achieved by accepting some arguments by reference instead of by value, the default-implemented functions for ring operations on references should be overwritten.

Relationship with RingStore

Note that usually, this trait will not be used directly, but always through a RingStore. In more detail, while this trait defines the functionality, RingStore allows abstracting the storage - everything that allows access to a ring then is a RingStore, as for example, references or shared pointers to rings. If you want to use rings directly by value, some technical details make it necessary to use the no-op container RingStore. For more detail, see the documentation of RingStore.

A note on equality

Generally speaking, the notion of being canonically isomorphic (given by CanIsoFromTo is often more useful for rings than equality (defined by PartialEq).

In particular, being canonically isomorphic means that that there is a bidirectional mapping of elements a in Ring1 <-> b in Ring2 such that a and b behave exactly the same. This mapping is provided by the functions of CanIsoFromTo. Note that every ring is supposed to be canonically isomorphic to itself, via the identiy mapping.

The notion of equality is stronger than that. In particular, implementors of PartialEq must ensure that if rings R and S are equal, then they are canonically isomorphic and the canonical isomorphism is given by bitwise identity map. In particular, elements of R and S must have the same type.

Hence, be careful to not mix up elements of different rings, even if they have the same type. This can easily lead to nasty errors. For example, consider the following code

let Z7 = zn_big::Zn::new(StaticRing::<i64>::RING, 7);
let Z11 = zn_big::Zn::new(StaticRing::<i64>::RING, 11);
assert!(Z11.get_ring() != Z7.get_ring());
let neg_one = Z7.int_hom().map(-1);
assert!(!Z11.is_neg_one(&neg_one));

It is even allowed that both rings are isomorphic, and might be expected to be intuitively “the same”, but still they are considered unequal, and swapping elements leads to incorrect results.

However, swapping elements between rings is well-defined and correct if they are “equal” as given by PartialEq (not just canonically isomorphic)

let Z11_fst = zn_big::Zn::new(StaticRing::<i64>::RING, 7);
let Z11_snd = Z11_fst.clone();
assert!(Z11_fst.get_ring() == Z11_snd.get_ring());
let neg_one = Z11_fst.int_hom().map(-1);
assert!(Z11_fst.is_neg_one(&neg_one));

Example

An example implementation of a new, very useless ring type that represents 32-bit integers stored on the heap.

 
#[derive(PartialEq)]
struct MyRingBase;
 
impl RingBase for MyRingBase {
     
    type Element = Box<i32>;
 
    fn clone_el(&self, val: &Self::Element) -> Self::Element { val.clone() }

    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { **lhs += *rhs; }
 
    fn negate_inplace(&self, lhs: &mut Self::Element) { **lhs = -**lhs; }
 
    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { **lhs *= *rhs; }
 
    fn from_int(&self, value: i32) -> Self::Element { Box::new(value) }
 
    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { **lhs == **rhs }
 
    fn is_commutative(&self) -> bool { true }
    fn is_noetherian(&self) -> bool { true }
    fn is_approximate(&self) -> bool { false }
 
    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, _: EnvBindingStrength) -> std::fmt::Result {
        write!(out, "{}", **value)
    }
 
    fn characteristic<I>(&self, ZZ: I) -> Option<El<I>>
        where I: RingStore + Copy, I::Type: IntegerRing
    {
        Some(ZZ.zero())
    }
}
 
// To use the ring through a RingStore, it is also required to implement CanHomFrom<Self>
// and CanIsoFromTo<Self>.
 
impl CanHomFrom<MyRingBase> for MyRingBase {
 
    type Homomorphism = ();
 
    fn has_canonical_hom(&self, _from: &MyRingBase) -> Option<()> { Some(()) }
 
    fn map_in(&self, _from: &MyRingBase, el: Self::Element, _: &()) -> Self::Element { el }
}
 
impl CanIsoFromTo<MyRingBase> for MyRingBase {
 
    type Isomorphism = ();
 
    fn has_canonical_iso(&self, _from: &MyRingBase) -> Option<()> { Some(()) }
 
    fn map_out(&self, _from: &MyRingBase, el: Self::Element, _: &()) -> Self::Element { el }
}
 
// A type alias for the simple, by-value RingStore.
pub type MyRing = RingValue<MyRingBase>;
 
impl MyRingBase {
 
    pub const RING: MyRing = RingValue::from(MyRingBase);
}
 
let ring = MyRingBase::RING;
assert!(ring.eq_el(
    &ring.int_hom().map(6), 
    &ring.mul(ring.int_hom().map(3), ring.int_hom().map(2))
));

TODO: on next breaking release restrict with : Debug

Required Associated Types

type Element: Sized

Type of elements of the ring

Required Methods

fn clone_el(&self, val: &Self::Element) -> Self::Element

fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn negate_inplace(&self, lhs: &mut Self::Element)

fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn from_int(&self, value: i32) -> Self::Element

fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

fn is_commutative(&self) -> bool

Returns whether the ring is commutative, i.e. a * b = b * a for all elements a, b. Note that addition is assumed to be always commutative.

fn is_noetherian(&self) -> bool

Returns whether the ring is noetherian, i.e. every ideal is finitely generated.

Rings for which this is not the case are a exceptional situation in computer algebra, since they are usually “very large” and hard to work with. Examples for non-noetherian rings could be the polynomial ring in infinitely many variables Z[X1, X2, X3, ...] or the ring of algebraic integers.

fn is_approximate(&self) -> bool

Returns whether this ring computes with approximations to elements. This would usually be the case for rings that are based on f32 or f64, to represent real or complex numbers.

Note that these rings cannot provide implementations for RingBase::eq_el(), RingBase::is_zero() etc, and hence are of limited use in this crate. Currently, the only way how approximate rings are used is a complex-valued fast Fourier transform, via crate::rings::float_complex::Complex64.

fn dbg_within<'a>( &self, value: &Self::Element, out: &mut Formatter<'a>, _env: EnvBindingStrength, ) -> Result

Writes a human-readable representation of value to out, taking into account the possible context to place parenthesis as needed.

See also RingBase::dbg() and EnvBindingStrength.

Used by RingStore::format(), RingStore::println() and the implementations of std::fmt::Debug and std::fmt::Display of crate::wrapper::RingElementWrapper.

fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>

where I::Type: IntegerRing,

Returns the characteristic of this ring as an element of the given implementation of ZZ.

If None is returned, this means the given integer ring might not be able to represent the characteristic. This must never happen if the given implementation of ZZ allows for unbounded integers (like crate::integer::BigIntRing). In other cases however, we allow to perform the size check heuristically only, so this might return None even in some cases where the integer ring would in fact be able to represent the characteristic.

Example

let ZZ = StaticRing::<i16>::RING;
assert_eq!(Some(0), StaticRing::<i64>::RING.characteristic(&ZZ));
assert_eq!(None, zn_64::Zn::new(i16::MAX as u64 + 1).characteristic(&ZZ));
assert_eq!(Some(i16::MAX), zn_64::Zn::new(i16::MAX as u64).characteristic(&ZZ));

Provided Methods

fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn zero(&self) -> Self::Element

fn one(&self) -> Self::Element

fn neg_one(&self) -> Self::Element

fn is_zero(&self, value: &Self::Element) -> bool

fn is_one(&self, value: &Self::Element) -> bool

fn is_neg_one(&self, value: &Self::Element) -> bool

fn fma( &self, lhs: &Self::Element, rhs: &Self::Element, summand: Self::Element, ) -> Self::Element

Fused-multiply-add. This computes summand + lhs * rhs.

fn dbg<'a>(&self, value: &Self::Element, out: &mut Formatter<'a>) -> Result

Writes a human-readable representation of value to out.

Used by RingStore::format(), RingStore::println() and the implementations of std::fmt::Debug and std::fmt::Display of crate::wrapper::RingElementWrapper.

fn square(&self, value: &mut Self::Element)

fn negate(&self, value: Self::Element) -> Self::Element

fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32)

fn mul_int(&self, lhs: Self::Element, rhs: i32) -> Self::Element

fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element

fn fma_int( &self, lhs: &Self::Element, rhs: i32, summand: Self::Element, ) -> Self::Element

Fused-multiply-add with an integer. This computes summand + lhs * rhs.

fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

Computes lhs := rhs - lhs.

fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

Computes lhs := rhs - lhs.

fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn add_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn add_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn add(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn sub_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn mul_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn mul(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn pow_gen<R: RingStore>( &self, x: Self::Element, power: &El<R>, integers: R, ) -> Self::Element

where R::Type: IntegerRing,

Raises x to the power of an arbitrary, nonnegative integer given by a custom integer ring implementation.

Unless overriden by implementors, this uses a square-and-multiply approach to achieve running time O(log(power)).

Panic

This may panic if power is negative.

fn sum<I>(&self, els: I) -> Self::Element

where I: IntoIterator<Item = Self::Element>,

Sums the elements given by the iterator.

The implementation might be as simple as els.fold(self.zero(), |a, b| self.add(a, b)), but can be more efficient than that in some cases.

fn prod<I>(&self, els: I) -> Self::Element

where I: IntoIterator<Item = Self::Element>,

Computes the product of the elements given by the iterator.

The implementation might be as simple as els.fold(self.one(), |a, b| self.mul(a, b)), but can be more efficient than that in some cases.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl RingBase for Real64Base

type Element = f64

impl RingBase for Complex64Base

type Element = Complex64El

impl RingBase for MPZBase

Available on crate feature mpir only.

type Element = MPZEl

impl RingBase for feanor_math::rings::zn::zn_64::ZnBase

type Element = ZnEl

impl<A: Allocator + Clone> RingBase for RustBigintRingBase<A>

type Element = RustBigint<A>

impl<C: RingStore, J: RingStore, A: Allocator + Clone> RingBase for feanor_math::rings::zn::zn_rns::ZnBase<C, J, A>

where C::Type: ZnRing + CanHomFrom<J::Type>, J::Type: IntegerRing, <C::Type as ZnRing>::IntegerRingBase: IntegerRing + CanIsoFromTo<J::Type>,

type Element = ZnEl<C, A>

impl<I> RingBase for RationalFieldBase<I>

where I: RingStore, I::Type: IntegerRing,

type Element = RationalFieldEl<I>

impl<I: RingStore> RingBase for feanor_math::rings::zn::zn_big::ZnBase<I>

where I::Type: IntegerRing,

type Element = ZnEl<I>

impl<R> RingBase for FractionFieldImplBase<R>

where R: RingStore, R::Type: Domain,

type Element = FractionFieldEl<R>

impl<R, A> RingBase for MultivariatePolyRingImplBase<R, A>

where R: RingStore, A: Clone + Allocator + Send,

type Element = MultivariatePolyRingEl<R, A>

impl<R, V, A, C> RingBase for FreeAlgebraImplBase<R, V, A, C>

where R: RingStore, V: VectorView<El<R>>, A: Allocator + Clone, C: ConvolutionAlgorithm<R::Type>,

type Element = FreeAlgebraImplEl<R, A>

impl<R: DelegateRing + PartialEq + ?Sized> RingBase for R

type Element = <R as DelegateRing>::Element

impl<R: RingStore> RingBase for SparsePolyRingBase<R>

type Element = SparsePolyRingEl<R>

impl<R: RingStore, A: Allocator + Clone, C: ConvolutionAlgorithm<R::Type>> RingBase for DensePolyRingBase<R, A, C>

type Element = DensePolyRingEl<R, A>

impl<R: RingStore, const N: usize> RingBase for DirectPowerRingBase<R, N>

type Element = [<<R as RingStore>::Type as RingBase>::Element; N]

impl<T: PrimitiveInt> RingBase for StaticRingBase<T>

type Element = T

impl<const N: u64, const IS_FIELD: bool> RingBase for feanor_math::rings::zn::zn_static::ZnBase<N, IS_FIELD>

type Element = u64