Struct FastPrimeMod

Source

pub struct FastPrimeMod<const P: u32, const BUILD_INV: bool = true, const BUILD_POW: bool = true> {
    root: u32,
    pow_lo: Box<[u32]>,
    pow_hi: Box<[u32]>,
    frac: Box<[u32]>,
    log: Box<[u32]>,
    inv: Box<[u32]>,
}

Expand description

Fast online inverse and power queries for a prime modulus.

Fields§

§root: u32§pow_lo: Box<[u32]>§pow_hi: Box<[u32]>§frac: Box<[u32]>§log: Box<[u32]>§inv: Box<[u32]>

Implementations§

Source §

impl<const P: u32, const BUILD_INV: bool, const BUILD_POW: bool> FastPrimeMod<P, BUILD_INV, BUILD_POW>

Source

pub fn new() -> Self

Builds the tables enabled by the const generic mode.

§Panics

Panics if P is not an odd prime or if P >= 2^30.

Examples found in repository ?

crates/competitive/src/math/fast_prime_mod.rs (line 193)

192    fn default() -> Self {
193        Self::new()
194    }

Source

pub fn modulus(&self) -> u32

Returns the prime modulus.

Source

fn small_fraction(&self, x: u32) -> (usize, u32)

Examples found in repository ?

crates/competitive/src/math/fast_prime_mod.rs (line 127)

125    pub fn inverse(&self, x: u32) -> u32 {
126        assert!(1 <= x && x < P);
127        let (i, b) = self.small_fraction(x);
128        mul_mod_raw::<P>(self.inv[i], b)
129    }
130}
131
132impl<const P: u32, const BUILD_INV: bool> FastPrimeMod<P, BUILD_INV, true> {
133    /// Returns the primitive root used by this table.
134    #[inline]
135    pub fn primitive_root(&self) -> u32 {
136        self.root
137    }
138
139    /// Returns `a^exp mod P`.
140    ///
141    /// `0^0` is defined as `1`.
142    ///
143    /// # Panics
144    ///
145    /// Panics unless `a < P`.
146    #[inline]
147    pub fn pow(&self, a: u32, exp: u64) -> u32 {
148        assert!(a < P);
149        if a == 0 {
150            return if exp == 0 { 1 } else { 0 };
151        }
152        let ord = (P - 1) as u64;
153        self.pow_nonzero_reduced(a, (exp % ord) as u32)
154    }
155
156    /// Returns `a^exp_mod mod P` for a non-zero base and a reduced exponent.
157    ///
158    /// # Panics
159    ///
160    /// Panics unless `1 <= a < P` and `exp_mod < P - 1`.
161    #[inline]
162    pub fn pow_nonzero_reduced(&self, a: u32, exp_mod: u32) -> u32 {
163        assert!(1 <= a && a < P);
164        assert!(exp_mod < P - 1);
165        let exp = (self.log_r(a) as u64 * exp_mod as u64 % (P - 1) as u64) as u32;
166        self.pow_root_reduced(exp)
167    }
168
169    /// Returns `r^exp_mod mod P`, where `r` is this table's primitive root.
170    ///
171    /// # Panics
172    ///
173    /// Panics unless `exp_mod < P - 1`.
174    #[inline]
175    pub fn pow_root_reduced(&self, exp_mod: u32) -> u32 {
176        assert!(exp_mod < P - 1);
177        pow_root_raw::<P>(exp_mod, &self.pow_lo, &self.pow_hi)
178    }
179
180    #[inline]
181    fn log_r(&self, x: u32) -> u32 {
182        let (i, b) = self.small_fraction(x);
183        let k = table_k::<P>();
184        let ord = P - 1;
185        self.log[i] + ord - self.log[k + b as usize]
186    }

Source §

impl<const P: u32, const BUILD_POW: bool> FastPrimeMod<P, true, BUILD_POW>

Source

pub fn inverse(&self, x: u32) -> u32

Returns x^{-1} mod P.

§Panics

Panics unless 1 <= x < P.

Source §

impl<const P: u32, const BUILD_INV: bool> FastPrimeMod<P, BUILD_INV, true>

Source

pub fn primitive_root(&self) -> u32

Returns the primitive root used by this table.

Source

pub fn pow(&self, a: u32, exp: u64) -> u32

Returns a^exp mod P.

0^0 is defined as 1.

§Panics

Panics unless a < P.

Source

pub fn pow_nonzero_reduced(&self, a: u32, exp_mod: u32) -> u32

Returns a^exp_mod mod P for a non-zero base and a reduced exponent.

§Panics

Panics unless 1 <= a < P and exp_mod < P - 1.

Examples found in repository ?

crates/competitive/src/math/fast_prime_mod.rs (line 153)

147    pub fn pow(&self, a: u32, exp: u64) -> u32 {
148        assert!(a < P);
149        if a == 0 {
150            return if exp == 0 { 1 } else { 0 };
151        }
152        let ord = (P - 1) as u64;
153        self.pow_nonzero_reduced(a, (exp % ord) as u32)
154    }

Source

pub fn pow_root_reduced(&self, exp_mod: u32) -> u32

Returns r^exp_mod mod P, where r is this table’s primitive root.

§Panics

Panics unless exp_mod < P - 1.

Examples found in repository ?

crates/competitive/src/math/fast_prime_mod.rs (line 166)

162    pub fn pow_nonzero_reduced(&self, a: u32, exp_mod: u32) -> u32 {
163        assert!(1 <= a && a < P);
164        assert!(exp_mod < P - 1);
165        let exp = (self.log_r(a) as u64 * exp_mod as u64 % (P - 1) as u64) as u32;
166        self.pow_root_reduced(exp)
167    }

Source

fn log_r(&self, x: u32) -> u32

Examples found in repository ?

crates/competitive/src/math/fast_prime_mod.rs (line 165)

162    pub fn pow_nonzero_reduced(&self, a: u32, exp_mod: u32) -> u32 {
163        assert!(1 <= a && a < P);
164        assert!(exp_mod < P - 1);
165        let exp = (self.log_r(a) as u64 * exp_mod as u64 % (P - 1) as u64) as u32;
166        self.pow_root_reduced(exp)
167    }