1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
use crate::integer::Integer;
use crate::natural::arithmetic::divisible_by_power_of_2::limbs_divisible_by_power_of_2;
use crate::natural::InnerNatural::{Large, Small};
use crate::natural::Natural;
use crate::platform::Limb;
use core::cmp::Ordering;
use malachite_base::num::arithmetic::traits::EqModPowerOf2;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::conversion::traits::ExactFrom;
// Interpreting a slice of `Limb`s as the limbs (in ascending order) of a `Natural`, returns whether
// the negative of the `Natural` is equivalent to a limb mod two to the power of `pow`; that is,
// whether the `pow` least-significant bits of the negative of the `Natural` and the limb are equal.
//
// This function assumes that `limbs` has length at least 2 and the last (most significant) limb is
// nonzero.
//
// # Worst-case complexity
// $T(n) = O(n)$
//
// $M(n) = O(1)$
//
// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
pub_test! {limbs_eq_mod_power_of_2_neg_limb(xs: &[Limb], y: Limb, pow: u64) -> bool {
if y == 0 {
return limbs_divisible_by_power_of_2(xs, pow);
}
let i = usize::exact_from(pow >> Limb::LOG_WIDTH);
match i.cmp(&xs.len()) {
Ordering::Greater => false,
Ordering::Equal => {
if pow & Limb::WIDTH_MASK == 0 {
// Check whether the sum of X and y is 0 mod B ^ xs.len().
let mut carry = y;
for &x in xs {
let sum = x.wrapping_add(carry);
if sum != 0 {
return false;
}
carry = 1;
}
true
} else {
false
}
}
Ordering::Less => {
if i == 0 {
xs[0].eq_mod_power_of_2(y.wrapping_neg(), pow)
} else {
xs[0] == y.wrapping_neg()
&& xs[1..i].iter().all(|&x| x == Limb::MAX)
&& xs[i].eq_mod_power_of_2(Limb::MAX, pow & Limb::WIDTH_MASK)
}
}
}
}}
fn limbs_eq_mod_power_of_2_neg_pos_greater(xs: &[Limb], ys: &[Limb], pow: u64) -> bool {
let xs_len = xs.len();
let i = usize::exact_from(pow >> Limb::LOG_WIDTH);
let small_pow = pow & Limb::WIDTH_MASK;
if i > xs_len || i == xs_len && small_pow != 0 {
false
} else {
let ys_len = ys.len();
let mut y_nonzero_seen = false;
for j in 0..i {
let y = if j >= ys_len {
Limb::MAX
} else if y_nonzero_seen {
!ys[j]
} else if ys[j] == 0 {
0
} else {
y_nonzero_seen = true;
ys[j].wrapping_neg()
};
if xs[j] != y {
return false;
}
}
if small_pow == 0 {
true
} else {
// i < xs_len
let y = if i >= ys_len {
Limb::MAX
} else if y_nonzero_seen {
!ys[i]
} else {
ys[i].wrapping_neg()
};
xs[i].eq_mod_power_of_2(y, small_pow)
}
}
}
// Interpreting two slices of `Limb`s as the limbs (in ascending order) of two `Natural`s, returns
// whether the first `Natural` and the negative of the second natural (equivalently, the negative of
// the first `Natural` and the second `Natural`) are equivalent mod two to the power of `pow`; that
// is, whether their `pow` least-significant bits are equal.
//
// This function assumes that neither slice is empty and their last elements are nonzero.
//
// # Worst-case complexity
// $T(n) = O(n)$
//
// $M(n) = O(1)$
//
// where $T$ is time, $M$ is additional memory, and $n$ is `max(xs.len(), ys.len())`.
//
// This is equivalent to `mpz_congruent_2exp_p` from `mpz/cong_2exp.c`, GMP 6.2.1, where `a` is
// negative and `c` is positive.
pub_test! {limbs_eq_mod_power_of_2_neg_pos(xs: &[Limb], ys: &[Limb], pow: u64) -> bool {
if xs.len() >= ys.len() {
limbs_eq_mod_power_of_2_neg_pos_greater(xs, ys, pow)
} else {
limbs_eq_mod_power_of_2_neg_pos_greater(ys, xs, pow)
}
}}
impl Natural {
fn eq_mod_power_of_2_neg_limb(&self, other: Limb, pow: u64) -> bool {
match *self {
Natural(Small(ref small)) => {
pow <= Limb::WIDTH && small.wrapping_neg().eq_mod_power_of_2(other, pow)
}
Natural(Large(ref limbs)) => limbs_eq_mod_power_of_2_neg_limb(limbs, other, pow),
}
}
fn eq_mod_power_of_2_neg_pos(&self, other: &Natural, pow: u64) -> bool {
match (self, other) {
(_, &Natural(Small(y))) => self.eq_mod_power_of_2_neg_limb(y, pow),
(&Natural(Small(x)), _) => other.eq_mod_power_of_2_neg_limb(x, pow),
(&Natural(Large(ref xs)), &Natural(Large(ref ys))) => {
limbs_eq_mod_power_of_2_neg_pos(xs, ys, pow)
}
}
}
}
impl<'a, 'b> EqModPowerOf2<&'b Integer> for &'a Integer {
/// Returns whether one [`Integer`] is equal to another modulo $2^k$; that is, whether their $k$
/// least-significant bits (in two's complement) are equal.
///
/// $f(x, y, k) = (x \equiv y \mod 2^k)$.
///
/// $f(x, y, k) = (\exists n \in \Z : x - y = n2^k)$.
///
/// # Worst-case complexity
/// $T(n) = O(n)$
///
/// $M(n) = O(1)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `min(pow, self.significant_bits(),
/// other.significant_bits())`.
///
/// # Examples
/// ```
/// use malachite_base::num::arithmetic::traits::EqModPowerOf2;
/// use malachite_base::num::basic::traits::Zero;
/// use malachite_nz::integer::Integer;
///
/// assert_eq!(Integer::ZERO.eq_mod_power_of_2(&Integer::from(-256), 8), true);
/// assert_eq!(Integer::from(-0b1101).eq_mod_power_of_2(&Integer::from(0b11011), 3), true);
/// assert_eq!(Integer::from(-0b1101).eq_mod_power_of_2(&Integer::from(0b11011), 4), false);
/// ```
fn eq_mod_power_of_2(self, other: &'b Integer, pow: u64) -> bool {
if self.sign == other.sign {
self.abs.eq_mod_power_of_2(&other.abs, pow)
} else {
self.abs.eq_mod_power_of_2_neg_pos(&other.abs, pow)
}
}
}