competitive::algebra

Trait Field

Source 
pub trait Field: Ring
where
    Self::Additive: Invertible,
    Self::Multiplicative: Invertible,
{
    // Provided methods
    fn inv(x: &Self::T) -> Self::T { ... }
    fn div(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn div_assign(x: &mut Self::T, y: &Self::T) { ... }
}

Provided Methods§

Source

fn inv(x: &Self::T) -> Self::T

multiplicative inverse: $-$

Source

fn div(x: &Self::T, y: &Self::T) -> Self::T

multiplicative right inversed operaion: $-$

Examples found in repository?
crates/competitive/src/math/bitwisexor_convolve.rs (line 45)
41    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
42        BitwisexorConvolve::<R::Additive, false>::hadamard_transform(&mut f);
43        let len = R::T::from(len);
44        for f in f.iter_mut() {
45            *f = R::div(f, &len);
46        }
47        f
48    }
49
50    fn multiply(f: &mut Self::F, g: &Self::F) {
51        for (f, g) in f.iter_mut().zip(g) {
52            *f = R::mul(f, g);
53        }
54    }
55
56    fn convolve(a: Self::T, b: Self::T) -> Self::T {
57        assert_eq!(a.len(), b.len());
58        let len = a.len();
59        let same = a == b;
60        let mut a = Self::transform(a, len);
61        if same {
62            for a in a.iter_mut() {
63                *a = R::mul(a, a);
64            }
65        } else {
66            let b = Self::transform(b, len);
67            Self::multiply(&mut a, &b);
68        }
69        Self::inverse_transform(a, len)
70    }
71}
72
73impl<R> ConvolveSteps for BitwisexorConvolve<R, true>
74where
75    R: Field,
76    R::T: PartialEq,
77    R::Additive: Invertible,
78    R::Multiplicative: Invertible,
79    R::T: TryFrom<usize>,
80    <R::T as TryFrom<usize>>::Error: Debug,
81{
82    type T = Vec<R::T>;
83    type F = Vec<R::T>;
84
85    fn length(t: &Self::T) -> usize {
86        t.len()
87    }
88
89    fn transform(mut t: Self::T, _len: usize) -> Self::F {
90        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut t);
91        t
92    }
93
94    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
95        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut f);
96        let len = R::T::try_from(len).unwrap();
97        for f in f.iter_mut() {
98            *f = R::div(f, &len);
99        }
100        f
101    }
Source

fn div_assign(x: &mut Self::T, y: &Self::T)

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§