haar_lib/num/
gaussian_int.rs

1//! ガウス整数
2use crate::impl_from;
3use crate::impl_ops;
4
5/// ガウス整数 $a + bi (a, b \in \mathbb{Z})$
6#[derive(Clone, Copy, Default, Debug, Eq, PartialEq, Hash)]
7pub struct GaussianInt {
8    /// 実部
9    pub re: i64,
10    /// 虚部
11    pub im: i64,
12}
13
14impl GaussianInt {
15    /// ガウス整数$a + bi$を返す。
16    pub fn new(a: i64, b: i64) -> Self {
17        Self { re: a, im: b }
18    }
19
20    /// `self`のノルム$N(\mathtt{self})$を返す。
21    ///
22    /// ただし、$N(a + bi) = a^2 + b^2$
23    pub fn norm(self) -> u64 {
24        (self.re * self.re + self.im * self.im) as u64
25    }
26
27    /// $\mathtt{self} = q \times \mathtt{b} + r (N(b) > N(r))$となる$q$と$r$を返す。
28    pub fn div_rem(self, b: Self) -> (Self, Self) {
29        let a = self;
30        assert!(b.re != 0 || b.im != 0);
31
32        let deno = b.re * b.re + b.im * b.im;
33        let d_re = (a.re * b.re + a.im * b.im) / deno;
34        let d_im = (a.im * b.re - a.re * b.im) / deno;
35
36        let (q, _) = (d_re - 1..=d_re + 1)
37            .flat_map(|re| {
38                (d_im - 1..=d_im + 1).map(move |im| {
39                    let q = Self { re, im };
40                    let d = (a - q * b).norm();
41                    (q, d)
42                })
43            })
44            .min_by_key(|(_, d)| *d)
45            .unwrap();
46
47        (q, self - q * b)
48    }
49
50    /// `self`が$0 + 0i$ならば`true`を返す。
51    pub fn is_zero(self) -> bool {
52        self.re == 0 && self.im == 0
53    }
54
55    /// `self`と`b`の最大公約数を返す。
56    pub fn gcd(self, b: Self) -> Self {
57        if b.is_zero() {
58            self
59        } else {
60            b.gcd(self % b)
61        }
62    }
63}
64
65impl_ops!(Add for GaussianInt, |a: Self, b: Self| Self::new(a.re + b.re, a.im + b.im));
66impl_ops!(Sub for GaussianInt, |a: Self, b: Self| Self::new(a.re - b.re, a.im - b.im));
67impl_ops!(Mul for GaussianInt, |a: Self, b: Self| Self::new(a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re));
68impl_ops!(Neg for GaussianInt, |a: Self| Self::new(-a.re, -a.im));
69
70impl_ops!(AddAssign for GaussianInt, |a: &mut Self, b: Self| *a = *a + b);
71impl_ops!(SubAssign for GaussianInt, |a: &mut Self, b: Self| *a = *a - b);
72impl_ops!(MulAssign for GaussianInt, |a: &mut Self, b: Self| *a = *a * b);
73
74impl_ops!(
75    /// $\mathtt{self} = q \times \mathtt{b} + r (N(b) > N(r))$となる$q$を返す。
76    Div for GaussianInt, |a: Self, b: Self| a.div_rem(b).0);
77impl_ops!(
78    /// $\mathtt{self} = q \times \mathtt{b} + r (N(b) > N(r))$となる$r$を返す。
79    Rem for GaussianInt, |a: Self, b: Self| a.div_rem(b).1);
80
81impl_ops!(DivAssign for GaussianInt, |a: &mut Self, b: Self| *a = *a / b);
82impl_ops!(RemAssign for GaussianInt, |a: &mut Self, b: Self| *a = *a % b);
83
84impl_from!((i64, i64) => GaussianInt, |(a, b)| Self::new(a, b));
85impl_from!(GaussianInt => (i64, i64), |GaussianInt { re, im }| (re, im));
haar_lib/num/gaussian_int.rs

haar_lib/num/
gaussian_int.rs
