gaussiant 0.8.0

//! Gaussian integers in Rust.
//!
//! A [Gaussian integer] is a complex number whose real and imaginary parts are both integers.
//!
//! [Gaussian integer]: https://en.wikipedia.org/wiki/Gaussian_integer
//! [Gaussian prime]: crate::GaussianInt#method.is_gaussian_prime
#![deny(missing_docs)]
#![allow(clippy::needless_return)]

#[cfg(doctest)]
#[macro_use]
extern crate doc_comment;

#[cfg(doctest)]
doctest!("../README.md", readme);

use std::str::FromStr;

use num_complex::{Complex, ParseComplexError};
use num_integer::Integer;
use num_traits::{Num, One, PrimInt, Signed, Zero};

mod ops;

/// A Gaussian integer is a complex number whose real and imaginary parts are both integers.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct GaussianInt<T: PrimInt + Integer>(pub Complex<T>);

/// Creates a new [`GaussianInt`].
///
/// # Example
///
/// ```
/// # use gaussiant::{GaussianInt, gaussint};
/// # fn main() {
/// let z = gaussint!(1, 1);
/// let _z = gaussint!(1, -1);
/// assert_eq!(z * _z, gaussint!(2, 0));
/// # }
/// ```
#[macro_export]
macro_rules! gaussint {
    ($a:expr,$b:expr) => {
        GaussianInt::new($a, $b)
    };
    ($n:expr) => {
        GaussianInt::new($n, 0)
    };
}

impl<T: PrimInt + Integer> GaussianInt<T> {
    /// Creates a new [`GaussianInt`].
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// // 𝑖
    /// let square_root_of_negative_one = GaussianInt::new(0, 1);
    /// # }
    /// ```
    pub fn new(r: T, i: T) -> Self {
        Self(Complex::new(r, i))
    }

    /// Given a Gaussian integer z₀, called a *modulus*,
    /// two Gaussian integers z₁, z₂ are *congruent modulo z₀*,
    /// if their difference is a multiple of z₀.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::{GaussianInt, gaussint};
    /// # fn main() {
    /// // 2 + 5i ≡ i mod 1 + 2i
    /// let c1 = gaussint!(2, 5);
    /// let c2 = gaussint!(0, 1);
    /// let c3 = gaussint!(1, 2);
    /// assert!(c1.congruent(c2, c3));
    /// # }
    /// ```
    pub fn congruent(&self, other: Self, modulus: Self) -> bool {
        (*self - other) % modulus == Self::zero()
    }
}

impl<T: PrimInt + Integer + Signed> GaussianInt<T> {
    /// Returns the complex conjugate.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(5, 4);
    /// assert_eq!(z.conj(), GaussianInt::new(5, -4));
    /// # }
    /// ```
    pub fn conj(&self) -> Self {
        Self::new(self.0.re, -self.0.im)
    }

    /// Returns the norm.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(2, 7);
    /// assert_eq!(z.norm(), 53);
    /// # }
    /// ```
    pub fn norm(&self) -> usize {
        let a = self.0.re;
        let b = self.0.im;
        (T::pow(a, 2) + T::pow(b, 2)).to_usize().unwrap()
    }

    /// Returns `true` if `self` divides `other`.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let c1 = GaussianInt::new(5, 0);
    /// let c2 = GaussianInt::new(1, 2);
    /// assert!(c2.divides(c1));
    /// # }
    /// ```
    pub fn divides(&self, other: Self) -> bool {
        *self != Self::zero() && (other % *self) == Self::zero()
    }

    /// Tests whether a Gaussian integer is a rational integer.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(2, 7);
    /// let z2 = GaussianInt::new(0, -7);
    /// assert!((z + z2).is_rational());
    /// # }
    /// ```
    pub fn is_rational(&self) -> bool {
        self.0.im == T::zero()
    }

    /// Tests for [Gaussian primality].
    ///
    /// A Gaussian integer *a* + *b*i is a *Gaussian prime* if and only if either:
    ///
    /// 1. one of *a*, *b* is zero,
    ///    and the absolute value of the other
    ///    is a prime number of the form 4*n* + 3
    ///    (with *n* a nonnegative integer)
    /// 2. both *a* and *b* are nonzero,
    ///    and *a*² + *b*² is a prime number
    ///    (which will not be of the form 4*n* + 3).
    ///
    /// [Gaussian primality]: https://en.wikipedia.org/wiki/Gaussian_integer#Gaussian_primes
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(2, 7);
    /// assert!(z.is_gaussian_prime());
    /// # }
    /// ```
    pub fn is_gaussian_prime(&self) -> bool {
        let a = self.0.re;
        let b = self.0.im;

        // These numbers would cause integer overflow panics below.
        match (a.abs().to_isize().unwrap(), b.abs().to_isize().unwrap()) {
            (0, 0) => return false,
            (1, 1) => return true,
            (-1, -1) => return true,
            (2, 0) => return false,
            (0, 2) => return false,
            _ => {}
        }

        let condition_1 = match (a.is_zero(), b.is_zero()) {
            (true, false) => {
                let other = b.abs().to_u64().unwrap();
                primal::is_prime(other) && (other - 3) % 4 == 0
            }
            (false, true) => {
                let other = a.abs().to_u64().unwrap();
                primal::is_prime(other) && (other - 3) % 4 == 0
            }
            _ => false,
        };

        let condition_2 = match (a.is_zero(), b.is_zero()) {
            (false, false) => {
                let a = a.abs().to_u64().unwrap();
                let b = b.abs().to_u64().unwrap();
                let sum_of_squares = u64::pow(a, 2) + u64::pow(b, 2);
                let sum_of_squares_is_4n_plus_3 = (sum_of_squares - 3) % 4 == 0;
                primal::is_prime(sum_of_squares) && !sum_of_squares_is_4n_plus_3
            }
            _ => false,
        };

        condition_1 || condition_2
    }

    /// Returns an array of the units of ℤ\[*i*\], the ring of Gaussian integers.
    ///
    /// The units are 1, -1, *i*, -*i*.
    pub fn units() -> [Self; 4] {
        [
            Self::one(),                     //  1
            -Self::one(),                    // -1
            Self::new(T::zero(), T::one()),  //  i
            Self::new(T::zero(), -T::one()), // -i
        ]
    }

    /// Gaussian integers are called associates
    /// if they can be obtained from one another by multiplication by units.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z1 = GaussianInt::new(1, 1);
    /// let z2 = GaussianInt::new(1, -1);
    /// assert!(z1.is_associated(z2));
    /// # }
    /// ```
    pub fn is_associated(&self, other: Self) -> bool {
        for u in GaussianInt::units() {
            if (*self * u) == other {
                return true;
            }
        }
        false
    }

    /// Tests whether a Gaussian integer is "even."
    ///
    /// A Gaussian integer *z* is "even" if *z* ≡ 0 mod 1+*i*.
    ///
    /// See <https://en.wikipedia.org/wiki/Gaussian_integer#Examples>.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(3, 1);
    /// assert!(z.is_even());
    /// # }
    /// ```
    pub fn is_even(&self) -> bool {
        let modulus = Self::new(T::one(), T::one());
        // self ≡ 0 mod 1+i
        self.congruent(Self::zero(), modulus)
    }

    /// Tests whether a Gaussian integer is "odd."
    ///
    /// A Gaussian integer *z* is "odd" if *z* ≡ 1 mod 1+*i*.
    ///
    /// See <https://en.wikipedia.org/wiki/Gaussian_integer#Examples>.
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let z = GaussianInt::new(2, 1);
    /// assert!(z.is_odd());
    /// # }
    /// ```
    pub fn is_odd(&self) -> bool {
        let modulus = Self::new(T::one(), T::one());
        // self ≡ 1 mod 1+i
        self.congruent(Self::one(), modulus)
    }
}

impl<T: PrimInt + Integer + Signed> GaussianInt<T>
where
    f64: From<T>,
{
    /// Convert to polar form (r, theta), such that
    /// `self = r * exp(i * theta)`
    ///
    /// # Example
    ///
    /// ```
    /// # use gaussiant::GaussianInt;
    /// # fn main() {
    /// let c = GaussianInt::new(0, 1);
    /// // The polar form of *i* is (1, π/2).
    /// assert_eq!(c.to_polar(), (1f64, std::f64::consts::PI / 2f64));
    /// # }
    /// ```
    pub fn to_polar(&self) -> (f64, f64) {
        let a = self.0.re;
        let b = self.0.im;
        let a: f64 = a.into();
        let b: f64 = b.into();
        Complex::new(a, b).to_polar()
    }
}

/// Returns an iterator of all Gaussian integers *a* + *b*i
/// where |*a*|,|*b*| ≤ `n`.
pub fn get_g_ints(n: isize) -> impl Iterator<Item = GaussianInt<isize>> + 'static {
    let mut integers: Vec<GaussianInt<_>> = vec![];
    for a in -n..=n {
        for b in -n..=n {
            let z = GaussianInt::new(a, b);
            integers.push(z);
        }
    }
    integers.into_iter()
}

/// Returns an iterator of all Gaussian integers *a* + *b*i
/// where *a* is positive (or zero) and |*b*| ≤ `n`.
pub fn get_pos_g_ints(n: isize) -> impl Iterator<Item = GaussianInt<isize>> + 'static {
    let mut pos_integers: Vec<GaussianInt<_>> = vec![];
    for a in 0..=n {
        for b in -n..=n {
            let z = GaussianInt::new(a, b);
            pos_integers.push(z);
        }
    }
    pos_integers.into_iter()
}

/// Returns an iterator of all Gaussian primes *a* + *b*i
/// where |a|,|b| ≤ `n`.
pub fn get_g_primes(n: isize) -> impl Iterator<Item = GaussianInt<isize>> + 'static {
    let set = get_g_ints(n);
    let mut primes: Vec<GaussianInt<_>> = vec![];
    for z in set {
        if z.is_gaussian_prime() {
            primes.push(z);
        }
    }
    primes.into_iter()
}

/// Returns an iterator of all Gaussian primes *a* + *b*i
/// where *a* is positive (or zero) and |*b*| ≤ `n`.
pub fn get_pos_g_primes(n: isize) -> impl Iterator<Item = GaussianInt<isize>> + 'static {
    let set = get_pos_g_ints(n);
    let mut pos_primes: Vec<GaussianInt<_>> = vec![];
    for z in set {
        if z.is_gaussian_prime() {
            pos_primes.push(z);
        }
    }
    pos_primes.into_iter()
}

impl<T: PrimInt + Integer> One for GaussianInt<T> {
    fn one() -> Self {
        GaussianInt::new(T::one(), T::zero())
    }
}

impl<T: PrimInt + Integer> Zero for GaussianInt<T> {
    fn zero() -> Self {
        GaussianInt::new(T::zero(), T::zero())
    }

    fn is_zero(&self) -> bool {
        *self == GaussianInt::zero()
    }
}

impl<T: PrimInt + Integer> From<Complex<T>> for GaussianInt<T> {
    fn from(z: Complex<T>) -> Self {
        Self(z)
    }
}

impl<T: PrimInt + Integer> From<GaussianInt<T>> for isize {
    fn from(g: GaussianInt<T>) -> Self {
        g.0.re.to_isize().unwrap()
    }
}

impl<T> FromStr for GaussianInt<T>
where
    T: PrimInt + Integer + FromStr + Num + Clone,
{
    type Err = ParseComplexError<T::Err>;

    /// Parses `a ± bi`, `ai ± b`, `a`, or `bi` where `a` and `b` are of type `T`.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::str::FromStr;
    /// # use gaussiant::{GaussianInt, gaussint};
    /// # fn main() {
    /// assert_eq!(
    ///     GaussianInt::new(1, 1),
    ///     GaussianInt::from_str("1+i").expect("parse problem!")
    /// );
    /// # }
    /// ```
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(Self::from(Complex::from_str(s)?))
    }
}

impl<T: PrimInt + Integer> std::fmt::Display for GaussianInt<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let one = T::one();
        let zero = T::zero();
        // Can't do -one because self isn't necessarily `Signed`
        let im_is_neg_one = self.0.im + one == zero;

        // a
        if self.0.im == zero {
            return write!(f, "{}", self.0.re.to_isize().unwrap());
        }
        // i
        if self.0.re == zero && self.0.im == T::one() {
            return write!(f, "i");
        }
        // -i
        if self.0.re == zero && im_is_neg_one {
            return write!(f, "-i");
        }
        // bi
        if self.0.re == zero && !im_is_neg_one {
            return write!(f, "{}i", self.0.im.to_isize().unwrap());
        }
        // a+i
        if self.0.im == one {
            return write!(f, "{}+i", self.0.re.to_isize().unwrap());
        }

        if self.0.im < zero {
            // -i
            if self.0.re == zero && im_is_neg_one {
                return write!(f, "-i");
            }
            // a-i
            if self.0.im + one == zero {
                write!(f, "{}-i", self.0.re.to_isize().unwrap(),)
            } else {
                // a-bi
                return write!(
                    f,
                    "{}{}i",
                    self.0.re.to_isize().unwrap(),
                    self.0.im.to_isize().unwrap()
                );
            }
        } else {
            // a+bi
            return write!(
                f,
                "{}+{}i",
                self.0.re.to_isize().unwrap(),
                self.0.im.to_isize().unwrap()
            );
        }
    }
}

#[cfg(test)]
mod tests;