haar_lib/num/const_modint/
mod.rs

1//! コンパイル時にmod Mが決まるModInt
2
3pub mod algebra;
4
5use crate::impl_from;
6use crate::impl_one_zero;
7use crate::impl_ops;
8pub use crate::num::ff::*;
9use crate::num::one_zero::*;
10use std::{
11    fmt,
12    fmt::{Debug, Display, Formatter},
13};
14
15/// [`ConstModInt<M>`]を生成するための構造体。
16#[derive(Copy, Clone, Default, PartialEq, Eq)]
17pub struct ConstModIntBuilder<const M: u32>;
18
19impl<const M: u32> FF for ConstModIntBuilder<M> {
20    type Element = ConstModInt<M>;
21    fn from_u64(&self, a: u64) -> Self::Element {
22        Self::Element::new_unchecked(if a < M as u64 {
23            a as u32
24        } else {
25            (a % M as u64) as u32
26        })
27    }
28    fn from_i64(&self, value: i64) -> Self::Element {
29        let value = ((value % M as i64) + M as i64) as u32;
30        Self::Element::new(value)
31    }
32    fn modulo(&self) -> u32 {
33        M
34    }
35}
36
37/// `M`で剰余をとる構造体。
38#[derive(Copy, Clone, PartialEq, Default)]
39pub struct ConstModInt<const M: u32>(u32);
40
41impl<const M: u32> FFElem for ConstModInt<M> {
42    #[inline]
43    fn value(self) -> u32 {
44        self.0
45    }
46
47    #[inline]
48    fn modulo(self) -> u32 {
49        M
50    }
51
52    fn pow(self, mut p: u64) -> Self {
53        let mut ret: u64 = 1;
54        let mut a = self.0 as u64;
55
56        while p > 0 {
57            if (p & 1) != 0 {
58                ret *= a;
59                ret %= M as u64;
60            }
61
62            a *= a;
63            a %= M as u64;
64
65            p >>= 1;
66        }
67
68        Self::new_unchecked(ret as u32)
69    }
70}
71
72impl<const M: u32> ConstModInt<M> {
73    /// `ConstModInt<M>`を生成する。
74    pub fn new(n: u32) -> Self {
75        Self(if n < M { n } else { n % M })
76    }
77
78    #[inline]
79    fn new_unchecked(value: u32) -> Self {
80        Self(value)
81    }
82}
83
84impl<const M: u32> Display for ConstModInt<M> {
85    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
86        write!(f, "{}", self.0)
87    }
88}
89
90impl<const M: u32> Debug for ConstModInt<M> {
91    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
92        write!(f, "{} (mod {})", self.0, M)
93    }
94}
95
96impl_ops!([const M: u32]; Add for ConstModInt<M>, |x: Self, y: Self| {
97    let a = x.0 + y.0;
98    Self::new_unchecked(if a < M { a } else { a - M })
99});
100impl_ops!([const M: u32]; Sub for ConstModInt<M>, |x: Self, y: Self| {
101    let a = if x.0 < y.0 {
102        x.0 + M - y.0
103    } else {
104        x.0 - y.0
105    };
106    Self::new_unchecked(a)
107});
108impl_ops!([const M: u32]; Mul for ConstModInt<M>, |x: Self, y: Self| {
109    let a = x.0 as u64 * y.0 as u64;
110    Self::new_unchecked(if a < M as u64 {
111        a as u32
112    } else {
113        (a % M as u64) as u32
114    })
115});
116impl_ops!([const M: u32]; Div for ConstModInt<M>, |x: Self, y: Self| x * y.inv());
117
118impl_ops!([const M: u32]; AddAssign for ConstModInt<M>, |x: &mut Self, y| *x = *x + y);
119impl_ops!([const M: u32]; SubAssign for ConstModInt<M>, |x: &mut Self, y| *x = *x - y);
120impl_ops!([const M: u32]; MulAssign for ConstModInt<M>, |x: &mut Self, y| *x = *x * y);
121impl_ops!([const M: u32]; DivAssign for ConstModInt<M>, |x: &mut Self, y| *x = *x / y);
122
123impl_ops!([const M: u32]; Neg for ConstModInt<M>, |x: Self| Self::new_unchecked(if x.0 == 0 { 0 } else { M - x.0 }));
124
125impl_from!([const M: u32]; ConstModInt<M> => u32, |value: ConstModInt<M>| value.0);
126
127impl_from!([const M: u32]; usize => ConstModInt<M>, |value| ConstModIntBuilder.from_u64(value as u64));
128impl_from!([const M: u32]; u64 => ConstModInt<M>, |value| ConstModIntBuilder.from_u64(value));
129impl_from!([const M: u32]; u32 => ConstModInt<M>, |value| ConstModIntBuilder.from_u64(value as u64));
130
131impl_from!([const M: u32]; isize => ConstModInt<M>, |value| ConstModIntBuilder.from_i64(value as i64));
132impl_from!([const M: u32]; i64 => ConstModInt<M>, |value| ConstModIntBuilder.from_i64(value));
133impl_from!([const M: u32]; i32 => ConstModInt<M>, |value| ConstModIntBuilder.from_i64(value as i64));
134
135impl_one_zero!([const M: u32]; ConstModInt<M>; one: Self(1); zero: Self(0););
haar_lib/num/const_modint/mod.rs

haar_lib/num/const_modint/
mod.rs
