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

use crate::natural::Natural;
use malachite_base::num::arithmetic::traits::{
    ModPowerOf2Shl, ModPowerOf2ShlAssign, ModPowerOf2Shr, ModPowerOf2ShrAssign, UnsignedAbs,
};
use malachite_base::num::basic::signeds::PrimitiveSigned;
use std::ops::{Shr, ShrAssign};

fn mod_power_of_2_shr_ref<'a, U, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
    x: &'a Natural,
    bits: S,
    pow: u64,
) -> Natural
where
    &'a Natural: ModPowerOf2Shl<U, Output = Natural> + Shr<U, Output = Natural>,
{
    if bits >= S::ZERO {
        x >> bits.unsigned_abs()
    } else {
        x.mod_power_of_2_shl(bits.unsigned_abs(), pow)
    }
}

fn mod_power_of_2_shr_assign<U, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
    x: &mut Natural,
    bits: S,
    pow: u64,
) where
    Natural: ModPowerOf2ShlAssign<U> + ShrAssign<U>,
{
    if bits >= S::ZERO {
        *x >>= bits.unsigned_abs();
    } else {
        x.mod_power_of_2_shl_assign(bits.unsigned_abs(), pow);
    }
}

macro_rules! impl_mod_power_of_2_shr_signed {
    ($t:ident) => {
        impl ModPowerOf2Shr<$t> for Natural {
            type Output = Natural;

            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$. Assumes the
            /// input is already reduced modulo $2^k$. The [`Natural`] is taken by value.
            ///
            /// $f(x, n, k) = y$, where $x, y < 2^k$ and
            /// $\lfloor 2^{-n}x \rfloor \equiv y \mod 2^k$.
            ///
            /// # Worst-case complexity
            /// $T(n) = O(n)$
            ///
            /// $M(n) = O(n)$
            ///
            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
            ///
            /// # Examples
            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr).
            #[inline]
            fn mod_power_of_2_shr(mut self, bits: $t, pow: u64) -> Natural {
                self.mod_power_of_2_shr_assign(bits, pow);
                self
            }
        }

        impl<'a> ModPowerOf2Shr<$t> for &'a Natural {
            type Output = Natural;

            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$. Assumes the
            /// input is already reduced modulo $2^k$. The [`Natural`] is taken by reference.
            ///
            /// $f(x, n, k) = y$, where $x, y < 2^k$ and
            /// $\lfloor 2^{-n}x \rfloor \equiv y \mod 2^k$.
            ///
            /// # Worst-case complexity
            /// $T(n) = O(n)$
            ///
            /// $M(n) = O(n)$
            ///
            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
            ///
            /// # Examples
            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr).
            #[inline]
            fn mod_power_of_2_shr(self, bits: $t, pow: u64) -> Natural {
                mod_power_of_2_shr_ref(self, bits, pow)
            }
        }

        impl ModPowerOf2ShrAssign<$t> for Natural {
            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$, in place.
            /// Assumes the input is already reduced modulo $2^k$.
            ///
            /// $x \gets y$, where $x, y < 2^k$ and $\lfloor 2^{-n}x \rfloor \equiv y \mod 2^k$.
            ///
            /// # Worst-case complexity
            /// $T(n) = O(n)$
            ///
            /// $M(n) = O(n)$
            ///
            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
            ///
            /// # Examples
            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr_assign).
            #[inline]
            fn mod_power_of_2_shr_assign(&mut self, bits: $t, pow: u64) {
                mod_power_of_2_shr_assign(self, bits, pow);
            }
        }
    };
}
apply_to_signeds!(impl_mod_power_of_2_shr_signed);