use crate::integer::Integer;
use crate::natural::arithmetic::add::{limbs_add, limbs_add_limb};
use crate::natural::arithmetic::divisible_by::{
limbs_divisible_by, limbs_divisible_by_limb, limbs_divisible_by_val_ref,
};
use crate::natural::arithmetic::eq_mod::{limbs_eq_limb_mod_limb, limbs_mod_exact_odd_limb};
use crate::natural::arithmetic::mod_op::limbs_mod_limb;
use crate::natural::InnerNatural::{Large, Small};
use crate::natural::Natural;
use crate::platform::{Limb, BMOD_1_TO_MOD_1_THRESHOLD};
use malachite_base::fail_on_untested_path;
use malachite_base::num::arithmetic::traits::{
DivisibleBy, EqMod, EqModPowerOf2, NegMod, PowerOf2,
};
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::logic::traits::TrailingZeros;
pub_test! {limbs_eq_neg_limb_mod_limb(xs: &[Limb], y: Limb, m: Limb) -> bool {
limbs_eq_limb_mod_limb(xs, y.neg_mod(m), m)
}}
const fn quick_neg_mod(n: Limb, d: Limb) -> Limb {
if n <= d {
d - n
} else {
let d = d << d.leading_zeros();
(if n <= d { d } else { d << 1 }).wrapping_sub(n)
}
}
pub_const_test! {limbs_pos_limb_eq_neg_limb_mod(x: Limb, y: Limb, ms: &[Limb]) -> bool {
ms.len() == 2 && ms[1] == 1 && {
let (sum, overflow) = x.overflowing_add(y);
overflow && sum == ms[0]
}
}}
#[allow(clippy::absurd_extreme_comparisons)]
fn limbs_pos_eq_neg_limb_mod_helper(xs: &[Limb], y: Limb, ms: &[Limb]) -> Option<bool> {
let m_len = ms.len();
let x_len = xs.len();
assert!(m_len > 1);
assert!(x_len > 1);
assert_ne!(y, 0);
assert_ne!(*xs.last().unwrap(), 0);
assert_ne!(*ms.last().unwrap(), 0);
let m_0 = ms[0];
let twos = TrailingZeros::trailing_zeros(m_0);
if !xs[0].wrapping_neg().eq_mod_power_of_2(y, twos) {
return Some(false);
}
if m_len == 2 && m_0 != 0 {
let m_1 = ms[1];
if m_1 < Limb::power_of_2(twos) {
let m_0 = (m_0 >> twos) | (m_1 << (Limb::WIDTH - twos));
let y = quick_neg_mod(y, m_0);
return Some(if x_len >= BMOD_1_TO_MOD_1_THRESHOLD {
limbs_mod_limb(xs, m_0)
== if y < m_0 {
y
} else {
fail_on_untested_path("limbs_pos_eq_neg_limb_mod_helper, y >= m_0");
y % m_0
}
} else {
let r = limbs_mod_exact_odd_limb(xs, m_0, y);
r == 0 || r == m_0
});
}
}
None
}
pub_test! {limbs_pos_eq_neg_limb_mod_ref(xs: &[Limb], y: Limb, ms: &[Limb]) -> bool {
if let Some(equal) = limbs_pos_eq_neg_limb_mod_helper(xs, y, ms) {
return equal;
}
let mut scratch = limbs_add_limb(xs, y);
scratch.len() >= ms.len() && limbs_divisible_by_val_ref(&mut scratch, ms)
}}
pub_test! {limbs_pos_eq_neg_limb_mod(xs: &[Limb], y: Limb, ms: &mut [Limb]) -> bool {
if let Some(equal) = limbs_pos_eq_neg_limb_mod_helper(xs, y, ms) {
return equal;
}
let mut scratch = limbs_add_limb(xs, y);
scratch.len() >= ms.len() && limbs_divisible_by(&mut scratch, ms)
}}
pub_test! {limbs_pos_eq_neg_mod_limb(xs: &[Limb], ys: &[Limb], m: Limb) -> bool {
if xs.len() >= ys.len() {
limbs_pos_eq_mod_neg_limb_greater(xs, ys, m)
} else {
limbs_pos_eq_mod_neg_limb_greater(ys, xs, m)
}
}}
fn limbs_pos_eq_mod_neg_limb_greater(xs: &[Limb], ys: &[Limb], m: Limb) -> bool {
assert!(xs.len() > 1);
assert!(ys.len() > 1);
assert_ne!(*xs.last().unwrap(), 0);
assert_ne!(*ys.last().unwrap(), 0);
assert_ne!(m, 0);
if !xs[0]
.wrapping_neg()
.eq_mod_power_of_2(ys[0], TrailingZeros::trailing_zeros(m))
{
return false;
}
limbs_divisible_by_limb(&limbs_add(xs, ys), m)
}
fn limbs_pos_eq_neg_mod_greater_helper(xs: &[Limb], ys: &[Limb], ms: &[Limb]) -> Option<bool> {
assert!(ms.len() > 1);
assert!(xs.len() > 1);
assert!(ys.len() > 1);
assert_ne!(*xs.last().unwrap(), 0);
assert_ne!(*ys.last().unwrap(), 0);
assert_ne!(*ms.last().unwrap(), 0);
if !xs[0]
.wrapping_neg()
.eq_mod_power_of_2(ys[0], TrailingZeros::trailing_zeros(ms[0]))
{
Some(false)
} else {
None
}
}
pub_test! {limbs_pos_eq_neg_mod_ref(xs: &[Limb], ys: &[Limb], ms: &[Limb]) -> bool {
if xs.len() >= ys.len() {
limbs_pos_eq_neg_mod_greater_ref(xs, ys, ms)
} else {
limbs_pos_eq_neg_mod_greater_ref(ys, xs, ms)
}
}}
fn limbs_pos_eq_neg_mod_greater_ref(xs: &[Limb], ys: &[Limb], ms: &[Limb]) -> bool {
if let Some(equal) = limbs_pos_eq_neg_mod_greater_helper(xs, ys, ms) {
return equal;
}
let mut scratch = limbs_add(xs, ys);
scratch.len() >= ms.len() && limbs_divisible_by_val_ref(&mut scratch, ms)
}
pub_test! {limbs_pos_eq_neg_mod(xs: &[Limb], ys: &[Limb], ms: &mut [Limb]) -> bool {
if xs.len() >= ys.len() {
limbs_pos_eq_neg_mod_greater(xs, ys, ms)
} else {
limbs_pos_eq_neg_mod_greater(ys, xs, ms)
}
}}
fn limbs_pos_eq_neg_mod_greater(xs: &[Limb], ys: &[Limb], ms: &mut [Limb]) -> bool {
if let Some(equal) = limbs_pos_eq_neg_mod_greater_helper(xs, ys, ms) {
return equal;
}
let mut scratch = limbs_add(xs, ys);
scratch.len() >= ms.len() && limbs_divisible_by(&mut scratch, ms)
}
impl Natural {
fn eq_neg_limb_mod_limb(&self, other: Limb, m: Limb) -> bool {
m != 0
&& match *self {
Natural(Small(small)) => small % m == other.neg_mod(m),
Natural(Large(ref limbs)) => limbs_eq_neg_limb_mod_limb(limbs, other, m),
}
}
fn pos_eq_neg_mod(&self, other: &Natural, m: Natural) -> bool {
match (self, other, m) {
(_, _, natural_zero!()) => false,
(x, &natural_zero!(), m) => x.divisible_by(m),
(&natural_zero!(), y, m) => y.divisible_by(m),
(x, &Natural(Small(y)), Natural(Small(m))) => x.eq_neg_limb_mod_limb(y, m),
(&Natural(Small(x)), y, Natural(Small(m))) => y.eq_neg_limb_mod_limb(x, m),
(&Natural(Small(x)), &Natural(Small(y)), Natural(Large(ref m))) => {
limbs_pos_limb_eq_neg_limb_mod(x, y, m)
}
(&Natural(Large(ref xs)), &Natural(Large(ref ys)), Natural(Small(m))) => {
limbs_pos_eq_neg_mod_limb(xs, ys, m)
}
(&Natural(Large(ref xs)), &Natural(Small(y)), Natural(Large(ref mut m))) => {
limbs_pos_eq_neg_limb_mod(xs, y, m)
}
(&Natural(Small(x)), &Natural(Large(ref ys)), Natural(Large(ref mut m))) => {
limbs_pos_eq_neg_limb_mod(ys, x, m)
}
(&Natural(Large(ref xs)), &Natural(Large(ref ys)), Natural(Large(ref mut m))) => {
limbs_pos_eq_neg_mod(xs, ys, m)
}
}
}
fn pos_eq_neg_mod_ref(&self, other: &Natural, m: &Natural) -> bool {
match (self, other, m) {
(_, _, &natural_zero!()) => false,
(x, &natural_zero!(), m) => x.divisible_by(m),
(&natural_zero!(), y, m) => y.divisible_by(m),
(x, &Natural(Small(y)), &Natural(Small(m))) => x.eq_neg_limb_mod_limb(y, m),
(&Natural(Small(x)), y, &Natural(Small(m))) => y.eq_neg_limb_mod_limb(x, m),
(&Natural(Small(x)), &Natural(Small(y)), &Natural(Large(ref m))) => {
limbs_pos_limb_eq_neg_limb_mod(x, y, m)
}
(&Natural(Large(ref xs)), &Natural(Large(ref ys)), &Natural(Small(m))) => {
limbs_pos_eq_neg_mod_limb(xs, ys, m)
}
(&Natural(Large(ref xs)), &Natural(Small(y)), &Natural(Large(ref m))) => {
limbs_pos_eq_neg_limb_mod_ref(xs, y, m)
}
(&Natural(Small(x)), &Natural(Large(ref ys)), &Natural(Large(ref m))) => {
limbs_pos_eq_neg_limb_mod_ref(ys, x, m)
}
(&Natural(Large(ref xs)), &Natural(Large(ref ys)), &Natural(Large(ref m))) => {
limbs_pos_eq_neg_mod_ref(xs, ys, m)
}
}
}
}
impl EqMod<Integer, Natural> for Integer {
fn eq_mod(self, other: Integer, m: Natural) -> bool {
if self.sign == other.sign {
self.abs.eq_mod(other.abs, m)
} else {
self.abs.pos_eq_neg_mod(&other.abs, m)
}
}
}
impl<'a> EqMod<Integer, &'a Natural> for Integer {
fn eq_mod(self, other: Integer, m: &'a Natural) -> bool {
if self.sign == other.sign {
self.abs.eq_mod(other.abs, m)
} else {
self.abs.pos_eq_neg_mod_ref(&other.abs, m)
}
}
}
impl<'a> EqMod<&'a Integer, Natural> for Integer {
fn eq_mod(self, other: &'a Integer, m: Natural) -> bool {
if self.sign == other.sign {
self.abs.eq_mod(&other.abs, m)
} else {
self.abs.pos_eq_neg_mod(&other.abs, m)
}
}
}
impl<'a, 'b> EqMod<&'a Integer, &'b Natural> for Integer {
fn eq_mod(self, other: &'a Integer, m: &'b Natural) -> bool {
if self.sign == other.sign {
self.abs.eq_mod(&other.abs, m)
} else {
self.abs.pos_eq_neg_mod_ref(&other.abs, m)
}
}
}
impl<'a> EqMod<Integer, Natural> for &'a Integer {
fn eq_mod(self, other: Integer, m: Natural) -> bool {
if self.sign == other.sign {
(&self.abs).eq_mod(other.abs, m)
} else {
self.abs.pos_eq_neg_mod(&other.abs, m)
}
}
}
impl<'a, 'b> EqMod<Integer, &'b Natural> for &'a Integer {
fn eq_mod(self, other: Integer, m: &'b Natural) -> bool {
if self.sign == other.sign {
(&self.abs).eq_mod(other.abs, m)
} else {
self.abs.pos_eq_neg_mod_ref(&other.abs, m)
}
}
}
impl<'a, 'b> EqMod<&'b Integer, Natural> for &'a Integer {
fn eq_mod(self, other: &'b Integer, m: Natural) -> bool {
if self.sign == other.sign {
(&self.abs).eq_mod(&other.abs, m)
} else {
self.abs.pos_eq_neg_mod(&other.abs, m)
}
}
}
impl<'a, 'b, 'c> EqMod<&'b Integer, &'c Natural> for &'a Integer {
fn eq_mod(self, other: &'b Integer, m: &'c Natural) -> bool {
if self.sign == other.sign {
(&self.abs).eq_mod(&other.abs, m)
} else {
self.abs.pos_eq_neg_mod_ref(&other.abs, m)
}
}
}