yui_core/conc/num/
qint.rs

1//! Quadratic integers: the ring 𝒪 of algebraic integers of ℚ(√D) for a
2//! squarefree integer `D ≢ 0 (mod 4)`.
3//!
4//! 𝒪 is represented as `ℤ[ω]` where
5//!
6//! ```text
7//!   ω =  { (1 + √D)/2   if D ≡ 1    (mod 4)
8//!        { √D           if D ≡ 2, 3 (mod 4).
9//! ```
10//!
11//! A general `z ∈ ℤ[ω]` is stored as the pair `(a, b)` representing `a + b·ω`,
12//! i.e.
13//!
14//! ```text
15//!   z = a + bω = { (a + b/2) + (b/2)√D   if D ≡ 1
16//!                {        a  +    b √D   if D ≡ 2, 3.
17//! ```
18//!
19//! The cases `D = -1` and `D = -3` give the [Gaussian integers](GaussInt) `ℤ[i]`
20//! and the [Eisenstein integers](EisenInt) `ℤ[ω]`, respectively.
21//!
22//! See: <https://en.wikipedia.org/wiki/Quadratic_integer>,
23//! <https://en.wikipedia.org/wiki/Gaussian_integer>,
24//! <https://en.wikipedia.org/wiki/Eisenstein_integer>
25
26use std::str::FromStr;
27use std::fmt::{Display, Debug};
28use std::ops::{Add, Neg, Sub, Mul, AddAssign, SubAssign, MulAssign, Rem, Div, RemAssign, DivAssign};
29use num_traits::{Zero, One};
30use auto_impl_ops::auto_ops;
31use crate::abst::{AddGrp, AddGrpOps, AddMon, AddMonOps, MathType, EucRing, EucRingOps, Mon, MonOps, Ring, RingOps};
32use crate::ext::DivRound;
33use crate::util::parse_err::ParseErr;
34use super::int::{IntType, IntOps};
35
36/// A quadratic integer in `ℤ[ω]`, represented by `(a, b)` for `a + b·ω`.
37///
38/// See the module-level docs for the meaning of `ω` and the const `D`.
39#[derive(Clone, Default, PartialEq, Eq)]
40pub struct QuadInt<I, const D: i32>(I, I)
41where I: IntType, for<'x> &'x I: IntOps<I>;
42
43/// Gaussian integers: `ℤ[i] = QuadInt<I, -1>`.
44pub type GaussInt<I> = QuadInt<I, -1>;
45
46/// Eisenstein integers: `ℤ[ω]` with `ω = (1 + √-3)/2`, i.e. `QuadInt<I, -3>`.
47/// Note `-3 ≡ 1 (mod 4)`, so `ω` is the 6th root of unity, not the cube root `(-1 + √-3)/2`;
48/// the two generate the same ring.
49pub type EisenInt<I> = QuadInt<I, -3>;
50
51impl<I, const D: i32> QuadInt<I, D>
52where I: IntType, for<'x> &'x I: IntOps<I> {
53    pub fn new(a: I, b: I) -> Self {
54        assert!(D % 4 != 0);
55        Self(a, b)
56    }
57
58    pub fn omega() -> Self {
59        Self::new(I::zero(), I::one())
60    }
61
62    pub fn is_rational(&self) -> bool {
63        self.1.is_zero()
64    }
65
66    pub fn left(&self) -> &I {
67        &self.0
68    }
69
70    pub fn right(&self) -> &I {
71        &self.1
72    }
73
74    pub fn pair_into(self) -> (I, I) {
75        (self.0, self.1)
76    }
77
78    pub fn pair(&self) -> (&I, &I) {
79        (&self.0, &self.1)
80    }
81
82    // When D ≡ 1,
83    //
84    //   bar(z) = (a + b/2) - (b/2)√D
85    //          = (a + b) - b ω,
86    //
87    // when D ≡ 2, 3,
88    //
89    //   bar(z) = a - b √D
90    //          = a - b ω
91    //
92
93    pub fn conj(&self) -> Self {
94        let (a, b) = self.pair();
95        match D.rem_euclid(4) {
96            1     => QuadInt(a + b, -b),
97            2 | 3 => QuadInt(a.clone(), -b),
98            _     => panic!()
99        }
100    }
101
102    // When D ≡ 1,
103    //
104    //  N(z) = (a + b/2)^2 - (b/2)^2 D
105    //       = a^2 + ab + b^2 (1 - D)/4,
106    //
107    // when D ≡ 2, 3,
108    //
109    //  bar(z) = a^2 - b^2 D.
110    //
111
112    pub fn norm(&self) -> I {
113        let (a, b) = self.pair();
114        match D.rem_euclid(4) {
115            1 => {
116                let d = I::from_i32( (1 - D) / 4).unwrap();
117                a * a + a * b + b * b * d
118            },
119            2 | 3 => {
120                let d = I::from_i32(D).unwrap();
121                a * a - b * b * d
122            },
123            _     => panic!()
124        }
125    }
126}
127
128impl<I, const D: i32> From<I> for QuadInt<I, D>
129where I: IntType, for<'x> &'x I: IntOps<I> {
130    fn from(i: I) -> Self {
131        Self::new(i, I::zero())
132    }
133}
134
135impl<I, const D: i32> FromStr for QuadInt<I, D>
136where I: IntType + FromStr, for<'x> &'x I: IntOps<I> {
137    type Err = ParseErr;
138
139    fn from_str(s: &str) -> Result<Self, Self::Err> {
140        if let Ok(a) = s.parse::<I>() {
141            Ok(Self::from(a))
142        } else if let Ok((a, b)) = parse_tuple::<I, I>(s) {
143            Ok(Self::new(a, b))
144        } else {
145            Err(ParseErr::invalid(s, &Self::math_symbol()))
146        }
147    }
148}
149
150fn parse_tuple<I, J>(s: &str) -> Result<(I, J), ()>
151where I: FromStr, J: FromStr {
152    let r = regex::Regex::new(r"\((.+)?,\s*(.+)?\)").unwrap();
153    if let Some(c) = r.captures(s) {
154        let (s1, s2) = (&c[1], &c[2]);
155        if let (Ok(a), Ok(b)) = (s1.parse::<I>(), s2.parse::<J>()) {
156            return Ok((a, b))
157        }
158    }
159    Err(())
160}
161
162impl<I, const D: i32> Display for QuadInt<I, D>
163where I: IntType, for<'x> &'x I: IntOps<I> {
164    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
165        let (a, b) = self.pair();
166        let x = if D == -1 { "i" } else { "ω" };
167
168        if b.is_zero() {
169            write!(f, "{a}")
170        } else if a.is_zero() {
171            let b =
172                if b.is_one() { String::from("") }
173                else if (-b).is_one() { String::from("-") }
174                else { b.to_string() };
175            write!(f, "{b}{x}")
176        } else {
177            let sign = if !b.is_negative() { "+" } else { "-" };
178            let b =
179                if b.is_unit() { String::from("") }
180                else if b.is_negative() { (-b).to_string() }
181                else { b.to_string() };
182
183            write!(f, "{a} {sign} {b}{x}")
184        }
185    }
186}
187
188impl<I, const D: i32> Debug for QuadInt<I, D>
189where I: IntType, for<'x> &'x I: IntOps<I> {
190    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
191        Display::fmt(self, f)
192    }
193}
194
195impl<I, const D: i32> Zero for QuadInt<I, D>
196where I: IntType, for<'x> &'x I: IntOps<I> {
197    fn zero() -> Self {
198        Self::new(I::zero(), I::zero())
199    }
200
201    fn is_zero(&self) -> bool {
202        self.0.is_zero() && self.1.is_zero()
203    }
204}
205
206impl<I, const D: i32> One for QuadInt<I, D>
207where I: IntType, for<'x> &'x I: IntOps<I> {
208    fn one() -> Self {
209        Self::new(I::one(), I::zero())
210    }
211
212    fn is_one(&self) -> bool {
213        self.0.is_one() && self.1.is_zero()
214    }
215}
216
217impl_unop!(Neg, neg);
218impl_add_op!(Add, add);
219impl_add_op!(Sub, sub);
220
221#[auto_ops]
222impl<I, const D: i32> Mul<&QuadInt<I, D>> for &QuadInt<I, D>
223where I: IntType, for<'x> &'x I: IntOps<I> {
224    type Output = QuadInt<I, D>;
225
226    fn mul(self, rhs: &QuadInt<I, D>) -> Self::Output {
227        // When D ≡ 1,
228        //
229        //   ω^2 = (D + 1)/4 + √D/2
230        //       = (D - 1)/4 + ω,
231        //
232        // hence
233        //
234        //    (a + bω)(c + dω)
235        //  = (ac + bd(D - 1)/4) + (ad + bc + bd)ω.
236        //
237        // When D ≡ 2, 3,
238        //
239        //   ω^2 = D,
240        //
241        // hence
242        //
243        //    (a + bω)(c + dω)
244        //  = (ac + bdD) + (ad + bc)ω.
245
246        let (a, b) = self.pair();
247        let (c, d) = rhs.pair();
248
249        if b.is_zero() {
250            return QuadInt(a * c, a * d)
251        } else if d.is_zero() {
252            return QuadInt(a * c, b * c)
253        }
254
255        match D.rem_euclid(4) {
256            1 => {
257                let e = I::from_i32((D - 1) / 4).unwrap();
258                let x = a * c + b * d * e;
259                let y = a * d + b * c + b * d;
260                QuadInt(x, y)
261            },
262            2 | 3 => {
263                let e = I::from_i32(D).unwrap();
264                let x = a * c + b * d * e;
265                let y = a * d + b * c;
266                QuadInt(x, y)
267            },
268            _ => panic!()
269        }
270    }
271}
272
273// Div / Rem for GaussInt (D = -1).
274
275impl<I> DivRound for GaussInt<I>
276where I: IntType, for<'x> &'x I: IntOps<I> {
277    fn div_round(&self, rhs: &Self) -> Self {
278        let norm = rhs.norm();
279        let w = self * &rhs.conj();
280        let (x, y) = w.pair_into();
281        QuadInt(
282            x.div_round(&norm),
283            y.div_round(&norm)
284        )
285    }
286}
287
288#[auto_ops]
289impl<I> Div<&GaussInt<I>> for &GaussInt<I>
290where I: IntType, for<'x> &'x I: IntOps<I> {
291    type Output = GaussInt<I>;
292
293    fn div(self, rhs: &GaussInt<I>) -> Self::Output {
294        self.div_round(rhs)
295    }
296}
297
298#[auto_ops]
299impl<I> Rem<&GaussInt<I>> for &GaussInt<I>
300where I: IntType, for<'x> &'x I: IntOps<I> {
301    type Output = GaussInt<I>;
302
303    fn rem(self, rhs: &GaussInt<I>) -> Self::Output {
304        let q = self / rhs;
305        self - rhs * q
306    }
307}
308
309// Div / Rem for EisenInt (D = -3).
310
311impl<I> DivRound for EisenInt<I>
312where I: IntType, for<'x> &'x I: IntOps<I> {
313    //  z / w = (x + y ω) / N(w)
314    //        = (x + y) / N(w) + y / N(w) (ω - 1).
315    //
316    // (m, n) = ([(x + y) / N(w)], [y / N(w) ]).
317    //
318    // [z / w] = m + n(ω - 1) = (m - n) + nω.
319
320    fn div_round(&self, rhs: &Self) -> Self {
321        let norm = rhs.norm();
322        let w = self * &rhs.conj();
323        let (x, y) = w.pair();
324        let (m, n) = (
325            (x + y).div_round(&norm),
326            y.div_round(&norm)
327        );
328        QuadInt(&m - &n, n)
329    }
330}
331
332#[auto_ops]
333impl<I> Div<&EisenInt<I>> for &EisenInt<I>
334where I: IntType, for<'x> &'x I: IntOps<I> {
335    type Output = EisenInt<I>;
336
337    fn div(self, rhs: &EisenInt<I>) -> Self::Output {
338        self.div_round(rhs)
339    }
340}
341
342#[auto_ops]
343impl<I> Rem<&EisenInt<I>> for &EisenInt<I>
344where I: IntType, for<'x> &'x I: IntOps<I> {
345    type Output = EisenInt<I>;
346
347    fn rem(self, rhs: &EisenInt<I>) -> Self::Output {
348        let q = self / rhs;
349        self - rhs * q
350    }
351}
352
353impl_alg_op!(AddMonOps);
354impl_alg_op!(AddGrpOps);
355impl_alg_op!(MonOps);
356impl_alg_op!(RingOps);
357impl_alg_op_d!(EucRingOps, -1);
358impl_alg_op_d!(EucRingOps, -3);
359
360impl<I, const D: i32> MathType for QuadInt<I, D>
361where I: IntType, for<'x> &'x I: IntOps<I> {
362    fn math_symbol() -> String {
363        match D {
364            -1 => String::from("Z[i]"),
365            -3 => String::from("Z[ω]"),
366            // for D ≡ 1 (mod 4) the ring is ℤ[(1+√D)/2], strictly larger than ℤ[√D].
367            _ if D.rem_euclid(4) == 1 => format!("Z[(1 + √{D})/2]"),
368            _ => format!("Z[√{D}]"),
369        }
370    }
371}
372
373impl<I, const D: i32> AddMon for QuadInt<I, D>
374where I: IntType, for<'x> &'x I: IntOps<I> {}
375
376impl<I, const D: i32> AddGrp for QuadInt<I, D>
377where I: IntType, for<'x> &'x I: IntOps<I> {}
378
379impl<I, const D: i32> Mon for QuadInt<I, D>
380where I: IntType, for<'x> &'x I: IntOps<I> {}
381
382impl<I, const D: i32> Ring for QuadInt<I, D>
383where I: IntType, for<'x> &'x I: IntOps<I> {
384    // see: https://en.wikipedia.org/wiki/Quadratic_integer#Units
385    fn is_unit(&self) -> bool {
386        self.norm().is_unit()
387    }
388
389    fn inv(&self) -> Option<Self> {
390        if let Some(u) = self.norm().inv() {
391            let u = Self::from(u);
392            Some(u * self.conj())
393        } else {
394            None
395        }
396    }
397
398    fn normalizing_unit(&self) -> Self {
399        let (a, b) = self.pair();
400        match D {
401            -1 => {
402                if a.is_positive() && !b.is_negative() {         // a > 0, b ≧ 0 -> 1
403                    Self::one()
404                } else if !a.is_positive() && b.is_positive() {  // a ≦ 0, b > 0 -> -i
405                    -Self::omega()
406                } else if a.is_negative() && !b.is_positive() {  // a < 0, b ≦ 0 -> -1
407                    -Self::one()
408                } else if !a.is_negative() && b.is_negative() {  // a ≧ 0, b < 0 -> i
409                    Self::omega()
410                } else {                                         // a = b = 0    -> 1
411                    Self::one()
412                }
413            },
414            -3 => {
415                let c = a + b;
416                if a.is_positive() && !b.is_negative() {         // a > 0, b ≧ 0     -> 1
417                    Self::one()
418                } else if !a.is_positive() && c.is_positive() {  // a ≦ 0, a + b > 0 -> 1/ω   = 1 - ω
419                    Self::new(I::one(), -I::one())
420                } else if !c.is_positive() && b.is_positive() {  // a + b ≦ 0, b > 0 -> 1/ω^2 = -ω
421                    -Self::omega()
422                } else if a.is_negative() && !b.is_positive() {  // a < 0, b ≦ 0     -> 1/ω^3 = -1
423                    -Self::one()
424                } else if !a.is_negative() && c.is_negative() {  // a ≧ 0, a + b < 0 -> 1/ω^4 = ω - 1
425                    Self::new(-I::one(), I::one())
426                } else if !c.is_negative() && b.is_negative() {  // a + b ≧ 0, b < 0 -> 1/ω^5 = ω
427                    Self::omega()
428                } else {
429                    Self::one()
430                }
431            },
432            _ => {
433                if a.is_negative() {
434                    -Self::one()
435                } else {
436                    Self::one()
437                }
438            }
439        }
440    }
441}
442
443impl<I> EucRing for QuadInt<I, -1>
444where I: IntType, for<'x> &'x I: IntOps<I> {}
445
446impl<I> EucRing for QuadInt<I, -3>
447where I: IntType, for<'x> &'x I: IntOps<I> {}
448
449// -- macros -- //
450
451macro_rules! impl_unop {
452    ($trait:ident, $method:ident) => {
453        impl<I, const D: i32> $trait for QuadInt<I, D>
454        where I: IntType, for<'x> &'x I: IntOps<I> {
455            type Output = Self;
456
457            fn $method(self) -> Self::Output {
458                let (a, b) = self.pair_into();
459                Self(I::$method(a), I::$method(b))
460            }
461        }
462
463        impl<I, const D: i32> $trait for &QuadInt<I, D>
464        where I: IntType, for<'x> &'x I: IntOps<I> {
465            type Output = QuadInt<I, D>;
466
467            fn $method(self) -> Self::Output {
468                let (a, b) = self.pair();
469                QuadInt(<&I>::$method(a), <&I>::$method(b))
470            }
471        }
472    };
473}
474
475macro_rules! impl_add_op {
476    ($trait:ident, $method:ident) => {
477        #[auto_ops]
478        impl<I, const D: i32> $trait<&QuadInt<I, D>> for &QuadInt<I, D>
479        where I: IntType, for<'x> &'x I: IntOps<I> {
480            type Output = QuadInt<I, D>;
481
482            fn $method(self, rhs: &QuadInt<I, D>) -> Self::Output {
483                let (a, b) = self.pair();
484                let (c, d) =  rhs.pair();
485                QuadInt(<&I>::$method(a, c), <&I>::$method(b, d))
486            }
487        }
488    };
489}
490
491macro_rules! impl_alg_op {
492    ($trait:ident) => {
493        impl<I, const D: i32> $trait<Self> for QuadInt<I, D>
494        where I: IntType, for<'x> &'x I: IntOps<I> {}
495
496        impl<I, const D: i32> $trait<QuadInt<I, D>> for &QuadInt<I, D>
497        where I: IntType, for<'x> &'x I: IntOps<I> {}
498    };
499}
500
501macro_rules! impl_alg_op_d {
502    ($trait:ident, $d:literal) => {
503        impl<I> $trait<Self> for QuadInt<I, $d>
504        where I: IntType, for<'x> &'x I: IntOps<I> {}
505
506        impl<I> $trait<QuadInt<I, $d>> for &QuadInt<I, $d>
507        where I: IntType, for<'x> &'x I: IntOps<I> {}
508    };
509}
510
511use {impl_unop, impl_add_op, impl_alg_op, impl_alg_op_d};
512
513#[cfg(test)]
514mod tests {
515    use super::*;
516    use num_bigint::BigInt;
517
518    #[test]
519    fn check() {
520        fn check<T>() where T: Ring, for<'a> &'a T: RingOps<T> {}
521
522        type A = QuadInt<i32, -1>;
523        type B = QuadInt<i64, -1>;
524        type C = QuadInt<BigInt, -1>;
525
526        check::<A>();
527        check::<B>();
528        check::<C>();
529    }
530
531    #[test]
532    fn display_gauss() {
533        type A = QuadInt<i32, -1>;
534        let a = A::new(-2, 0);
535        let b = A::new(0, 3);
536        let c = A::new(1, 3);
537        let d = A::new(2, -3);
538        assert_eq!(format!("{}", a), "-2");
539        assert_eq!(format!("{}", b), "3i");
540        assert_eq!(format!("{}", c), "1 + 3i");
541        assert_eq!(format!("{}", d), "2 - 3i");
542    }
543
544    #[test]
545    fn math_symbol_names_the_ring() {
546        // `D ≡ 1 (mod 4)` adjoins `(1 + √D)/2`, not `√D`.
547        assert_eq!(QuadInt::<i32, -1>::math_symbol(), "Z[i]");
548        assert_eq!(QuadInt::<i32, -3>::math_symbol(), "Z[ω]");
549        assert_eq!(QuadInt::<i32, 5>::math_symbol(), "Z[(1 + √5)/2]");
550        assert_eq!(QuadInt::<i32, -2>::math_symbol(), "Z[√-2]");
551    }
552
553    #[test]
554    fn display_eisen() {
555        type A = QuadInt<i32, -3>;
556        let a = A::new(-2, 0);
557        let b = A::new(0, 3);
558        let c = A::new(1, 3);
559        let d = A::new(2, -3);
560        assert_eq!(format!("{}", a), "-2");
561        assert_eq!(format!("{}", b), "3ω");
562        assert_eq!(format!("{}", c), "1 + 3ω");
563        assert_eq!(format!("{}", d), "2 - 3ω");
564    }
565
566    #[test]
567    fn zero() {
568        type A = QuadInt<i32, -3>;
569        let a = A::new(1, 3);
570        let b = A::zero();
571        let c = a + b;
572        assert_eq!(c, A::new(1, 3));
573
574        let a = A::new(0, 0);
575        let b = A::new(0, 1);
576        assert!(a.is_zero());
577        assert!(!b.is_zero());
578    }
579
580    #[test]
581    fn one() {
582        type A = QuadInt<i32, -3>;
583
584        let a = A::new(1, 3);
585        let b = A::one();
586        let c = a * b;
587        assert_eq!(c, A::new(1, 3));
588
589        let a = A::new(1, 0);
590        let b = A::new(0, 1);
591        let c = A::new(1, 1);
592
593        assert!(a.is_one());
594        assert!(!b.is_one());
595        assert!(!c.is_one());
596    }
597
598    #[test]
599    fn add() {
600        type A = QuadInt<i32, -3>;
601        let a = A::new(1, 3);
602        let b = A::new(-3, 2);
603        let c = a + b;
604        assert_eq!(c, A::new(-2, 5));
605    }
606
607    #[test]
608    fn sub() {
609        type A = QuadInt<i32, -3>;
610        let a = A::new(1, 3);
611        let b = A::new(-3, 2);
612        let c = a - b;
613        assert_eq!(c, A::new(4, 1));
614    }
615
616    #[test]
617    fn neg() {
618        type A = QuadInt<i32, -3>;
619        let a = A::new(1, 3);
620        assert_eq!(-a, A::new(-1, -3));
621    }
622
623    #[test]
624    fn mul_gauss() {
625        type A = QuadInt<i32, -1>; // GaussInt
626        let a = A::new(1, 3);
627        let b = A::new(2, -1);
628        let c = a * b;
629        assert_eq!(c, A::new(5, 5));
630    }
631
632    #[test]
633    fn mul_eisen() {
634        type A = QuadInt<i32, -3>; // EisenInt
635        let a = A::new(1, 3);
636        let b = A::new(2, -1);
637        let c = a * b;
638        assert_eq!(c, A::new(5, 2));
639    }
640
641    #[test]
642    fn norm_gauss() {
643        type A = QuadInt<i32, -1>; // GaussInt
644        let a = A::new(3, -2);
645        assert_eq!(a.norm(), 13);
646    }
647
648    #[test]
649    fn norm_eisen() {
650        type A = QuadInt<i32, -3>; // GaussInt
651        let a = A::new(3, -2);
652        assert_eq!(a.norm(), 7);
653    }
654
655    #[test]
656    fn conj_gauss() {
657        type A = QuadInt<i32, -1>; // GaussInt
658        let a = A::new(3, -2);
659        assert_eq!(a.conj(), A::new(3, 2));
660    }
661
662    #[test]
663    fn conj_eisen() {
664        type A = QuadInt<i32, -3>; // EisenInt
665        let a = A::new(3, -2);
666        assert_eq!(a.conj(), A::new(1, 2));
667    }
668
669    #[test]
670    fn unit_gauss() {
671        type A = QuadInt<i32, -1>; // GaussInt
672        assert!(A::new(1,  0).is_unit());
673        assert!(A::new(0,  1).is_unit());
674        assert!(A::new(-1, 0).is_unit());
675        assert!(A::new(0, -1).is_unit());
676        assert!(!A::new(1,  1).is_unit());
677    }
678
679    #[test]
680    fn gcd_normalized() {
681        // `x` divides `y` here, the branch that used to return `x` unchanged.
682        type A = QuadInt<i32, -1>; // GaussInt
683        let (x, y) = (A::new(0, -3), A::new(0, -6));
684
685        let d = EucRing::gcd(&x, &y);
686        assert_eq!(d, d.normalized(), "gcd is not normalized");
687
688        let (d, s, t) = EucRing::gcdx(&x, &y);
689        assert_eq!(d, d.normalized(), "gcdx's d is not normalized");
690        assert_eq!(&s * &x + &t * &y, d, "Bezout fails");
691        assert_eq!(EucRing::gcd(&x, &y), d, "gcd disagrees with gcdx");
692    }
693
694    #[test]
695    fn lcm_zero() {
696        // lcm(0, y) = 0, and gcd(0, 0) = 0 must not reach the division.
697        type A = QuadInt<i32, -1>; // GaussInt
698        let (z, a) = (A::new(0, 0), A::new(2, 1));
699        assert_eq!(EucRing::lcm(&z, &z), z);
700        assert_eq!(EucRing::lcm(&z, &a), z);
701        assert_eq!(EucRing::lcm(&a, &z), z);
702    }
703
704    #[test]
705    fn unit_eisen() {
706        type A = QuadInt<i32, -3>; // EisenInt
707        assert!(A::new(1,  0).is_unit());
708        assert!(A::new(0,  1).is_unit());
709        assert!(A::new(-1, 1).is_unit());
710        assert!(A::new(-1, 0).is_unit());
711        assert!(A::new(0, -1).is_unit());
712        assert!(A::new(1, -1).is_unit());
713        assert!(!A::new(1,  1).is_unit());
714    }
715
716    #[test]
717    fn inv_gauss() {
718        type A = QuadInt<i32, -1>; // GaussInt
719        assert_eq!(A::new(1,  0).inv(), Some(A::new(1,  0)));
720        assert_eq!(A::new(-1, 0).inv(), Some(A::new(-1, 0)));
721        assert_eq!(A::new(0,  1).inv(), Some(A::new(0, -1)));
722        assert_eq!(A::new(0, -1).inv(), Some(A::new(0,  1)));
723        assert_eq!(A::new(1,  1).inv(), None);
724    }
725
726    #[test]
727    fn inv_eisen() {
728        type A = QuadInt<i32, -3>; // EisenInt
729        assert_eq!(A::new(1,  0).inv(), Some(A::new(1,  0)));
730        assert_eq!(A::new(0,  1).inv(), Some(A::new(1, -1)));
731        assert_eq!(A::new(-1, 1).inv(), Some(A::new(0, -1)));
732        assert_eq!(A::new(-1, 0).inv(), Some(A::new(-1, 0)));
733        assert_eq!(A::new(0, -1).inv(), Some(A::new(-1, 1)));
734        assert_eq!(A::new(1, -1).inv(), Some(A::new(0,  1)));
735        assert_eq!(A::new(1,  1).inv(), None);
736    }
737
738    #[test]
739    fn normalizing_unit_gauss() {
740        type A = QuadInt<i32, -1>; // GaussInt
741        assert_eq!(A::new(1,  0).normalizing_unit(), A::new(1,  0));
742        assert_eq!(A::new(-1, 0).normalizing_unit(), A::new(-1, 0));
743        assert_eq!(A::new(2,  0).normalizing_unit(), A::new(1,  0));
744        assert_eq!(A::new(0,  1).normalizing_unit(), A::new(0, -1));
745        assert_eq!(A::new(0, -1).normalizing_unit(), A::new(0,  1));
746        assert_eq!(A::new(0,  2).normalizing_unit(), A::new(0, -1));
747
748        assert_eq!(A::new(1,  1).normalizing_unit(), A::new(1,  0));
749        assert_eq!(A::new(-1, 1).normalizing_unit(), A::new(0, -1));
750        assert_eq!(A::new(-1,-1).normalizing_unit(), A::new(-1, 0));
751        assert_eq!(A::new(1, -1).normalizing_unit(), A::new(0,  1));
752    }
753
754    #[test]
755    fn normalizing_unit_eisen() {
756        type A = QuadInt<i32, -3>; // EisenInt
757        assert_eq!(A::new(1,  0).normalizing_unit(), A::new(1,  0));
758        assert_eq!(A::new(0,  1).normalizing_unit(), A::new(1, -1));
759        assert_eq!(A::new(-1, 1).normalizing_unit(), A::new(0, -1));
760        assert_eq!(A::new(-1, 0).normalizing_unit(), A::new(-1, 0));
761        assert_eq!(A::new(0, -1).normalizing_unit(), A::new(-1, 1));
762        assert_eq!(A::new(1, -1).normalizing_unit(), A::new(0,  1));
763    }
764
765    #[test]
766    fn rem_gauss() {
767        type A = QuadInt<i32, -1>; // GaussInt
768        let a = A::new(49, -58);
769        let b = A::new(7, 9);
770        let q = &a / &b;
771        let r = &a % &b;
772
773        assert!(!r.is_zero());
774        assert!(r.norm() < a.norm());
775        assert_eq!(a, b * q + r);
776    }
777
778    #[test]
779    fn rem_eisen() {
780        type A = QuadInt<i32, -3>; // EisenInt
781        let a = A::new(49, -58);
782        let b = A::new(7, 9);
783        let q = &a / &b;
784        let r = &a % &b;
785
786        assert!(!r.is_zero());
787        assert!(r.norm() < a.norm());
788        assert_eq!(a, b * q + r);
789    }
790}
yui_core/conc/num/qint.rs

yui_core/conc/num/
qint.rs
