extern crate maths_traits;
extern crate num_traits;
extern crate rug;
#[path = "macros.rs"]
#[macro_use]
mod macros;
use maths_traits::{
algebra,
algebra::{additive::*, multiplicative::*, EuclideanDiv},
analysis,
analysis::Sign,
};
use num_traits::{
cast::{FromPrimitive, ToPrimitive},
ops::checked::*,
};
use rug::{ops::DivRounding, Assign};
use std::{
fmt::{Display, Formatter, Result as FmtResult},
ops,
ops::{Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign},
};
#[derive(Clone, Debug, PartialEq, PartialOrd, Eq, Ord)]
pub struct Integer {
pub val: rug::Integer,
}
impl Display for Integer {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.val.fmt(f)
}
}
impl<T> From<T> for Integer
where
rug::Integer: From<T>,
{
fn from(src: T) -> Self {
Self {
val: rug::Integer::from(src),
}
}
}
impl ToPrimitive for Integer {
fn to_i64(&self) -> Option<i64> {
self.val.to_i64()
}
fn to_u64(&self) -> Option<u64> {
self.val.to_u64()
}
fn to_isize(&self) -> Option<isize> {
self.val.to_isize()
}
fn to_i8(&self) -> Option<i8> {
self.val.to_i8()
}
fn to_i16(&self) -> Option<i16> {
self.val.to_i16()
}
fn to_i32(&self) -> Option<i32> {
self.val.to_i32()
}
fn to_i128(&self) -> Option<i128> {
self.val.to_i128()
}
fn to_usize(&self) -> Option<usize> {
self.val.to_usize()
}
fn to_u8(&self) -> Option<u8> {
self.val.to_u8()
}
fn to_u16(&self) -> Option<u16> {
self.val.to_u16()
}
fn to_u32(&self) -> Option<u32> {
self.val.to_u32()
}
fn to_u128(&self) -> Option<u128> {
self.val.to_u128()
}
fn to_f32(&self) -> Option<f32> {
Some(self.val.to_f32())
}
fn to_f64(&self) -> Option<f64> {
Some(self.val.to_f64())
}
}
impl FromPrimitive for Integer {
fn from_i64(n: i64) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_u64(n: u64) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_isize(n: isize) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_i8(n: i8) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_i16(n: i16) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_i32(n: i32) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_i128(n: i128) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_usize(n: usize) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_u8(n: u8) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_u16(n: u16) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_u32(n: u32) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_u128(n: u128) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n),
})
}
fn from_f32(n: f32) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n.to_i32()?),
})
}
fn from_f64(n: f64) -> Option<Self> {
Some(Self {
val: rug::Integer::from(n.to_i64()?),
})
}
}
impl AddAssociative for Integer {}
impl AddCommutative for Integer {}
impl MulAssociative for Integer {}
impl MulCommutative for Integer {}
impl analysis::ordered::AddOrdered for Integer {}
impl analysis::ordered::MulOrdered for Integer {}
impl algebra::ring_like::EuclideanDiv for Integer {
type Naturals = Integer;
fn euclid_norm(&self) -> Self::Naturals {
self.clone().abs()
}
fn div_euc(self, rhs: Self) -> Self {
Self {
val: self.val.div_euc(rhs.val),
}
}
fn rem_euc(self, rhs: Self) -> Self {
self % rhs
}
fn div_alg(self, rhs: Self) -> (Self, Self) {
(self.clone().div_euc(rhs.clone()), self.rem_euc(rhs))
}
}
impl analysis::ordered::ArchimedeanProperty for Integer {}
impl analysis::ordered::ArchimedeanDiv for Integer {
fn embed_nat<N: algebra::integer::Natural>(n: N) -> Self {
Self::from(n.to_u128().unwrap())
}
fn div_arch(self, rhs: Self) -> Self {
self.div_euc(rhs)
}
fn rem_arch(self, rhs: Self) -> Self {
self.rem_euc(rhs)
}
fn div_alg_arch(self, rhs: Self) -> (Self, Self) {
self.div_alg(rhs)
}
}
impl_arith! { Integer, Add { add }, AddAssign {add_assign} }
impl_arith! { Integer, Sub { sub }, SubAssign {sub_assign} }
impl_arith! { Integer, Mul { mul }, MulAssign {mul_assign} }
impl_arith! { Integer, Div { div }, DivAssign {div_assign} }
impl_arith! { Integer, Rem { rem }, RemAssign {rem_assign} }
impl_arith_diff! { Integer, Shl { shl }, ShlAssign {shl_assign} }
impl_arith_diff! { Integer, Shr { shr }, ShrAssign {shr_assign} }
impl CheckedAdd for Integer {
fn checked_add(&self, v: &Self) -> Option<Self> {
Some(self + v)
}
}
impl CheckedSub for Integer {
fn checked_sub(&self, v: &Self) -> Option<Self> {
Some(self - v)
}
}
impl CheckedNeg for Integer {
fn checked_neg(&self) -> Option<Self> {
Some(Self {
val: -self.val.clone(),
})
}
}
impl CheckedMul for Integer {
fn checked_mul(&self, v: &Self) -> Option<Self> {
Some(self * v)
}
}
impl CheckedDiv for Integer {
fn checked_div(&self, v: &Self) -> Option<Self> {
if v.is_zero() {
None
} else {
Some(self / v)
}
}
}
impl CheckedRem for Integer {
fn checked_rem(&self, v: &Self) -> Option<Self> {
if v.is_zero() {
None
} else {
Some(self % v)
}
}
}
impl CheckedShl for Integer {
fn checked_shl(&self, v: u32) -> Option<Self> {
Some(self << v)
}
}
impl CheckedShr for Integer {
fn checked_shr(&self, v: u32) -> Option<Self> {
Some(self >> v)
}
}
impl algebra::group_like::additive::Neg for Integer {
type Output = Integer;
fn neg(self) -> Self::Output {
Self::Output { val: -self.val }
}
}
impl algebra::group_like::additive::Zero for Integer {
fn zero() -> Self {
Self {
val: rug::Integer::new(),
}
}
fn is_zero(&self) -> bool {
self.val == 0
}
fn set_zero(&mut self) {
self.val.assign(0);
}
}
impl algebra::group_like::multiplicative::One for Integer {
fn one() -> Self {
Self {
val: rug::Integer::from(1),
}
}
fn is_one(&self) -> bool {
self.val == 1
}
fn set_one(&mut self) {
self.val.assign(1);
}
}
impl algebra::ring_like::Distributive for Integer {}
impl algebra::ring_like::Divisibility for Integer {
fn divides(self, rhs: Self) -> bool {
(rhs % self).is_zero()
}
fn divide(self, rhs: Self) -> Option<Self> {
let q = rhs.val.clone() / &self.val;
if self.val * &q == rhs.val {
Some(Self::from(q))
} else {
None
}
}
fn unit(&self) -> bool {
self.val == 1 || self.val == -1
}
fn inverse(self) -> Option<Self> {
match self.unit() {
false => None,
true => Some(self),
}
}
}
impl analysis::ordered::Sign for Integer {
fn signum(self) -> Self {
Self {
val: self.val.signum(),
}
}
fn abs(self) -> Self {
Self {
val: self.val.abs(),
}
}
}
impl algebra::ring_like::GCD for Integer {
fn gcd(self, rhs: Self) -> Self {
let (mut a, mut b) = if self > rhs { (self, rhs) } else { (rhs, self) };
while !b.is_zero() {
let r = a % &b;
a = b;
b = r;
}
a
}
fn lcm(self, rhs: Self) -> Self {
(self.clone() * &rhs).abs() / self.gcd(rhs)
}
}
impl algebra::ring_like::Bezout for Integer {
fn bezout_with_gcd(self, rhs: Self) -> (Self, Self, Self) {
let mut r = self.val;
let mut u = rug::Integer::from(1);
let mut v = rug::Integer::from(0);
let mut rr = rhs.val;
let mut uu = rug::Integer::from(0);
let mut vv = rug::Integer::from(1);
while rr != 0 {
let q = r.clone() / &rr;
let rs = r;
let us = u;
let vs = v;
r = rr.clone();
u = uu.clone();
v = vv.clone();
rr = rs - &q * rr;
uu = us - &q * uu;
vv = vs - &q * vv;
}
(Self { val: r }, Self { val: u }, Self { val: v })
}
fn bezout_coefficients(self, rhs: Self) -> (Self, Self) {
let r = self.bezout_with_gcd(rhs);
(r.1, r.2)
}
}
impl algebra::ring_like::NoZeroDivisors for Integer {}
impl algebra::ring_like::UniquelyFactorizable for Integer {}
impl algebra::ring_like::Primality for Integer {
fn prime(&self) -> bool {
if self.val < 2 {
return false;
}
let mut i = Self::from(2);
let max = Self::from(self.val.clone().sqrt());
while i <= max {
if (self.clone() % &i).is_zero() {
return false;
}
i += 1;
}
true
}
fn irreducible(&self) -> bool {
self.prime()
}
}
impl algebra::integer::Integer for Integer {}
impl algebra::integer::Natural for Integer {}
impl algebra::integer::IntegerSubset for Integer {
type Signed = Integer;
type Unsigned = Integer;
fn as_signed(self) -> Self::Signed {
self
}
fn as_unsigned(self) -> Self::Unsigned {
self
}
}
#[cfg(test)]
mod tests {
use super::*;
use maths_traits::algebra::{Bezout, Divisibility, Primality, GCD};
#[test]
fn test_ops() {
let a = Integer::from(16);
let b = Integer::from(10);
let c = Integer::from(-6);
assert_eq!(b.clone() - a.clone(), c);
assert_eq!(&b - a.clone(), c);
assert_eq!(b.clone() - &a, c);
assert_eq!(&b - &a, c);
assert_eq!(b.clone() - a.to_i16().unwrap(), c);
assert_eq!(&b - a.to_i16().unwrap(), c);
}
#[test]
fn test_divisibility() {
assert_eq!(
Integer::from(11).divide(Integer::from(22)),
Some(Integer::from(2))
);
assert_eq!(Integer::from(11).divide(Integer::from(23)), None);
assert_eq!(
Integer::from(-11).divide(Integer::from(22)),
Some(Integer::from(-2))
);
assert_eq!(
Integer::from(11).divide(Integer::from(-22)),
Some(Integer::from(-2))
);
assert_eq!(
Integer::from(-11).divide(Integer::from(-22)),
Some(Integer::from(2))
);
assert_eq!(Integer::zero().inverse(), None);
assert_eq!(Integer::from(2).inverse(), None);
assert_eq!(Integer::one().inverse(), Some(Integer::one()));
assert_eq!(Integer::one().neg().inverse(), Some(Integer::one().neg()));
}
#[test]
fn test_gcd() {
assert_eq!(Integer::from(2).gcd(Integer::from(17)), Integer::from(1));
assert_eq!(Integer::from(27).gcd(Integer::from(72)), Integer::from(9));
assert_eq!(
Integer::from(70).lcm(Integer::from(154)),
Integer::from(770)
);
assert_eq!(
Integer::from(3131).lcm(Integer::from(57)),
Integer::from(178467)
);
}
#[test]
fn test_bezout() {
assert_eq!(
Integer::from(120).bezout_with_gcd(Integer::from(23)),
(Integer::from(1), Integer::from(-9), Integer::from(47))
);
}
#[test]
fn test_primality() {
assert!(Integer::from(2).prime());
assert!(Integer::from(3).prime());
assert!(Integer::from(101).prime());
assert!(!Integer::from(1).prime());
assert!(!Integer::from(4).prime());
assert!(!Integer::from(10201).prime());
}
#[test]
fn test_euclidean_div() {
assert_eq!(
Integer::from(11).div_alg(Integer::from(5)),
(Integer::from(2), Integer::from(1))
);
assert_eq!(
Integer::from(10).div_alg(Integer::from(11)),
(Integer::from(0), Integer::from(10))
);
}
}