modint/
lib.rs

1extern crate typenum;
2extern crate num_traits;
3
4use typenum::Unsigned as CompileTimeUnsigned;
5use num_traits::ops::wrapping::{
6    WrappingAdd,
7    WrappingMul
8};
9use num_traits::{
10    Num, 
11    Zero, 
12    One, 
13    Unsigned as UnsignedNum
14};
15
16use std::marker::PhantomData;
17use std::ops::{
18    Add,
19    Sub,
20    Mul,
21    Div,
22    Rem,
23};
24
25pub trait FromCompileTimeUnsinged {
26    fn from<T: CompileTimeUnsigned>() -> Self;
27}
28
29impl FromCompileTimeUnsinged for u8 {
30    fn from<T: CompileTimeUnsigned>() -> Self {
31        T::to_u8()
32    }
33}
34
35impl FromCompileTimeUnsinged for u16 {
36    fn from<T: CompileTimeUnsigned>() -> Self {
37        T::to_u16()
38    }
39}
40
41impl FromCompileTimeUnsinged for u32 {
42    fn from<T: CompileTimeUnsigned>() -> Self {
43        T::to_u32()
44    }
45}
46
47impl FromCompileTimeUnsinged for u64 {
48    fn from<T: CompileTimeUnsigned>() -> Self {
49        T::to_u64()
50    }
51}
52
53impl FromCompileTimeUnsinged for usize {
54    fn from<T: CompileTimeUnsigned>() -> Self {
55        T::to_usize()
56    }
57}
58
59#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
60pub struct Unsigned<V, M> {
61    value: V,
62    phantom: PhantomData<M>
63}
64
65impl<V, M> Unsigned<V, M> {
66    pub fn value(self) -> V {
67        self.value
68    }
69}
70
71impl<V, M> From<V> for Unsigned<V, M>
72    where V: Rem<Output=V> + FromCompileTimeUnsinged,
73          M: CompileTimeUnsigned
74{
75    fn from(value: V) -> Self {
76        Unsigned {
77            value: value % V::from::<M>(),
78            phantom: Default::default()
79        }
80
81    }
82}
83
84impl<V, M> Add for Unsigned<V, M>
85    where V: WrappingAdd + Rem<Output=V> + FromCompileTimeUnsinged,
86          M: CompileTimeUnsigned
87{
88    type Output = Self;
89
90    fn add(self, rhs: Self) -> Self {
91        Unsigned {
92            value: self.value.wrapping_add(&rhs.value) % V::from::<M>(),
93            phantom: Default::default()
94        }
95    }
96}
97
98impl<V, M> Sub for Unsigned<V, M>
99    where V: Sub<Output=V> + Ord + Rem<Output=V> + FromCompileTimeUnsinged,
100          M: CompileTimeUnsigned
101{
102    type Output = Self;
103
104    fn sub(self, rhs: Self) -> Self {
105        let value = if self.value >= rhs.value {
106            self.value - rhs.value
107        } else {
108            V::from::<M>() - (rhs.value - self.value)
109        };
110
111        Unsigned {
112            value,
113            phantom: Default::default()
114        }
115    }
116}
117
118impl<V, M> Mul for Unsigned<V, M>
119    where V: WrappingMul + Rem<Output=V> + FromCompileTimeUnsinged,
120          M: CompileTimeUnsigned
121{
122    type Output = Self;
123
124    fn mul(self, rhs: Self) -> Self {
125        Unsigned {
126            value: self.value.wrapping_mul(&rhs.value) % V::from::<M>(),
127            phantom: Default::default()
128        }
129    }
130}
131
132impl<V, M> Div for Unsigned<V, M>
133    where V: Div<Output=V> + FromCompileTimeUnsinged,
134          M: CompileTimeUnsigned
135{
136    type Output = Self;
137
138    fn div(self, rhs: Self) -> Self {
139        Unsigned {
140            value: self.value / rhs.value,
141            phantom: Default::default()
142        }
143    }
144}
145
146impl<V, M> Rem for Unsigned<V, M>
147    where V: Rem<Output=V> + FromCompileTimeUnsinged,
148          M: CompileTimeUnsigned
149{
150    type Output = Self;
151
152    fn rem(self, rhs: Self) -> Self {
153        Unsigned {
154            value: self.value % rhs.value,
155            phantom: Default::default()
156        }
157    }
158}
159
160impl<V, M> Zero for Unsigned<V, M>
161    where V: Zero + WrappingAdd + Rem<Output=V> + FromCompileTimeUnsinged,
162          M: CompileTimeUnsigned
163{
164    fn zero() -> Self {
165        Unsigned {
166            value: V::zero(),
167            phantom: Default::default()
168        }
169    }
170
171    fn is_zero(&self) -> bool {
172        self.value.is_zero()
173    }
174}
175
176impl<V, M> One for Unsigned<V, M>
177    where V: One + WrappingMul + Rem<Output=V> + FromCompileTimeUnsinged,
178          M: CompileTimeUnsigned
179{
180    fn one() -> Self {
181        V::one().into()
182    }
183}
184
185impl<V, M> Num for Unsigned<V, M>
186    where V: Num + FromCompileTimeUnsinged + WrappingAdd + WrappingMul + PartialEq + Ord,
187          M: CompileTimeUnsigned + PartialEq
188{
189    type FromStrRadixErr = <V as Num>::FromStrRadixErr;
190
191    fn from_str_radix(s: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
192        Ok(V::from_str_radix(s, radix)?.into())
193    }
194}
195
196impl<V, M> UnsignedNum for Unsigned<V, M>
197    where V: Num + FromCompileTimeUnsinged + WrappingAdd + WrappingMul + PartialEq + Ord,
198          M: CompileTimeUnsigned + PartialEq
199{}
200
201#[cfg(test)]
202mod tests {
203    use typenum::U17;
204    use super::Unsigned;
205
206    type M17 = Unsigned<u8, U17>;
207
208    #[test]
209    fn construct() {
210        assert_eq!(M17::from(1 ).value(), 1);
211        assert_eq!(M17::from(4 ).value(), 4);
212        assert_eq!(M17::from(17).value(), 0);
213        assert_eq!(M17::from(18).value(), 1);
214    }
215
216    #[test]
217    fn add() {
218        assert_eq!(M17::from(1)  + 1 .into(), 2.into());
219        assert_eq!(M17::from(16) + 1 .into(), 0.into());
220        assert_eq!(M17::from(1)  + 17.into(), 1.into());
221        assert_eq!(M17::from(1)  + 35.into(), 2.into());
222    }
223
224    #[test]
225    fn sub() {
226        assert_eq!(M17::from(2)  - 1 .into(), 1 .into());
227        assert_eq!(M17::from(1)  - 3 .into(), 15.into());
228        assert_eq!(M17::from(15) - 16.into(), 16.into());
229        assert_eq!(M17::from(11) - 17.into(), 11.into());
230    }
231
232    #[test]
233    fn mul() {
234        assert_eq!(M17::from(2) * 2.into(), 4.into());
235        assert_eq!(M17::from(5) * 4.into(), 3.into());
236    }
237}
modint/lib.rs

modint/
lib.rs
