v0.3 with const generics

EbTech · EbTech · commit 1d345542b51e · 2021-03-25T20:41:45.000-07:00
diff --git a/.travis.yml b/.travis.yml
@@ -1,6 +1,6 @@
 language: rust
 rust:
-  #- 1.51.0 # Version currently supported by Codeforces
+  - 1.51.0 # Version currently supported by Codeforces
   - stable
   - beta
   - nightly
diff --git a/Cargo.toml b/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "contest-algorithms"
-version = "0.2.1"
+version = "0.3.0"
 authors = ["Aram Ebtekar"]
 edition = "2018"
 
diff --git a/README.md b/README.md
@@ -43,7 +43,7 @@ For help in getting started, you may check out [some of my past submissions](htt
 
 My other goal is to appeal to developers who feel limited by ancient (yet still mainstream) programming languages, by demonstrating the power of modern techniques.
 
-Rather than try to persuade you with words, this repository aims to show by example. If you're new to Rust, see [Jim Blandy's *Why Rust?*](http://www.oreilly.com/programming/free/files/why-rust.pdf) for a brief introduction, or just [dive in!](https://doc.rust-lang.org/book/)
+Rather than try to persuade you with words, this repository aims to show by example. If you'd like to learn the language, I recommend [the official book](https://doc.rust-lang.org/book/) or [Programming Rust](https://www.amazon.com/Programming-Rust-Fast-Systems-Development-dp-1492052590/dp/1492052590).
 
 # Contents
 
diff --git a/src/math/fft.rs b/src/math/fft.rs
@@ -1,5 +1,5 @@
 //! The Fast Fourier Transform (FFT) and Number Theoretic Transform (NTT)
-use super::num::{Complex, Field, PI};
+use super::num::{CommonField, Complex, PI};
 use std::ops::{Add, Div, Mul, Neg, Sub};
 
 // We can delete this struct once f64::reverse_bits() stabilizes.
@@ -30,6 +30,7 @@ impl Iterator for BitRevIterator {
     }
 }
 
+#[allow(clippy::upper_case_acronyms)]
 pub trait FFT: Sized + Copy {
     type F: Sized
         + Copy
@@ -77,7 +78,7 @@ impl FFT for f64 {
 // 440564289 and 1713844692 are inverses and 2^27th roots of 1 mod (15<<27)+1
 //       125 and 2267742733 are inverses and 2^30th roots of 1 mod (3<<30)+1
 impl FFT for i64 {
-    type F = Field;
+    type F = CommonField;
 
     const ZERO: Self = 0;
 
@@ -197,9 +198,9 @@ mod test {
         let dft_v = dft_from_reals(&v, v.len());
         let new_v: Vec<i64> = idft_to_reals(&dft_v, v.len());
 
-        let seven = Field::from(7);
-        let one = Field::from(1);
-        let prim = Field::from(15_311_432).pow(1 << 21);
+        let seven = CommonField::from(7);
+        let one = CommonField::from(1);
+        let prim = CommonField::from(15_311_432).pow(1 << 21);
         let prim2 = prim * prim;
 
         let eval0 = seven + one + one;
@@ -230,6 +231,6 @@ mod test {
         let m = convolution(&vec![999], &vec![1_000_000]);
 
         assert_eq!(z, vec![14, 30, 6, 4]);
-        assert_eq!(m, vec![999_000_000 - Field::MOD]);
+        assert_eq!(m, vec![999_000_000 - super::super::num::COMMON_PRIME]);
     }
 }
diff --git a/src/math/num.rs b/src/math/num.rs
@@ -165,87 +165,88 @@ impl Div for Complex {
     }
 }
 
-//github.com/ Represents an element of the finite (Galois) field of prime order, given by
-//github.com/ MOD. Until Rust gets const generics, MOD must be hardcoded, but any prime in
-//github.com/ [1, 2^31.5] will work. If MOD is not prime, ring operations are still valid
+//github.com/ Represents an element of the finite (Galois) field of prime order M, where
+//github.com/ 1 <= M < 2^31.5. If M is not prime, ring operations are still valid
 //github.com/ but recip() and division are not. Note that the latter operations are also
 //github.com/ the slowest, so precompute any inverses that you intend to use frequently.
 #[derive(Clone, Copy, Eq, PartialEq, Debug, Hash)]
-pub struct Field {
+pub struct Modulo<const M: i64> {
     pub val: i64,
 }
-impl Field {
-    pub const MOD: i64 = 998_244_353; // 2^23 * 7 * 17 + 1
-
-    //github.com/ Computes self^exp in O(log(exp)) time
-    pub fn pow(mut self, mut exp: u64) -> Self {
+impl<const M: i64> Modulo<M> {
+    //github.com/ Computes self^n in O(log n) time
+    pub fn pow(mut self, mut n: u64) -> Self {
         let mut result = Self::from_small(1);
-        while exp > 0 {
-            if exp % 2 == 1 {
+        while n > 0 {
+            if n % 2 == 1 {
                 result = result * self;
             }
             self = self * self;
-            exp /= 2;
+            n /= 2;
         }
         result
     }
     //github.com/ Computes inverses of 1 to n in O(n) time
     pub fn vec_of_recips(n: i64) -> Vec<Self> {
         let mut recips = vec![Self::from(0), Self::from(1)];
         for i in 2..=n {
-            let (md, dv) = (Self::MOD % i, Self::MOD / i);
+            let (md, dv) = (M % i, M / i);
             recips.push(recips[md as usize] * Self::from_small(-dv));
         }
         recips
     }
-    //github.com/ Computes self^-1 in O(log(Self::MOD)) time
+    //github.com/ Computes self^-1 in O(log M) time
     pub fn recip(self) -> Self {
-        self.pow(Self::MOD as u64 - 2)
+        self.pow(M as u64 - 2)
     }
-    //github.com/ Avoids the % operation but requires -Self::MOD <= x < Self::MOD
+    //github.com/ Avoids the % operation but requires -M <= x < M
     fn from_small(s: i64) -> Self {
-        let val = if s < 0 { s + Self::MOD } else { s };
+        let val = if s < 0 { s + M } else { s };
         Self { val }
     }
 }
-impl From<i64> for Field {
+impl<const M: i64> From<i64> for Modulo<M> {
     fn from(val: i64) -> Self {
-        // Self { val: val.rem_euclid(Self::MOD) }
-        Self::from_small(val % Self::MOD)
+        // Self { val: val.rem_euclid(M) }
+        Self::from_small(val % M)
     }
 }
-impl Neg for Field {
+impl<const M: i64> Neg for Modulo<M> {
     type Output = Self;
     fn neg(self) -> Self {
         Self::from_small(-self.val)
     }
 }
-impl Add for Field {
+impl<const M: i64> Add for Modulo<M> {
     type Output = Self;
     fn add(self, other: Self) -> Self {
-        Self::from_small(self.val + other.val - Self::MOD)
+        Self::from_small(self.val + other.val - M)
     }
 }
-impl Sub for Field {
+impl<const M: i64> Sub for Modulo<M> {
     type Output = Self;
     fn sub(self, other: Self) -> Self {
         Self::from_small(self.val - other.val)
     }
 }
-impl Mul for Field {
+impl<const M: i64> Mul for Modulo<M> {
     type Output = Self;
     fn mul(self, other: Self) -> Self {
         Self::from(self.val * other.val)
     }
 }
 #[allow(clippy::suspicious_arithmetic_impl)]
-impl Div for Field {
+impl<const M: i64> Div for Modulo<M> {
     type Output = Self;
     fn div(self, other: Self) -> Self {
         self * other.recip()
     }
 }
 
+//github.com/ Prime modulus that's commonly used in programming competitions
+pub const COMMON_PRIME: i64 = 998_244_353; // 2^23 * 7 * 17 + 1;
+pub type CommonField = Modulo<COMMON_PRIME>;
+
 #[derive(Clone, PartialEq, Debug)]
 pub struct Matrix {
     cols: usize,
@@ -268,15 +269,15 @@ impl Matrix {
         let inner = vec.to_vec().into_boxed_slice();
         Self { cols, inner }
     }
-    pub fn pow(&self, mut exp: u64) -> Self {
+    pub fn pow(&self, mut n: u64) -> Self {
         let mut base = self.clone();
         let mut result = Self::one(self.cols);
-        while exp > 0 {
-            if exp % 2 == 1 {
+        while n > 0 {
+            if n % 2 == 1 {
                 result = &result * &base;
             }
             base = &base * &base;
-            exp /= 2;
+            n /= 2;
         }
         result
     }
@@ -417,10 +418,10 @@ mod test {
 
     #[test]
     fn test_field() {
-        let base = Field::from(1234);
+        let base = CommonField::from(1234);
         let zero = base - base;
         let one = base.recip() * base;
-        let two = Field::from(2 - 5 * Field::MOD);
+        let two = CommonField::from(2 - 5 * COMMON_PRIME);
 
         assert_eq!(zero.val, 0);
         assert_eq!(one.val, 1);
@@ -430,11 +431,11 @@ mod test {
 
     #[test]
     fn test_vec_of_recips() {
-        let recips = Field::vec_of_recips(20);
+        let recips = CommonField::vec_of_recips(20);
 
         assert_eq!(recips.len(), 21);
         for i in 1..recips.len() {
-            assert_eq!(recips[i], Field::from(i as i64).recip());
+            assert_eq!(recips[i], CommonField::from(i as i64).recip());
         }
     }
 
