Struct malachite_nz::natural::Natural

pub struct Natural(/* private fields */);

A natural (non-negative) integer.

Any Natural small enough to fit into a Limb is represented inline. Only Naturals outside this range incur the costs of heap-allocation. Here’s a diagram of a slice of Naturals (using 32-bit limbs) containing the first 8 values of Sylvester’s sequence:

Implementations

impl Natural

pub fn approx_log(&self) -> f64

Calculates the approximate natural logarithm of a nonzero Natural.

$f(x) = (1+\epsilon)(\log x)$, where $|\epsilon| < 2^{-52}.$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::float::NiceFloat;
use malachite_nz::natural::Natural;

assert_eq!(NiceFloat(Natural::from(10u32).approx_log()), NiceFloat(2.3025850929940455));
assert_eq!(
    NiceFloat(Natural::from(10u32).pow(10000).approx_log()),
    NiceFloat(23025.850929940454)
);

This is equivalent to fmpz_dlog from fmpz/dlog.c, FLINT 2.7.1.

impl Natural

pub fn cmp_normalized(&self, other: &Natural) -> Ordering

Returns a result of a comparison between two Naturals as if each had been multiplied by some power of 2 to bring it into the interval $[1, 2)$.

That is, the comparison is equivalent to a comparison between $f(x)$ and $f(y)$, where $$ f(n) = n2^{\lfloor\log_2 n \rfloor}. $$

The multiplication is not actually performed.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Panics

Panics if either argument is zero.

Examples

use malachite_nz::natural::Natural;
use std::cmp::Ordering;

// 1 == 1.0 * 2^0, 4 == 1.0 * 2^2
// 1.0 == 1.0
assert_eq!(Natural::from(1u32).cmp_normalized(&Natural::from(4u32)), Ordering::Equal);

// 5 == 1.25 * 2^2, 6 == 1.5 * 2^2
// 1.25 < 1.5
assert_eq!(Natural::from(5u32).cmp_normalized(&Natural::from(6u32)), Ordering::Less);

// 3 == 1.5 * 2^1, 17 == 1.0625 * 2^4
// 1.5 > 1.0625
assert_eq!(Natural::from(3u32).cmp_normalized(&Natural::from(17u32)), Ordering::Greater);

// 9 == 1.125 * 2^3, 36 == 1.125 * 2^5
// 1.125 == 1.125
assert_eq!(Natural::from(9u32).cmp_normalized(&Natural::from(36u32)), Ordering::Equal);

impl Natural

pub fn from_limbs_asc(xs: &[Limb]) -> Natural

Converts a slice of limbs to a Natural.

The limbs are in ascending order, so that less-significant limbs have lower indices in the input slice.

This function borrows the limbs. If taking ownership of limbs is possible, from_owned_limbs_asc is more efficient.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.len().

This function is more efficient than from_limbs_desc.

Examples

use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert_eq!(Natural::from_limbs_asc(&[]), 0);
    assert_eq!(Natural::from_limbs_asc(&[123]), 123);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from_limbs_asc(&[3567587328, 232]), 1000000000000u64);
}

pub fn from_limbs_desc(xs: &[Limb]) -> Natural

Converts a slice of limbs to a Natural.

The limbs in descending order, so that less-significant limbs have higher indices in the input slice.

This function borrows the limbs. If taking ownership of the limbs is possible, from_owned_limbs_desc is more efficient.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.len().

This function is less efficient than from_limbs_asc.

Examples

use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert_eq!(Natural::from_limbs_desc(&[]), 0);
    assert_eq!(Natural::from_limbs_desc(&[123]), 123);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from_limbs_desc(&[232, 3567587328]), 1000000000000u64);
}

pub fn from_owned_limbs_asc(xs: Vec<Limb>) -> Natural

Converts a Vec of limbs to a Natural.

The limbs are in ascending order, so that less-significant limbs have lower indices in the input Vec.

This function takes ownership of the limbs. If it’s necessary to borrow the limbs instead, use from_limbs_asc.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.len().

This function is more efficient than from_limbs_desc.

Examples

use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert_eq!(Natural::from_owned_limbs_asc(vec![]), 0);
    assert_eq!(Natural::from_owned_limbs_asc(vec![123]), 123);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from_owned_limbs_asc(vec![3567587328, 232]), 1000000000000u64);
}

pub fn from_owned_limbs_desc(xs: Vec<Limb>) -> Natural

Converts a Vec of limbs to a Natural.

The limbs are in descending order, so that less-significant limbs have higher indices in the input Vec.

This function takes ownership of the limbs. If it’s necessary to borrow the limbs instead, use from_limbs_desc.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.len().

This function is less efficient than from_limbs_asc.

Examples

use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert_eq!(Natural::from_owned_limbs_desc(vec![]), 0);
    assert_eq!(Natural::from_owned_limbs_desc(vec![123]), 123);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from_owned_limbs_desc(vec![232, 3567587328]), 1000000000000u64);
}

impl Natural

pub const fn const_from(x: Limb) -> Natural

Converts a Limb to a Natural.

This function is const, so it may be used to define constants.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_nz::natural::Natural;

const TEN: Natural = Natural::const_from(10);
assert_eq!(TEN, 10);

impl Natural

pub fn limb_count(&self) -> u64

Returns the number of limbs of a Natural.

Zero has 0 limbs.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert_eq!(Natural::ZERO.limb_count(), 0);
    assert_eq!(Natural::from(123u32).limb_count(), 1);
    assert_eq!(Natural::from(10u32).pow(12).limb_count(), 2);
}

impl Natural

pub fn sci_mantissa_and_exponent_round<T: PrimitiveFloat>( &self, rm: RoundingMode ) -> Option<(T, u64, Ordering)>

Returns a Natural’s scientific mantissa and exponent, rounding according to the specified rounding mode. An Ordering is also returned, indicating whether the mantissa and exponent represent a value that is less than, equal to, or greater than the original value.

When $x$ is positive, we can write $x = 2^{e_s}m_s$, where $e_s$ is an integer and $m_s$ is a rational number with $1 \leq m_s < 2$. We represent the rational mantissa as a float. The conversion might not be exact, so we round to the nearest float using the provided rounding mode. If the rounding mode is Exact but the conversion is not exact, None is returned. $$ f(x, r) \approx \left (\frac{x}{2^{\lfloor \log_2 x \rfloor}}, \lfloor \log_2 x \rfloor\right ). $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::conversion::traits::SciMantissaAndExponent;
use malachite_base::num::float::NiceFloat;
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

let test = |n: Natural, rm: RoundingMode, out: Option<(f32, u64, Ordering)>| {
    assert_eq!(
        n.sci_mantissa_and_exponent_round(rm)
            .map(|(m, e, o)| (NiceFloat(m), e, o)),
        out.map(|(m, e, o)| (NiceFloat(m), e, o))
    );
};
test(Natural::from(3u32), RoundingMode::Floor, Some((1.5, 1, Ordering::Equal)));
test(Natural::from(3u32), RoundingMode::Down, Some((1.5, 1, Ordering::Equal)));
test(Natural::from(3u32), RoundingMode::Ceiling, Some((1.5, 1, Ordering::Equal)));
test(Natural::from(3u32), RoundingMode::Up, Some((1.5, 1, Ordering::Equal)));
test(Natural::from(3u32), RoundingMode::Nearest, Some((1.5, 1, Ordering::Equal)));
test(Natural::from(3u32), RoundingMode::Exact, Some((1.5, 1, Ordering::Equal)));

test(
    Natural::from(123u32),
    RoundingMode::Floor,
    Some((1.921875, 6, Ordering::Equal)),
);
test(
    Natural::from(123u32),
    RoundingMode::Down,
    Some((1.921875, 6, Ordering::Equal)),
);
test(
    Natural::from(123u32),
    RoundingMode::Ceiling,
    Some((1.921875, 6, Ordering::Equal)),
);
test(Natural::from(123u32), RoundingMode::Up, Some((1.921875, 6, Ordering::Equal)));
test(
    Natural::from(123u32),
    RoundingMode::Nearest,
    Some((1.921875, 6, Ordering::Equal)),
);
test(
    Natural::from(123u32),
    RoundingMode::Exact,
    Some((1.921875, 6, Ordering::Equal)),
);

test(
    Natural::from(1000000000u32),
    RoundingMode::Nearest,
    Some((1.8626451, 29, Ordering::Equal)),
);
test(
    Natural::from(10u32).pow(52),
    RoundingMode::Nearest,
    Some((1.670478, 172, Ordering::Greater)),
);

test(Natural::from(10u32).pow(52), RoundingMode::Exact, None);

pub fn from_sci_mantissa_and_exponent_round<T: PrimitiveFloat>( sci_mantissa: T, sci_exponent: u64, rm: RoundingMode ) -> Option<(Natural, Ordering)>

Constructs a Natural from its scientific mantissa and exponent, rounding according to the specified rounding mode. An Ordering is also returned, indicating whether the returned value is less than, equal to, or greater than the exact value represented by the mantissa and exponent.

When $x$ is positive, we can write $x = 2^{e_s}m_s$, where $e_s$ is an integer and $m_s$ is a rational number with $1 \leq m_s < 2$. Here, the rational mantissa is provided as a float. If the mantissa is outside the range $[1, 2)$, None is returned.

Some combinations of mantissas and exponents do not specify a Natural, in which case the resulting value is rounded to a Natural using the specified rounding mode. If the rounding mode is Exact but the input does not exactly specify a Natural, None is returned.

$$ f(x, r) \approx 2^{e_s}m_s. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is sci_exponent.

Panics

Panics if sci_mantissa is zero.

Examples

use malachite_base::num::conversion::traits::SciMantissaAndExponent;
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;
use std::str::FromStr;

let test = |
    mantissa: f32,
    exponent: u64,
    rm: RoundingMode,
    out: Option<(Natural, Ordering)>
| {
    assert_eq!(
        Natural::from_sci_mantissa_and_exponent_round(mantissa, exponent, rm),
        out
    );
};
test(1.5, 1, RoundingMode::Floor, Some((Natural::from(3u32), Ordering::Equal)));
test(1.5, 1, RoundingMode::Down, Some((Natural::from(3u32), Ordering::Equal)));
test(1.5, 1, RoundingMode::Ceiling, Some((Natural::from(3u32), Ordering::Equal)));
test(1.5, 1, RoundingMode::Up, Some((Natural::from(3u32), Ordering::Equal)));
test(1.5, 1, RoundingMode::Nearest, Some((Natural::from(3u32), Ordering::Equal)));
test(1.5, 1, RoundingMode::Exact, Some((Natural::from(3u32), Ordering::Equal)));

test(1.51, 1, RoundingMode::Floor, Some((Natural::from(3u32), Ordering::Less)));
test(1.51, 1, RoundingMode::Down, Some((Natural::from(3u32), Ordering::Less)));
test(1.51, 1, RoundingMode::Ceiling, Some((Natural::from(4u32), Ordering::Greater)));
test(1.51, 1, RoundingMode::Up, Some((Natural::from(4u32), Ordering::Greater)));
test(1.51, 1, RoundingMode::Nearest, Some((Natural::from(3u32), Ordering::Less)));
test(1.51, 1, RoundingMode::Exact, None);

test(
    1.670478,
    172,
    RoundingMode::Nearest,
    Some(
        (
            Natural::from_str("10000000254586612611935772707803116801852191350456320")
                .unwrap(),
            Ordering::Equal
        )
    ),
);

test(2.0, 1, RoundingMode::Floor, None);
test(10.0, 1, RoundingMode::Floor, None);
test(0.5, 1, RoundingMode::Floor, None);

impl Natural

pub fn to_limbs_asc(&self) -> Vec<Limb>

Returns the limbs of a Natural, in ascending order, so that less-significant limbs have lower indices in the output vector.

There are no trailing zero limbs.

This function borrows the Natural. If taking ownership is possible instead, into_limbs_asc is more efficient.

This function is more efficient than to_limbs_desc.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert!(Natural::ZERO.to_limbs_asc().is_empty());
    assert_eq!(Natural::from(123u32).to_limbs_asc(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from(10u32).pow(12).to_limbs_asc(), &[3567587328, 232]);
}

pub fn to_limbs_desc(&self) -> Vec<Limb>

Returns the limbs of a Natural in descending order, so that less-significant limbs have higher indices in the output vector.

There are no leading zero limbs.

This function borrows the Natural. If taking ownership is possible instead, into_limbs_desc is more efficient.

This function is less efficient than to_limbs_asc.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert!(Natural::ZERO.to_limbs_desc().is_empty());
    assert_eq!(Natural::from(123u32).to_limbs_desc(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from(10u32).pow(12).to_limbs_desc(), &[232, 3567587328]);
}

pub fn into_limbs_asc(self) -> Vec<Limb>

Returns the limbs of a Natural, in ascending order, so that less-significant limbs have lower indices in the output vector.

There are no trailing zero limbs.

This function takes ownership of the Natural. If it’s necessary to borrow instead, use to_limbs_asc.

This function is more efficient than into_limbs_desc.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert!(Natural::ZERO.into_limbs_asc().is_empty());
    assert_eq!(Natural::from(123u32).into_limbs_asc(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from(10u32).pow(12).into_limbs_asc(), &[3567587328, 232]);
}

pub fn into_limbs_desc(self) -> Vec<Limb>

Returns the limbs of a Natural, in descending order, so that less-significant limbs have higher indices in the output vector.

There are no leading zero limbs.

This function takes ownership of the Natural. If it’s necessary to borrow instead, use to_limbs_desc.

This function is less efficient than into_limbs_asc.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert!(Natural::ZERO.into_limbs_desc().is_empty());
    assert_eq!(Natural::from(123u32).into_limbs_desc(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from(10u32).pow(12).into_limbs_desc(), &[232, 3567587328]);
}

pub fn limbs(&self) -> LimbIterator<'_>

Returns a double-ended iterator over the limbs of a Natural.

The forward order is ascending, so that less-significant limbs appear first. There are no trailing zero limbs going forward, or leading zeros going backward.

If it’s necessary to get a Vec of all the limbs, consider using to_limbs_asc, to_limbs_desc, into_limbs_asc, or into_limbs_desc instead.

Worst-case complexity

Constant time and additional memory.

Examples

use itertools::Itertools;
use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;

if Limb::WIDTH == u32::WIDTH {
    assert!(Natural::ZERO.limbs().next().is_none());
    assert_eq!(Natural::from(123u32).limbs().collect_vec(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(Natural::from(10u32).pow(12).limbs().collect_vec(), &[3567587328, 232]);

    assert!(Natural::ZERO.limbs().rev().next().is_none());
    assert_eq!(Natural::from(123u32).limbs().rev().collect_vec(), &[123]);
    // 10^12 = 232 * 2^32 + 3567587328
    assert_eq!(
        Natural::from(10u32).pow(12).limbs().rev().collect_vec(),
        &[232, 3567587328]
    );
}

impl Natural

pub fn trailing_zeros(&self) -> Option<u64>

Returns the number of trailing zeros in the binary expansion of a Natural (equivalently, the multiplicity of 2 in its prime factorization), or None is the Natural is 0.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.trailing_zeros(), None);
assert_eq!(Natural::from(3u32).trailing_zeros(), Some(0));
assert_eq!(Natural::from(72u32).trailing_zeros(), Some(3));
assert_eq!(Natural::from(100u32).trailing_zeros(), Some(2));
assert_eq!(Natural::from(10u32).pow(12).trailing_zeros(), Some(12));

Trait Implementations

impl<'a, 'b> Add<&'a Natural> for &'b Natural

fn add(self, other: &'a Natural) -> Natural

Adds two Naturals, taking both by reference.

$$ f(x, y) = x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::ZERO + &Natural::from(123u32), 123);
assert_eq!(&Natural::from(123u32) + &Natural::ZERO, 123);
assert_eq!(&Natural::from(123u32) + &Natural::from(456u32), 579);
assert_eq!(
    &Natural::from(10u32).pow(12) + &(Natural::from(10u32).pow(12) << 1),
    3000000000000u64
);

type Output = Natural

The resulting type after applying the + operator.

impl<'a> Add<&'a Natural> for Natural

fn add(self, other: &'a Natural) -> Natural

Adds two Naturals, taking the first by reference and the second by value.

$$ f(x, y) = x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO + &Natural::from(123u32), 123);
assert_eq!(Natural::from(123u32) + &Natural::ZERO, 123);
assert_eq!(Natural::from(123u32) + &Natural::from(456u32), 579);
assert_eq!(
    Natural::from(10u32).pow(12) + &(Natural::from(10u32).pow(12) << 1),
    3000000000000u64
);

type Output = Natural

The resulting type after applying the + operator.

impl<'a> Add<Natural> for &'a Natural

fn add(self, other: Natural) -> Natural

Adds two Naturals, taking the first by value and the second by reference.

$$ f(x, y) = x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::ZERO + Natural::from(123u32), 123);
assert_eq!(&Natural::from(123u32) + Natural::ZERO, 123);
assert_eq!(&Natural::from(123u32) + Natural::from(456u32), 579);
assert_eq!(
    &Natural::from(10u32).pow(12) + (Natural::from(10u32).pow(12) << 1),
    3000000000000u64
);

type Output = Natural

The resulting type after applying the + operator.

impl Add for Natural

fn add(self, other: Natural) -> Natural

Adds two Naturals, taking both by value.

$$ f(x, y) = x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$ (only if the underlying Vec needs to reallocate)

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO + Natural::from(123u32), 123);
assert_eq!(Natural::from(123u32) + Natural::ZERO, 123);
assert_eq!(Natural::from(123u32) + Natural::from(456u32), 579);
assert_eq!(
    Natural::from(10u32).pow(12) + (Natural::from(10u32).pow(12) << 1),
    3000000000000u64
);

type Output = Natural

The resulting type after applying the + operator.

impl<'a> AddAssign<&'a Natural> for Natural

fn add_assign(&mut self, other: &'a Natural)

Adds a Natural to a Natural in place, taking the Natural on the right-hand side by reference.

$$ x \gets x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x += &Natural::from(10u32).pow(12);
x += &(Natural::from(10u32).pow(12) * Natural::from(2u32));
x += &(Natural::from(10u32).pow(12) * Natural::from(3u32));
x += &(Natural::from(10u32).pow(12) * Natural::from(4u32));
assert_eq!(x, 10000000000000u64);

impl AddAssign for Natural

fn add_assign(&mut self, other: Natural)

Adds a Natural to a Natural in place, taking the Natural on the right-hand side by value.

$$ x \gets x + y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$ (only if the underlying Vec needs to reallocate)

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x += Natural::from(10u32).pow(12);
x += Natural::from(10u32).pow(12) * Natural::from(2u32);
x += Natural::from(10u32).pow(12) * Natural::from(3u32);
x += Natural::from(10u32).pow(12) * Natural::from(4u32);
assert_eq!(x, 10000000000000u64);

impl<'a> AddMul<&'a Natural> for Natural

fn add_mul(self, y: &'a Natural, z: Natural) -> Natural

Adds a Natural and the product of two other Naturals, taking the first and third by value and the second by reference.

$f(x, y, z) = x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMul, Pow};
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(10u32).add_mul(&Natural::from(3u32), Natural::from(4u32)), 22);
assert_eq!(
    Natural::from(10u32).pow(12)
        .add_mul(&Natural::from(0x10000u32), Natural::from(10u32).pow(12)),
    65537000000000000u64
);

type Output = Natural

impl<'a, 'b, 'c> AddMul<&'a Natural, &'b Natural> for &'c Natural

fn add_mul(self, y: &'a Natural, z: &'b Natural) -> Natural

Adds a Natural and the product of two other Naturals, taking all three by reference.

$f(x, y, z) = x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n, m) = O(m + n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMul, Pow};
use malachite_nz::natural::Natural;

assert_eq!((&Natural::from(10u32)).add_mul(&Natural::from(3u32), &Natural::from(4u32)), 22);
assert_eq!(
    (&Natural::from(10u32).pow(12))
        .add_mul(&Natural::from(0x10000u32), &Natural::from(10u32).pow(12)),
    65537000000000000u64
);

type Output = Natural

impl<'a, 'b> AddMul<&'a Natural, &'b Natural> for Natural

fn add_mul(self, y: &'a Natural, z: &'b Natural) -> Natural

Adds a Natural and the product of two other Naturals, taking the first by value and the second and third by reference.

$f(x, y, z) = x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMul, Pow};
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(10u32).add_mul(&Natural::from(3u32), &Natural::from(4u32)), 22);
assert_eq!(
    Natural::from(10u32).pow(12)
        .add_mul(&Natural::from(0x10000u32), &Natural::from(10u32).pow(12)),
    65537000000000000u64
);

type Output = Natural

impl<'a> AddMul<Natural, &'a Natural> for Natural

fn add_mul(self, y: Natural, z: &'a Natural) -> Natural

Adds a Natural and the product of two other Naturals, taking the first two by value and the third by reference.

$f(x, y, z) = x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMul, Pow};
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(10u32).add_mul(Natural::from(3u32), &Natural::from(4u32)), 22);
assert_eq!(
    Natural::from(10u32).pow(12)
        .add_mul(Natural::from(0x10000u32), &Natural::from(10u32).pow(12)),
    65537000000000000u64
);

type Output = Natural

impl AddMul for Natural

fn add_mul(self, y: Natural, z: Natural) -> Natural

Adds a Natural and the product of two other Naturals, taking all three by value.

$f(x, y, z) = x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMul, Pow};
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(10u32).add_mul(Natural::from(3u32), Natural::from(4u32)), 22);
assert_eq!(
    Natural::from(10u32).pow(12)
        .add_mul(Natural::from(0x10000u32), Natural::from(10u32).pow(12)),
    65537000000000000u64
);

type Output = Natural

impl<'a> AddMulAssign<&'a Natural> for Natural

fn add_mul_assign(&mut self, y: &'a Natural, z: Natural)

Adds the product of two other Naturals to a Natural in place, taking the first Natural on the right-hand side by reference and the second by value.

$x \gets x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMulAssign, Pow};
use malachite_nz::natural::Natural;

let mut x = Natural::from(10u32);
x.add_mul_assign(&Natural::from(3u32), Natural::from(4u32));
assert_eq!(x, 22);

let mut x = Natural::from(10u32).pow(12);
x.add_mul_assign(&Natural::from(0x10000u32), Natural::from(10u32).pow(12));
assert_eq!(x, 65537000000000000u64);

impl<'a, 'b> AddMulAssign<&'a Natural, &'b Natural> for Natural

fn add_mul_assign(&mut self, y: &'a Natural, z: &'b Natural)

Adds the product of two other Naturals to a Natural in place, taking both Naturals on the right-hand side by reference.

$x \gets x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMulAssign, Pow};
use malachite_nz::natural::Natural;

let mut x = Natural::from(10u32);
x.add_mul_assign(&Natural::from(3u32), &Natural::from(4u32));
assert_eq!(x, 22);

let mut x = Natural::from(10u32).pow(12);
x.add_mul_assign(&Natural::from(0x10000u32), &Natural::from(10u32).pow(12));
assert_eq!(x, 65537000000000000u64);

impl<'a> AddMulAssign<Natural, &'a Natural> for Natural

fn add_mul_assign(&mut self, y: Natural, z: &'a Natural)

Adds the product of two other Naturals to a Natural in place, taking the first Natural on the right-hand side by value and the second by reference.

$x \gets x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMulAssign, Pow};
use malachite_nz::natural::Natural;

let mut x = Natural::from(10u32);
x.add_mul_assign(Natural::from(3u32), &Natural::from(4u32));
assert_eq!(x, 22);

let mut x = Natural::from(10u32).pow(12);
x.add_mul_assign(Natural::from(0x10000u32), &Natural::from(10u32).pow(12));
assert_eq!(x, 65537000000000000u64);

impl AddMulAssign for Natural

fn add_mul_assign(&mut self, y: Natural, z: Natural)

Adds the product of two other Naturals to a Natural in place, taking both Naturals on the right-hand side by value.

$x \gets x + yz$.

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{AddMulAssign, Pow};
use malachite_nz::natural::Natural;

let mut x = Natural::from(10u32);
x.add_mul_assign(Natural::from(3u32), Natural::from(4u32));
assert_eq!(x, 22);

let mut x = Natural::from(10u32).pow(12);
x.add_mul_assign(Natural::from(0x10000u32), Natural::from(10u32).pow(12));
assert_eq!(x, 65537000000000000u64);

impl Binary for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Converts a Natural to a binary String.

Using the # format flag prepends "0b" to the string.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToBinaryString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::ZERO.to_binary_string(), "0");
assert_eq!(Natural::from(123u32).to_binary_string(), "1111011");
assert_eq!(
    Natural::from_str("1000000000000").unwrap().to_binary_string(),
    "1110100011010100101001010001000000000000"
);
assert_eq!(format!("{:011b}", Natural::from(123u32)), "00001111011");

assert_eq!(format!("{:#b}", Natural::ZERO), "0b0");
assert_eq!(format!("{:#b}", Natural::from(123u32)), "0b1111011");
assert_eq!(
    format!("{:#b}", Natural::from_str("1000000000000").unwrap()),
    "0b1110100011010100101001010001000000000000"
);
assert_eq!(format!("{:#011b}", Natural::from(123u32)), "0b001111011");

impl<'a> BinomialCoefficient<&'a Natural> for Natural

fn binomial_coefficient(n: &'a Natural, k: &'a Natural) -> Natural

Computes the binomial coefficient of two Naturals, taking both by reference.

$$ f(n, k) =binom{n}{k} =frac{n!}{k!(n-k)!}. $$

Worst-case complexity

TODO

Examples

use malachite_base::num::arithmetic::traits::BinomialCoefficient;
use malachite_nz::natural::Natural;

assert_eq!(Natural::binomial_coefficient(&Natural::from(4u32), &Natural::from(0u32)), 1);
assert_eq!(Natural::binomial_coefficient(&Natural::from(4u32), &Natural::from(1u32)), 4);
assert_eq!(Natural::binomial_coefficient(&Natural::from(4u32), &Natural::from(2u32)), 6);
assert_eq!(Natural::binomial_coefficient(&Natural::from(4u32), &Natural::from(3u32)), 4);
assert_eq!(Natural::binomial_coefficient(&Natural::from(4u32), &Natural::from(4u32)), 1);
assert_eq!(
    Natural::binomial_coefficient(&Natural::from(10u32), &Natural::from(5u32)),
    252
);
assert_eq!(
    Natural::binomial_coefficient(&Natural::from(100u32), &Natural::from(50u32))
        .to_string(),
    "100891344545564193334812497256"
);

impl BinomialCoefficient for Natural

fn binomial_coefficient(n: Natural, k: Natural) -> Natural

Computes the binomial coefficient of two Naturals, taking both by value.

$$ f(n, k) =binom{n}{k} =frac{n!}{k!(n-k)!}. $$

Worst-case complexity

TODO

Examples

use malachite_base::num::arithmetic::traits::BinomialCoefficient;
use malachite_nz::natural::Natural;

assert_eq!(Natural::binomial_coefficient(Natural::from(4u32), Natural::from(0u32)), 1);
assert_eq!(Natural::binomial_coefficient(Natural::from(4u32), Natural::from(1u32)), 4);
assert_eq!(Natural::binomial_coefficient(Natural::from(4u32), Natural::from(2u32)), 6);
assert_eq!(Natural::binomial_coefficient(Natural::from(4u32), Natural::from(3u32)), 4);
assert_eq!(Natural::binomial_coefficient(Natural::from(4u32), Natural::from(4u32)), 1);
assert_eq!(Natural::binomial_coefficient(Natural::from(10u32), Natural::from(5u32)), 252);
assert_eq!(
    Natural::binomial_coefficient(Natural::from(100u32), Natural::from(50u32)).to_string(),
    "100891344545564193334812497256"
);

impl BitAccess for Natural

Provides functions for accessing and modifying the $i$th bit of a Natural, or the coefficient of $2^i$ in its binary expansion.

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_base::num::logic::traits::BitAccess;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x.assign_bit(2, true);
x.assign_bit(5, true);
x.assign_bit(6, true);
assert_eq!(x, 100);
x.assign_bit(2, false);
x.assign_bit(5, false);
x.assign_bit(6, false);
assert_eq!(x, 0);

let mut x = Natural::ZERO;
x.flip_bit(10);
assert_eq!(x, 1024);
x.flip_bit(10);
assert_eq!(x, 0);

fn get_bit(&self, index: u64) -> bool

Determines whether the $i$th bit of a Natural, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the Natural’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::logic::traits::BitAccess;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32).get_bit(2), false);
assert_eq!(Natural::from(123u32).get_bit(3), true);
assert_eq!(Natural::from(123u32).get_bit(100), false);
assert_eq!(Natural::from(10u32).pow(12).get_bit(12), true);
assert_eq!(Natural::from(10u32).pow(12).get_bit(100), false);

fn set_bit(&mut self, index: u64)

Sets the $i$th bit of a Natural, or the coefficient of $2^i$ in its binary expansion, to 1.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is index.

Examples

use malachite_base::num::logic::traits::BitAccess;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x.set_bit(2);
x.set_bit(5);
x.set_bit(6);
assert_eq!(x, 100);

fn clear_bit(&mut self, index: u64)

Sets the $i$th bit of a Natural, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the Natural’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is index.

Examples

use malachite_base::num::logic::traits::BitAccess;
use malachite_nz::natural::Natural;

let mut x = Natural::from(0x7fu32);
x.clear_bit(0);
x.clear_bit(1);
x.clear_bit(3);
x.clear_bit(4);
assert_eq!(x, 100);

fn assign_bit(&mut self, index: u64, bit: bool)

Sets the bit at index to whichever value bit is.

fn flip_bit(&mut self, index: u64)

Sets the bit at index to the opposite of its original value.

impl<'a, 'b> BitAnd<&'a Natural> for &'b Natural

fn bitand(self, other: &'a Natural) -> Natural

Takes the bitwise and of two Naturals, taking both by reference.

$$ f(x, y) = x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) & &Natural::from(456u32), 72);
assert_eq!(
    &Natural::from(10u32).pow(12) & &(Natural::from(10u32).pow(12) - Natural::ONE),
    999999995904u64
);

type Output = Natural

The resulting type after applying the & operator.

impl<'a> BitAnd<&'a Natural> for Natural

fn bitand(self, other: &'a Natural) -> Natural

Takes the bitwise and of two Naturals, taking the first by value and the second by reference.

$$ f(x, y) = x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) & &Natural::from(456u32), 72);
assert_eq!(
    Natural::from(10u32).pow(12) & &(Natural::from(10u32).pow(12) - Natural::ONE),
    999999995904u64
);

type Output = Natural

The resulting type after applying the & operator.

impl<'a> BitAnd<Natural> for &'a Natural

fn bitand(self, other: Natural) -> Natural

Takes the bitwise and of two Naturals, taking the first by reference and the seocnd by value.

$$ f(x, y) = x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) & Natural::from(456u32), 72);
assert_eq!(
    &Natural::from(10u32).pow(12) & (Natural::from(10u32).pow(12) - Natural::ONE),
    999999995904u64
);

type Output = Natural

The resulting type after applying the & operator.

impl BitAnd for Natural

fn bitand(self, other: Natural) -> Natural

Takes the bitwise and of two Naturals, taking both by value.

$$ f(x, y) = x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) & Natural::from(456u32), 72);
assert_eq!(
    Natural::from(10u32).pow(12) & (Natural::from(10u32).pow(12) - Natural::ONE),
    999999995904u64
);

type Output = Natural

The resulting type after applying the & operator.

impl<'a> BitAndAssign<&'a Natural> for Natural

fn bitand_assign(&mut self, other: &'a Natural)

Bitwise-ands a Natural with another Natural in place, taking the Natural on the right-hand side by reference.

$$ x \gets x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_nz::natural::Natural;

let mut x = Natural::from(u32::MAX);
x &= &Natural::from(0xf0ffffffu32);
x &= &Natural::from(0xfff0_ffffu32);
x &= &Natural::from(0xfffff0ffu32);
x &= &Natural::from(0xfffffff0u32);
assert_eq!(x, 0xf0f0_f0f0u32);

impl BitAndAssign for Natural

fn bitand_assign(&mut self, other: Natural)

Bitwise-ands a Natural with another Natural in place, taking the Natural on the right-hand side by value.

$$ x \gets x \wedge y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_nz::natural::Natural;

let mut x = Natural::from(u32::MAX);
x &= Natural::from(0xf0ffffffu32);
x &= Natural::from(0xfff0_ffffu32);
x &= Natural::from(0xfffff0ffu32);
x &= Natural::from(0xfffffff0u32);
assert_eq!(x, 0xf0f0_f0f0u32);

impl BitBlockAccess for Natural

fn get_bits(&self, start: u64, end: u64) -> Natural

Extracts a block of adjacent bits from a Natural, taking the Natural by reference.

The first index is start and last index is end - 1.

Let $n$ be self, and let $p$ and $q$ be start and end, respectively.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $$ f(n, p, q) = \sum_{i=p}^{q-1} 2^{b_{i-p}}. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if start > end.

Examples

use malachite_base::num::logic::traits::BitBlockAccess;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits(16, 48), 0xef011234u32);
assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits(4, 16), 0x567u32);
assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits(0, 100), 0xabcdef0112345678u64);
assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits(10, 10), 0);

fn get_bits_owned(self, start: u64, end: u64) -> Natural

Extracts a block of adjacent bits from a Natural, taking the Natural by value.

The first index is start and last index is end - 1.

Let $n$ be self, and let $p$ and $q$ be start and end, respectively.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $$ f(n, p, q) = \sum_{i=p}^{q-1} 2^{b_{i-p}}. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if start > end.

Examples

use malachite_base::num::logic::traits::BitBlockAccess;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits_owned(16, 48), 0xef011234u32);
assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits_owned(4, 16), 0x567u32);
assert_eq!(
    Natural::from(0xabcdef0112345678u64).get_bits_owned(0, 100),
    0xabcdef0112345678u64
);
assert_eq!(Natural::from(0xabcdef0112345678u64).get_bits_owned(10, 10), 0);

fn assign_bits(&mut self, start: u64, end: u64, bits: &Natural)

Replaces a block of adjacent bits in a Natural with other bits.

The least-significant end - start bits of bits are assigned to bits start through end - 1, inclusive, of self.

Let $n$ be self and let $m$ be bits, and let $p$ and $q$ be start and end, respectively.

If bits has fewer bits than end - start, the high bits are interpreted as 0. Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Let $$ m = \sum_{i=0}^k 2^{d_i}, $$ where for all $i$, $d_i\in \{0, 1\}$. Also, let $p, q \in \mathbb{N}$, and let $W$ be max(self.significant_bits(), end + 1).

Then $$ n \gets \sum_{i=0}^{W-1} 2^{c_i}, $$ where $$ \{c_0, c_1, c_2, \ldots, c_ {W-1}\} = \{b_0, b_1, b_2, \ldots, b_{p-1}, d_0, d_1, \ldots, d_{p-q-1}, b_q, \ldots, b_ {W-1}\}. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is end.

Panics

Panics if start > end.

Examples

use malachite_base::num::logic::traits::BitBlockAccess;
use malachite_nz::natural::Natural;

let mut n = Natural::from(123u32);
n.assign_bits(5, 7, &Natural::from(456u32));
assert_eq!(n, 27);

let mut n = Natural::from(123u32);
n.assign_bits(64, 128, &Natural::from(456u32));
assert_eq!(n.to_string(), "8411715297611555537019");

let mut n = Natural::from(123u32);
n.assign_bits(80, 100, &Natural::from(456u32));
assert_eq!(n.to_string(), "551270173744270903666016379");

type Bits = Natural

impl BitConvertible for Natural

fn to_bits_asc(&self) -> Vec<bool>

Returns a Vec containing the bits of a Natural in ascending order: least- to most-significant.

If the number is 0, the Vec is empty; otherwise, it ends with true.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::logic::traits::BitConvertible;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert!(Natural::ZERO.to_bits_asc().is_empty());
// 105 = 1101001b
assert_eq!(
    Natural::from(105u32).to_bits_asc(),
    &[true, false, false, true, false, true, true]
);

fn to_bits_desc(&self) -> Vec<bool>

Returns a Vec containing the bits of a Natural in descending order: most- to least-significant.

If the number is 0, the Vec is empty; otherwise, it begins with true.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::logic::traits::BitConvertible;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert!(Natural::ZERO.to_bits_desc().is_empty());
// 105 = 1101001b
assert_eq!(
    Natural::from(105u32).to_bits_desc(),
    &[true, true, false, true, false, false, true]
);

fn from_bits_asc<I: Iterator<Item = bool>>(xs: I) -> Natural

Converts an iterator of bits into a Natural. The bits should be in ascending order (least- to most-significant).

$$ f((b_i)_ {i=0}^{k-1}) = \sum_{i=0}^{k-1}2^i [b_i], $$ where braces denote the Iverson bracket, which converts a bit to 0 or 1.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.count().

Examples

use malachite_base::num::logic::traits::BitConvertible;
use malachite_nz::natural::Natural;
use std::iter::empty;

assert_eq!(Natural::from_bits_asc(empty()), 0);
// 105 = 1101001b
assert_eq!(
    Natural::from_bits_asc([true, false, false, true, false, true, true].iter().cloned()),
    105
);

fn from_bits_desc<I: Iterator<Item = bool>>(xs: I) -> Natural

Converts an iterator of bits into a Natural. The bits should be in descending order (most- to least-significant).

$$ f((b_i)_ {i=0}^{k-1}) = \sum_{i=0}^{k-1}2^{k-i-1} [b_i], $$ where braces denote the Iverson bracket, which converts a bit to 0 or 1.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is xs.count().

Examples

use malachite_base::num::logic::traits::BitConvertible;
use malachite_nz::natural::Natural;
use std::iter::empty;

assert_eq!(Natural::from_bits_desc(empty()), 0);
// 105 = 1101001b
assert_eq!(
    Natural::from_bits_desc([true, true, false, true, false, false, true].iter().cloned()),
    105
);

impl<'a> BitIterable for &'a Natural

fn bits(self) -> NaturalBitIterator<'a>

Returns a double-ended iterator over the bits of a Natural.

The forward order is ascending, so that less significant bits appear first. There are no trailing false bits going forward, or leading falses going backward.

If it’s necessary to get a Vec of all the bits, consider using to_bits_asc or to_bits_desc instead.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_base::num::logic::traits::BitIterable;
use malachite_nz::natural::Natural;

assert!(Natural::ZERO.bits().next().is_none());
// 105 = 1101001b
assert_eq!(
    Natural::from(105u32).bits().collect::<Vec<bool>>(),
    &[true, false, false, true, false, true, true]
);

assert!(Natural::ZERO.bits().next_back().is_none());
// 105 = 1101001b
assert_eq!(
    Natural::from(105u32).bits().rev().collect::<Vec<bool>>(),
    &[true, true, false, true, false, false, true]
);

type BitIterator = NaturalBitIterator<'a>

impl<'a, 'b> BitOr<&'a Natural> for &'b Natural

fn bitor(self, other: &'a Natural) -> Natural

Takes the bitwise or of two Naturals, taking both by reference.

$$ f(x, y) = x \vee y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) | &Natural::from(456u32), 507);
assert_eq!(
    &Natural::from(10u32).pow(12) | &(Natural::from(10u32).pow(12) - Natural::ONE),
    1000000004095u64
);

type Output = Natural

The resulting type after applying the | operator.

impl<'a> BitOr<&'a Natural> for Natural

fn bitor(self, other: &'a Natural) -> Natural

Takes the bitwise or of two Naturals, taking the first by value and the second by reference.

$$ f(x, y) = x \vee y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) | &Natural::from(456u32), 507);
assert_eq!(
    Natural::from(10u32).pow(12) | &(Natural::from(10u32).pow(12) - Natural::ONE),
    1000000004095u64
);

type Output = Natural

The resulting type after applying the | operator.

impl<'a> BitOr<Natural> for &'a Natural

fn bitor(self, other: Natural) -> Natural

Takes the bitwise or of two Naturals, taking the first by reference and the second by value.

$$ f(x, y) = x \vee y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) | Natural::from(456u32), 507);
assert_eq!(
    &Natural::from(10u32).pow(12) | (Natural::from(10u32).pow(12) - Natural::ONE),
    1000000004095u64
);

type Output = Natural

The resulting type after applying the | operator.

impl BitOr for Natural

fn bitor(self, other: Natural) -> Natural

Takes the bitwise or of two Naturals, taking both by value.

$$ f(x, y) = x \vee y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) | Natural::from(456u32), 507);
assert_eq!(
    Natural::from(10u32).pow(12) | (Natural::from(10u32).pow(12) - Natural::ONE),
    1000000004095u64
);

type Output = Natural

The resulting type after applying the | operator.

impl<'a> BitOrAssign<&'a Natural> for Natural

fn bitor_assign(&mut self, other: &'a Natural)

Bitwise-ors a Natural with another Natural in place, taking the Natural on the right-hand side by reference.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x |= &Natural::from(0x0000000fu32);
x |= &Natural::from(0x00000f00u32);
x |= &Natural::from(0x000f_0000u32);
x |= &Natural::from(0x0f000000u32);
assert_eq!(x, 0x0f0f_0f0f);

impl BitOrAssign for Natural

fn bitor_assign(&mut self, other: Natural)

Bitwise-ors a Natural with another Natural in place, taking the Natural on the right-hand side by value.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x |= Natural::from(0x0000000fu32);
x |= Natural::from(0x00000f00u32);
x |= Natural::from(0x000f_0000u32);
x |= Natural::from(0x0f000000u32);
assert_eq!(x, 0x0f0f_0f0f);

impl<'a> BitScan for &'a Natural

fn index_of_next_false_bit(self, start: u64) -> Option<u64>

Given a Natural and a starting index, searches the Natural for the smallest index of a false bit that is greater than or equal to the starting index.

Since every Natural has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the Natural’s width is allowed; the result is the starting index.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::logic::traits::BitScan;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(0), Some(0));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(20), Some(20));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(31), Some(31));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(32), Some(34));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(33), Some(34));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(34), Some(34));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(35), Some(36));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(100), Some(100));

fn index_of_next_true_bit(self, start: u64) -> Option<u64>

Given a Natural and a starting index, searches the Natural for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the Natural’s width, the result is None since there are no true bits past that point.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::logic::traits::BitScan;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(0), Some(32));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(20), Some(32));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(31), Some(32));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(32), Some(32));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(33), Some(33));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(34), Some(35));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(35), Some(35));
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(36), None);
assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(100), None);

impl<'a, 'b> BitXor<&'a Natural> for &'b Natural

fn bitxor(self, other: &'a Natural) -> Natural

Takes the bitwise xor of two Naturals, taking both by reference.

$$ f(x, y) = x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) ^ &Natural::from(456u32), 435);
assert_eq!(
    &Natural::from(10u32).pow(12) ^ &(Natural::from(10u32).pow(12) - Natural::ONE),
    8191
);

type Output = Natural

The resulting type after applying the ^ operator.

impl<'a> BitXor<&'a Natural> for Natural

fn bitxor(self, other: &'a Natural) -> Natural

Takes the bitwise xor of two Naturals, taking the first by value and the second by reference.

$$ f(x, y) = x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) ^ &Natural::from(456u32), 435);
assert_eq!(
    Natural::from(10u32).pow(12) ^ &(Natural::from(10u32).pow(12) - Natural::ONE),
    8191
);

type Output = Natural

The resulting type after applying the ^ operator.

impl<'a> BitXor<Natural> for &'a Natural

fn bitxor(self, other: Natural) -> Natural

Takes the bitwise xor of two Naturals, taking the first by reference and the second by value.

$$ f(x, y) = x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(&Natural::from(123u32) ^ Natural::from(456u32), 435);
assert_eq!(
    &Natural::from(10u32).pow(12) ^ (Natural::from(10u32).pow(12) - Natural::ONE),
    8191
);

type Output = Natural

The resulting type after applying the ^ operator.

impl BitXor for Natural

fn bitxor(self, other: Natural) -> Natural

Takes the bitwise xor of two Naturals, taking both by value.

$$ f(x, y) = x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::One;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(123u32) ^ Natural::from(456u32), 435);
assert_eq!(
    Natural::from(10u32).pow(12) ^ (Natural::from(10u32).pow(12) - Natural::ONE),
    8191
);

type Output = Natural

The resulting type after applying the ^ operator.

impl<'a> BitXorAssign<&'a Natural> for Natural

fn bitxor_assign(&mut self, other: &'a Natural)

Bitwise-xors a Natural with another Natural in place, taking the Natural on the right-hand side by reference.

$$ x \gets x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is other.significant_bits().

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x |= Natural::from(0x0000000fu32);
x |= Natural::from(0x00000f00u32);
x |= Natural::from(0x000f_0000u32);
x |= Natural::from(0x0f000000u32);
assert_eq!(x, 0x0f0f_0f0f);

impl BitXorAssign for Natural

fn bitxor_assign(&mut self, other: Natural)

Bitwise-xors a Natural with another Natural in place, taking the Natural on the right-hand side by value.

$$ x \gets x \oplus y. $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is min(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

let mut x = Natural::ZERO;
x ^= Natural::from(0x0000000fu32);
x ^= Natural::from(0x00000f00u32);
x ^= Natural::from(0x000f_0000u32);
x ^= Natural::from(0x0f000000u32);
assert_eq!(x, 0x0f0f_0f0f);

impl<'a> CeilingDivAssignNegMod<&'a Natural> for Natural

fn ceiling_div_assign_neg_mod(&mut self, other: &'a Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by reference and returning the remainder of the negative of the first number divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = y\left \lceil \frac{x}{y} \right \rceil - x, $$ $$ x \gets \left \lceil \frac{x}{y} \right \rceil. $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivAssignNegMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.ceiling_div_assign_neg_mod(&Natural::from(10u32)), 7);
assert_eq!(x, 3);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(
    x.ceiling_div_assign_neg_mod(&Natural::from_str("1234567890987").unwrap()),
    704498996588u64,
);
assert_eq!(x, 810000006724u64);

type ModOutput = Natural

impl CeilingDivAssignNegMod for Natural

fn ceiling_div_assign_neg_mod(&mut self, other: Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value and returning the remainder of the negative of the first number divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = y\left \lceil \frac{x}{y} \right \rceil - x, $$ $$ x \gets \left \lceil \frac{x}{y} \right \rceil. $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivAssignNegMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.ceiling_div_assign_neg_mod(Natural::from(10u32)), 7);
assert_eq!(x, 3);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(
    x.ceiling_div_assign_neg_mod(Natural::from_str("1234567890987").unwrap()),
    704498996588u64,
);
assert_eq!(x, 810000006724u64);

type ModOutput = Natural

impl<'a, 'b> CeilingDivNegMod<&'b Natural> for &'a Natural

fn ceiling_div_neg_mod(self, other: &'b Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by reference and returning the ceiling of the quotient and the remainder of the negative of the first Natural divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lceil \frac{x}{y} \right \rceil, \space y\left \lceil \frac{x}{y} \right \rceil - x \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivNegMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
assert_eq!(
    (&Natural::from(23u32)).ceiling_div_neg_mod(&Natural::from(10u32)).to_debug_string(),
    "(3, 7)"
);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .ceiling_div_neg_mod(&Natural::from_str("1234567890987").unwrap())
            .to_debug_string(),
    "(810000006724, 704498996588)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a> CeilingDivNegMod<&'a Natural> for Natural

fn ceiling_div_neg_mod(self, other: &'a Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by value and the second by reference and returning the ceiling of the quotient and the remainder of the negative of the first Natural divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lceil \frac{x}{y} \right \rceil, \space y\left \lceil \frac{x}{y} \right \rceil - x \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivNegMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
assert_eq!(
    Natural::from(23u32).ceiling_div_neg_mod(&Natural::from(10u32)).to_debug_string(),
    "(3, 7)"
);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .ceiling_div_neg_mod(&Natural::from_str("1234567890987").unwrap())
            .to_debug_string(),
    "(810000006724, 704498996588)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a> CeilingDivNegMod<Natural> for &'a Natural

fn ceiling_div_neg_mod(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by reference and the second by value and returning the ceiling of the quotient and the remainder of the negative of the first Natural divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lceil \frac{x}{y} \right \rceil, \space y\left \lceil \frac{x}{y} \right \rceil - x \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivNegMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
assert_eq!(
    (&Natural::from(23u32)).ceiling_div_neg_mod(Natural::from(10u32)).to_debug_string(),
    "(3, 7)"
);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .ceiling_div_neg_mod(Natural::from_str("1234567890987").unwrap())
            .to_debug_string(),
    "(810000006724, 704498996588)"
);

type DivOutput = Natural

type ModOutput = Natural

impl CeilingDivNegMod for Natural

fn ceiling_div_neg_mod(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by value and returning the ceiling of the quotient and the remainder of the negative of the first Natural divided by the second.

The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lceil \frac{x}{y} \right \rceil, \space y\left \lceil \frac{x}{y} \right \rceil - x \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingDivNegMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 3 * 10 - 7 = 23
assert_eq!(
    Natural::from(23u32).ceiling_div_neg_mod(Natural::from(10u32)).to_debug_string(),
    "(3, 7)"
);

// 810000006724 * 1234567890987 - 704498996588 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .ceiling_div_neg_mod(Natural::from_str("1234567890987").unwrap())
            .to_debug_string(),
    "(810000006724, 704498996588)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a, 'b> CeilingLogBase<&'b Natural> for &'a Natural

fn ceiling_log_base(self, base: &Natural) -> u64

Returns the ceiling of the base-$b$ logarithm of a positive Natural.

$f(x, b) = \lceil\log_b x\rceil$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is x.significant_bits().

Panics

Panics if self is 0 or base is less than 2.

Examples

use malachite_base::num::arithmetic::traits::CeilingLogBase;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(80u32).ceiling_log_base(&Natural::from(3u32)), 4);
assert_eq!(Natural::from(81u32).ceiling_log_base(&Natural::from(3u32)), 4);
assert_eq!(Natural::from(82u32).ceiling_log_base(&Natural::from(3u32)), 5);
assert_eq!(Natural::from(4294967296u64).ceiling_log_base(&Natural::from(10u32)), 10);

This is equivalent to fmpz_clog from fmpz/clog.c, FLINT 2.7.1.

type Output = u64

impl<'a> CeilingLogBase2 for &'a Natural

fn ceiling_log_base_2(self) -> u64

Returns the ceiling of the base-2 logarithm of a positive Natural.

$f(x) = \lceil\log_2 x\rceil$.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use malachite_base::num::arithmetic::traits::CeilingLogBase2;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(3u32).ceiling_log_base_2(), 2);
assert_eq!(Natural::from(100u32).ceiling_log_base_2(), 7);

type Output = u64

impl<'a> CeilingLogBasePowerOf2<u64> for &'a Natural

fn ceiling_log_base_power_of_2(self, pow: u64) -> u64

Returns the ceiling of the base-$2^k$ logarithm of a positive Natural.

$f(x, k) = \lceil\log_{2^k} x\rceil$.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0 or pow is 0.

Examples

use malachite_base::num::arithmetic::traits::CeilingLogBasePowerOf2;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(100u32).ceiling_log_base_power_of_2(2), 4);
assert_eq!(Natural::from(4294967296u64).ceiling_log_base_power_of_2(8), 4);

type Output = u64

impl<'a> CeilingRoot<u64> for &'a Natural

fn ceiling_root(self, exp: u64) -> Natural

Returns the ceiling of the $n$th root of a Natural, taking the Natural by reference.

$f(x, n) = \lceil\sqrt[n]{x}\rceil$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if exp is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingRoot;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(999u16).ceiling_root(3), 10);
assert_eq!(Natural::from(1000u16).ceiling_root(3), 10);
assert_eq!(Natural::from(1001u16).ceiling_root(3), 11);
assert_eq!(Natural::from(100000000000u64).ceiling_root(5), 159);

type Output = Natural

impl CeilingRoot<u64> for Natural

fn ceiling_root(self, exp: u64) -> Natural

Returns the ceiling of the $n$th root of a Natural, taking the Natural by value.

$f(x, n) = \lceil\sqrt[n]{x}\rceil$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if exp is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingRoot;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(999u16).ceiling_root(3), 10);
assert_eq!(Natural::from(1000u16).ceiling_root(3), 10);
assert_eq!(Natural::from(1001u16).ceiling_root(3), 11);
assert_eq!(Natural::from(100000000000u64).ceiling_root(5), 159);

type Output = Natural

impl CeilingRootAssign<u64> for Natural

fn ceiling_root_assign(&mut self, exp: u64)

Replaces a Natural with the ceiling of its $n$th root.

$x \gets \lceil\sqrt[n]{x}\rceil$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if exp is zero.

Examples

use malachite_base::num::arithmetic::traits::CeilingRootAssign;
use malachite_nz::natural::Natural;

let mut x = Natural::from(999u16);
x.ceiling_root_assign(3);
assert_eq!(x, 10);

let mut x = Natural::from(1000u16);
x.ceiling_root_assign(3);
assert_eq!(x, 10);

let mut x = Natural::from(1001u16);
x.ceiling_root_assign(3);
assert_eq!(x, 11);

let mut x = Natural::from(100000000000u64);
x.ceiling_root_assign(5);
assert_eq!(x, 159);

impl<'a> CeilingSqrt for &'a Natural

fn ceiling_sqrt(self) -> Natural

Returns the ceiling of the square root of a Natural, taking it by value.

$f(x) = \lceil\sqrt{x}\rceil$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::CeilingSqrt;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(99u8).ceiling_sqrt(), 10);
assert_eq!(Natural::from(100u8).ceiling_sqrt(), 10);
assert_eq!(Natural::from(101u8).ceiling_sqrt(), 11);
assert_eq!(Natural::from(1000000000u32).ceiling_sqrt(), 31623);
assert_eq!(Natural::from(10000000000u64).ceiling_sqrt(), 100000);

type Output = Natural

impl CeilingSqrt for Natural

fn ceiling_sqrt(self) -> Natural

Returns the ceiling of the square root of a Natural, taking it by value.

$f(x) = \lceil\sqrt{x}\rceil$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::CeilingSqrt;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(99u8).ceiling_sqrt(), 10);
assert_eq!(Natural::from(100u8).ceiling_sqrt(), 10);
assert_eq!(Natural::from(101u8).ceiling_sqrt(), 11);
assert_eq!(Natural::from(1000000000u32).ceiling_sqrt(), 31623);
assert_eq!(Natural::from(10000000000u64).ceiling_sqrt(), 100000);

type Output = Natural

impl CeilingSqrtAssign for Natural

fn ceiling_sqrt_assign(&mut self)

Replaces a Natural with the ceiling of its square root.

$x \gets \lceil\sqrt{x}\rceil$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::CeilingSqrtAssign;
use malachite_nz::natural::Natural;

let mut x = Natural::from(99u8);
x.ceiling_sqrt_assign();
assert_eq!(x, 10);

let mut x = Natural::from(100u8);
x.ceiling_sqrt_assign();
assert_eq!(x, 10);

let mut x = Natural::from(101u8);
x.ceiling_sqrt_assign();
assert_eq!(x, 11);

let mut x = Natural::from(1000000000u32);
x.ceiling_sqrt_assign();
assert_eq!(x, 31623);

let mut x = Natural::from(10000000000u64);
x.ceiling_sqrt_assign();
assert_eq!(x, 100000);

impl<'a, 'b> CheckedDiv<&'b Natural> for &'a Natural

fn checked_div(self, other: &'b Natural) -> Option<Natural>

Divides a Natural by another Natural, taking both by reference. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$. Returns None when the second Natural is zero, Some otherwise.

$$ f(x, y) = \begin{cases} \operatorname{Some}\left ( \left \lfloor \frac{x}{y} \right \rfloor \right ) & \text{if} \quad y \neq 0 \\ \text{None} & \text{otherwise} \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedDiv;
use malachite_base::num::basic::traits::{One, Zero};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).checked_div(&Natural::from(10u32)).to_debug_string(),
    "Some(2)"
);
assert_eq!((&Natural::ONE).checked_div(&Natural::ZERO), None);

type Output = Natural

impl<'a> CheckedDiv<&'a Natural> for Natural

fn checked_div(self, other: &'a Natural) -> Option<Natural>

Divides a Natural by another Natural, taking the first by value and the second by reference. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$. Returns None when the second Natural is zero, Some otherwise.

$$ f(x, y) = \begin{cases} \operatorname{Some}\left ( \left \lfloor \frac{x}{y} \right \rfloor \right ) & \text{if} \quad y \neq 0 \\ \text{None} & \text{otherwise} \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedDiv;
use malachite_base::num::basic::traits::{One, Zero};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

// 2 * 10 + 3 = 23
assert_eq!(
    Natural::from(23u32).checked_div(&Natural::from(10u32)).to_debug_string(),
    "Some(2)"
);
assert_eq!(Natural::ONE.checked_div(&Natural::ZERO), None);

type Output = Natural

impl<'a> CheckedDiv<Natural> for &'a Natural

fn checked_div(self, other: Natural) -> Option<Natural>

Divides a Natural by another Natural, taking the first by reference and the second by value. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$. Returns None when the second Natural is zero, Some otherwise.

$$ f(x, y) = \begin{cases} \operatorname{Some}\left ( \left \lfloor \frac{x}{y} \right \rfloor \right ) & \text{if} \quad y \neq 0 \\ \text{None} & \text{otherwise} \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedDiv;
use malachite_base::num::basic::traits::{One, Zero};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).checked_div(Natural::from(10u32)).to_debug_string(),
    "Some(2)"
);
assert_eq!((&Natural::ONE).checked_div(Natural::ZERO), None);

type Output = Natural

impl CheckedDiv for Natural

fn checked_div(self, other: Natural) -> Option<Natural>

Divides a Natural by another Natural, taking both by value. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$. Returns None when the second Natural is zero, Some otherwise.

$$ f(x, y) = \begin{cases} \operatorname{Some}\left ( \left \lfloor \frac{x}{y} \right \rfloor \right ) & \text{if} \quad y \neq 0 \\ \text{None} & \text{otherwise} \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedDiv;
use malachite_base::num::basic::traits::{One, Zero};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

// 2 * 10 + 3 = 23
assert_eq!(
    Natural::from(23u32).checked_div(Natural::from(10u32)).to_debug_string(),
    "Some(2)"
);
assert_eq!(Natural::ONE.checked_div(Natural::ZERO), None);

type Output = Natural

impl<'a, 'b> CheckedLogBase<&'b Natural> for &'a Natural

fn checked_log_base(self, base: &Natural) -> Option<u64>

Returns the base-$b$ logarithm of a positive Natural. If the Natural is not a power of $b$, then None is returned.

$$ f(x, b) = \begin{cases} \operatorname{Some}(\log_b x) & \text{if} \quad \log_b x \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is x.significant_bits().

Panics

Panics if self is 0 or base is less than 2.

Examples

use malachite_base::num::arithmetic::traits::CheckedLogBase;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(80u32).checked_log_base(&Natural::from(3u32)), None);
assert_eq!(Natural::from(81u32).checked_log_base(&Natural::from(3u32)), Some(4));
assert_eq!(Natural::from(82u32).checked_log_base(&Natural::from(3u32)), None);
assert_eq!(Natural::from(4294967296u64).checked_log_base(&Natural::from(10u32)), None);

type Output = u64

impl<'a> CheckedLogBase2 for &'a Natural

fn checked_log_base_2(self) -> Option<u64>

Returns the base-2 logarithm of a positive Natural. If the Natural is not a power of 2, then None is returned.

$$ f(x) = \begin{cases} \operatorname{Some}(\log_2 x) & \text{if} \quad \log_2 x \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use malachite_base::num::arithmetic::traits::CheckedLogBase2;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::from(3u32).checked_log_base_2(), None);
assert_eq!(Natural::from(4u32).checked_log_base_2(), Some(2));
assert_eq!(
    Natural::from_str("1267650600228229401496703205376").unwrap().checked_log_base_2(),
    Some(100)
);

type Output = u64

impl<'a> CheckedLogBasePowerOf2<u64> for &'a Natural

fn checked_log_base_power_of_2(self, pow: u64) -> Option<u64>

Returns the base-$2^k$ logarithm of a positive Natural. If the Natural is not a power of $2^k$, then None is returned.

$$ f(x, k) = \begin{cases} \operatorname{Some}(\log_{2^k} x) & \text{if} \quad \log_{2^k} x \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0 or pow is 0.

Examples

use malachite_base::num::arithmetic::traits::CheckedLogBasePowerOf2;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::from(100u32).checked_log_base_power_of_2(2), None);
assert_eq!(Natural::from(4294967296u64).checked_log_base_power_of_2(8), Some(4));

type Output = u64

impl<'a> CheckedRoot<u64> for &'a Natural

fn checked_root(self, exp: u64) -> Option<Natural>

Returns the the $n$th root of a Natural, or None if the Natural is not a perfect $n$th power. The Natural is taken by reference.

$$ f(x, n) = \begin{cases} \operatorname{Some}(sqrt[n]{x}) & \text{if} \quad \sqrt[n]{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if exp is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedRoot;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::from(999u16)).checked_root(3).to_debug_string(), "None");
assert_eq!((&Natural::from(1000u16)).checked_root(3).to_debug_string(), "Some(10)");
assert_eq!((&Natural::from(1001u16)).checked_root(3).to_debug_string(), "None");
assert_eq!((&Natural::from(100000000000u64)).checked_root(5).to_debug_string(), "None");
assert_eq!(
    (&Natural::from(10000000000u64)).checked_root(5).to_debug_string(),
    "Some(100)"
);

type Output = Natural

impl CheckedRoot<u64> for Natural

fn checked_root(self, exp: u64) -> Option<Natural>

Returns the the $n$th root of a Natural, or None if the Natural is not a perfect $n$th power. The Natural is taken by value.

$$ f(x, n) = \begin{cases} \operatorname{Some}(sqrt[n]{x}) & \text{if} \quad \sqrt[n]{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if exp is zero.

Examples

use malachite_base::num::arithmetic::traits::CheckedRoot;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(999u16).checked_root(3).to_debug_string(), "None");
assert_eq!(Natural::from(1000u16).checked_root(3).to_debug_string(), "Some(10)");
assert_eq!(Natural::from(1001u16).checked_root(3).to_debug_string(), "None");
assert_eq!(Natural::from(100000000000u64).checked_root(5).to_debug_string(), "None");
assert_eq!(Natural::from(10000000000u64).checked_root(5).to_debug_string(), "Some(100)");

type Output = Natural

impl<'a> CheckedSqrt for &'a Natural

fn checked_sqrt(self) -> Option<Natural>

Returns the the square root of a Natural, or None if it is not a perfect square. The Natural is taken by value.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::CheckedSqrt;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::from(99u8)).checked_sqrt().to_debug_string(), "None");
assert_eq!((&Natural::from(100u8)).checked_sqrt().to_debug_string(), "Some(10)");
assert_eq!((&Natural::from(101u8)).checked_sqrt().to_debug_string(), "None");
assert_eq!((&Natural::from(1000000000u32)).checked_sqrt().to_debug_string(), "None");
assert_eq!(
    (&Natural::from(10000000000u64)).checked_sqrt().to_debug_string(),
    "Some(100000)"
);

type Output = Natural

impl CheckedSqrt for Natural

fn checked_sqrt(self) -> Option<Natural>

Returns the the square root of a Natural, or None if it is not a perfect square. The Natural is taken by value.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::CheckedSqrt;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(99u8).checked_sqrt().to_debug_string(), "None");
assert_eq!(Natural::from(100u8).checked_sqrt().to_debug_string(), "Some(10)");
assert_eq!(Natural::from(101u8).checked_sqrt().to_debug_string(), "None");
assert_eq!(Natural::from(1000000000u32).checked_sqrt().to_debug_string(), "None");
assert_eq!(Natural::from(10000000000u64).checked_sqrt().to_debug_string(), "Some(100000)");

type Output = Natural

impl<'a, 'b> CheckedSub<&'a Natural> for &'b Natural

fn checked_sub(self, other: &'a Natural) -> Option<Natural>

Subtracts a Natural by another Natural, taking both by reference and returning None if the result is negative.

$$ f(x, y) = \begin{cases} \operatorname{Some}(x - y) & \text{if} \quad x \geq y, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{CheckedSub, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::ZERO).checked_sub(&Natural::from(123u32)).to_debug_string(), "None");
assert_eq!((&Natural::from(123u32)).checked_sub(&Natural::ZERO).to_debug_string(),
    "Some(123)");
assert_eq!((&Natural::from(456u32)).checked_sub(&Natural::from(123u32)).to_debug_string(),
    "Some(333)");
assert_eq!(
    (&(Natural::from(10u32).pow(12) * Natural::from(3u32)))
            .checked_sub(&Natural::from(10u32).pow(12)).to_debug_string(),
    "Some(2000000000000)"
);

type Output = Natural

impl<'a> CheckedSub<&'a Natural> for Natural

fn checked_sub(self, other: &'a Natural) -> Option<Natural>

Subtracts a Natural by another Natural, taking the first by value and the second by reference and returning None if the result is negative.

$$ f(x, y) = \begin{cases} \operatorname{Some}(x - y) & \text{if} \quad x \geq y, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{CheckedSub, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.checked_sub(&Natural::from(123u32)).to_debug_string(), "None");
assert_eq!(
    Natural::from(123u32).checked_sub(&Natural::ZERO).to_debug_string(),
    "Some(123)"
);
assert_eq!(Natural::from(456u32).checked_sub(&Natural::from(123u32)).to_debug_string(),
    "Some(333)");
assert_eq!(
    (Natural::from(10u32).pow(12) * Natural::from(3u32))
            .checked_sub(&Natural::from(10u32).pow(12)).to_debug_string(),
    "Some(2000000000000)"
);

type Output = Natural

impl<'a> CheckedSub<Natural> for &'a Natural

fn checked_sub(self, other: Natural) -> Option<Natural>

Subtracts a Natural by another Natural, taking the first by reference and the second by value and returning None if the result is negative.

$$ f(x, y) = \begin{cases} \operatorname{Some}(x - y) & \text{if} \quad x \geq y, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{CheckedSub, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::ZERO).checked_sub(Natural::from(123u32)).to_debug_string(), "None");
assert_eq!((&Natural::from(123u32)).checked_sub(Natural::ZERO).to_debug_string(),
    "Some(123)");
assert_eq!((&Natural::from(456u32)).checked_sub(Natural::from(123u32)).to_debug_string(),
    "Some(333)");
assert_eq!(
    (&(Natural::from(10u32).pow(12) * Natural::from(3u32)))
            .checked_sub(Natural::from(10u32).pow(12)).to_debug_string(),
    "Some(2000000000000)"
);

type Output = Natural

impl CheckedSub for Natural

fn checked_sub(self, other: Natural) -> Option<Natural>

Subtracts a Natural by another Natural, taking both by value and returning None if the result is negative.

$$ f(x, y) = \begin{cases} \operatorname{Some}(x - y) & \text{if} \quad x \geq y, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{CheckedSub, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.checked_sub(Natural::from(123u32)).to_debug_string(), "None");
assert_eq!(
    Natural::from(123u32).checked_sub(Natural::ZERO).to_debug_string(),
    "Some(123)"
);
assert_eq!(
    Natural::from(456u32).checked_sub(Natural::from(123u32)).to_debug_string(),
    "Some(333)"
);
assert_eq!(
    (Natural::from(10u32).pow(12) * Natural::from(3u32))
            .checked_sub(Natural::from(10u32).pow(12)).to_debug_string(),
    "Some(2000000000000)"
);

type Output = Natural

impl<'a> CheckedSubMul<&'a Natural> for Natural

fn checked_sub_mul(self, y: &'a Natural, z: Natural) -> Option<Natural>

Subtracts a Natural by the product of two other Naturals, taking the first and third by value and the second by reference and returning None if the result is negative.

$$ f(x, y, z) = \begin{cases} \operatorname{Some}(x - yz) & \text{if} \quad x \geq yz, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Panics

Panics if y * z is greater than self.

Examples

use malachite_base::num::arithmetic::traits::{CheckedSubMul, Pow};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    Natural::from(20u32).checked_sub_mul(&Natural::from(3u32), Natural::from(4u32))
            .to_debug_string(),
    "Some(8)"
);
assert_eq!(
    Natural::from(10u32).checked_sub_mul(&Natural::from(3u32), Natural::from(4u32))
            .to_debug_string(),
    "None"
);
assert_eq!(
    Natural::from(10u32).pow(12)
            .checked_sub_mul(&Natural::from(0x10000u32), Natural::from(0x10000u32))
            .to_debug_string(),
    "Some(995705032704)"
);

type Output = Natural

impl<'a, 'b, 'c> CheckedSubMul<&'a Natural, &'b Natural> for &'c Natural

fn checked_sub_mul(self, y: &'a Natural, z: &'b Natural) -> Option<Natural>

Subtracts a Natural by the product of two other Naturals, taking all three by reference and returning None if the result is negative.

$$ f(x, y, z) = \begin{cases} \operatorname{Some}(x - yz) & \text{if} \quad x \geq yz, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n, m) = O(m + n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::{CheckedSubMul, Pow};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    (&Natural::from(20u32)).checked_sub_mul(&Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "Some(8)"
);
assert_eq!(
    (&Natural::from(10u32)).checked_sub_mul(&Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "None"
);
assert_eq!(
    (&Natural::from(10u32).pow(12))
            .checked_sub_mul(&Natural::from(0x10000u32), &Natural::from(0x10000u32))
            .to_debug_string(),
    "Some(995705032704)"
);

type Output = Natural

impl<'a, 'b> CheckedSubMul<&'a Natural, &'b Natural> for Natural

fn checked_sub_mul(self, y: &'a Natural, z: &'b Natural) -> Option<Natural>

Subtracts a Natural by the product of two other Naturals, taking the first by value and the second and third by reference and returning None if the result is negative.

$$ f(x, y, z) = \begin{cases} \operatorname{Some}(x - yz) & \text{if} \quad x \geq yz, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Panics

Panics if y * z is greater than self.

Examples

use malachite_base::num::arithmetic::traits::{CheckedSubMul, Pow};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    Natural::from(20u32).checked_sub_mul(&Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "Some(8)"
);
assert_eq!(
    Natural::from(10u32).checked_sub_mul(&Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "None"
);
assert_eq!(
    Natural::from(10u32).pow(12)
            .checked_sub_mul(&Natural::from(0x10000u32), &Natural::from(0x10000u32))
            .to_debug_string(),
    "Some(995705032704)"
);

type Output = Natural

impl<'a> CheckedSubMul<Natural, &'a Natural> for Natural

fn checked_sub_mul(self, y: Natural, z: &'a Natural) -> Option<Natural>

Subtracts a Natural by the product of two other Naturals, taking the first two by value and the third by reference and returning None if the result is negative.

$$ f(x, y, z) = \begin{cases} \operatorname{Some}(x - yz) & \text{if} \quad x \geq yz, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Panics

Panics if y * z is greater than self.

Examples

use malachite_base::num::arithmetic::traits::{CheckedSubMul, Pow};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    Natural::from(20u32).checked_sub_mul(Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "Some(8)"
);
assert_eq!(
    Natural::from(10u32).checked_sub_mul(Natural::from(3u32), &Natural::from(4u32))
            .to_debug_string(),
    "None"
);
assert_eq!(
    Natural::from(10u32).pow(12)
            .checked_sub_mul(Natural::from(0x10000u32), &Natural::from(0x10000u32))
            .to_debug_string(),
    "Some(995705032704)"
);

type Output = Natural

impl CheckedSubMul for Natural

fn checked_sub_mul(self, y: Natural, z: Natural) -> Option<Natural>

Subtracts a Natural by the product of two other Naturals, taking all three by value and returning None if the result is negative.

$$ f(x, y, z) = \begin{cases} \operatorname{Some}(x - yz) & \text{if} \quad x \geq yz, \\ \operatorname{None} & \text{otherwise}. \end{cases} $$

Worst-case complexity

$T(n, m) = O(m + n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, $n$ is max(y.significant_bits(), z.significant_bits()), and $m$ is self.significant_bits().

Panics

Panics if y * z is greater than self.

Examples

use malachite_base::num::arithmetic::traits::{CheckedSubMul, Pow};
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    Natural::from(20u32).checked_sub_mul(Natural::from(3u32), Natural::from(4u32))
            .to_debug_string(),
    "Some(8)"
);
assert_eq!(
    Natural::from(10u32).checked_sub_mul(Natural::from(3u32), Natural::from(4u32))
            .to_debug_string(),
    "None"
);
assert_eq!(
    Natural::from(10u32).pow(12)
            .checked_sub_mul(Natural::from(0x10000u32), Natural::from(0x10000u32))
            .to_debug_string(),
    "Some(995705032704)"
);

type Output = Natural

impl Clone for Natural

fn clone(&self) -> Natural

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a> ConvertibleFrom<&'a Integer> for Natural

fn convertible_from(value: &'a Integer) -> bool

Determines whether an Integer can be converted to a Natural (when the Integer is non-negative). Takes the Integer by reference.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::conversion::traits::ConvertibleFrom;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;

assert_eq!(Natural::convertible_from(&Integer::from(123)), true);
assert_eq!(Natural::convertible_from(&Integer::from(-123)), false);
assert_eq!(Natural::convertible_from(&Integer::from(10u32).pow(12)), true);
assert_eq!(Natural::convertible_from(&-Integer::from(10u32).pow(12)), false);

impl<'a> ConvertibleFrom<&'a Natural> for f32

fn convertible_from(value: &'a Natural) -> bool

Determines whether a Natural can be exactly converted to a primitive float.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is value.significant_bits().

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for f64

fn convertible_from(value: &'a Natural) -> bool

Determines whether a Natural can be exactly converted to a primitive float.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is value.significant_bits().

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for i128

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a signed primitive integer type that’s larger than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for i16

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a signed primitive integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for i32

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a signed primitive integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for i64

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a SignedLimb (the signed type whose width is the same as a limb’s).

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for i8

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a signed primitive integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for isize

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to an isize.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for u128

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a primitive unsigned integer type that’s larger than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for u16

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a primitive unsigned integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for u32

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a primitive unsigned integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for u64

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for u8

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a value of a primitive unsigned integer type that’s smaller than a Limb.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a> ConvertibleFrom<&'a Natural> for usize

fn convertible_from(value: &Natural) -> bool

Determines whether a Natural can be converted to a usize.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<Integer> for Natural

fn convertible_from(value: Integer) -> bool

Determines whether an Integer can be converted to a Natural (when the Integer is non-negative). Takes the Integer by value.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::conversion::traits::ConvertibleFrom;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;

assert_eq!(Natural::convertible_from(Integer::from(123)), true);
assert_eq!(Natural::convertible_from(Integer::from(-123)), false);
assert_eq!(Natural::convertible_from(Integer::from(10u32).pow(12)), true);
assert_eq!(Natural::convertible_from(-Integer::from(10u32).pow(12)), false);

impl ConvertibleFrom<f32> for Natural

fn convertible_from(value: f32) -> bool

Determines whether a floating-point value can be exactly converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<f64> for Natural

fn convertible_from(value: f64) -> bool

Determines whether a floating-point value can be exactly converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<i128> for Natural

fn convertible_from(i: i128) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<i16> for Natural

fn convertible_from(i: i16) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<i32> for Natural

fn convertible_from(i: i32) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<i64> for Natural

fn convertible_from(i: i64) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<i8> for Natural

fn convertible_from(i: i8) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl ConvertibleFrom<isize> for Natural

fn convertible_from(i: isize) -> bool

Determines whether a signed primitive integer can be converted to a Natural.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl<'a, 'b> CoprimeWith<&'b Natural> for &'a Natural

fn coprime_with(self, other: &'b Natural) -> bool

Returns whether two Naturals are coprime; that is, whether they have no common factor other than 1. Both Naturals are taken by reference.

Every Natural is coprime with 1. No Natural is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::CoprimeWith;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::from(3u32)).coprime_with(Natural::from(5u32)), true);
assert_eq!((&Natural::from(12u32)).coprime_with(Natural::from(90u32)), false);

impl<'a> CoprimeWith<&'a Natural> for Natural

fn coprime_with(self, other: &'a Natural) -> bool

Returns whether two Naturals are coprime; that is, whether they have no common factor other than 1. The first Natural is taken by value and the second by reference.

Every Natural is coprime with 1. No Natural is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::CoprimeWith;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(3u32).coprime_with(&Natural::from(5u32)), true);
assert_eq!(Natural::from(12u32).coprime_with(&Natural::from(90u32)), false);

impl<'a> CoprimeWith<Natural> for &'a Natural

fn coprime_with(self, other: Natural) -> bool

Returns whether two Naturals are coprime; that is, whether they have no common factor other than 1. The first Natural is taken by reference and the second by value.

Every Natural is coprime with 1. No Natural is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::CoprimeWith;
use malachite_nz::natural::Natural;

assert_eq!((&Natural::from(3u32)).coprime_with(Natural::from(5u32)), true);
assert_eq!((&Natural::from(12u32)).coprime_with(Natural::from(90u32)), false);

impl CoprimeWith for Natural

fn coprime_with(self, other: Natural) -> bool

Returns whether two Naturals are coprime; that is, whether they have no common factor other than 1. Both Naturals are taken by value.

Every Natural is coprime with 1. No Natural is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::CoprimeWith;
use malachite_nz::natural::Natural;

assert_eq!(Natural::from(3u32).coprime_with(Natural::from(5u32)), true);
assert_eq!(Natural::from(12u32).coprime_with(Natural::from(90u32)), false);

impl CountOnes for &Natural

fn count_ones(self) -> u64

Counts the number of ones in the binary expansion of a Natural.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::Pow;
use malachite_base::num::basic::traits::Zero;
use malachite_base::num::logic::traits::CountOnes;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.count_ones(), 0);
// 105 = 1101001b
assert_eq!(Natural::from(105u32).count_ones(), 4);
// 10^12 = 1110100011010100101001010001000000000000b
assert_eq!(Natural::from(10u32).pow(12).count_ones(), 13);

impl Debug for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Converts a Natural to a String.

This is the same as the Display::fmt implementation.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::ZERO.to_debug_string(), "0");
assert_eq!(Natural::from(123u32).to_debug_string(), "123");
assert_eq!(
    Natural::from_str("1000000000000").unwrap().to_debug_string(),
    "1000000000000"
);
assert_eq!(format!("{:05?}", Natural::from(123u32)), "00123");

impl Default for Natural

fn default() -> Natural

The default value of a Natural, 0.

impl Digits<Natural> for Natural

fn to_digits_asc(&self, base: &Natural) -> Vec<Natural>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

use malachite_base::num::basic::traits::{Two, Zero};
use malachite_base::num::conversion::traits::Digits;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.to_digits_asc(&Natural::from(6u32)).to_debug_string(), "[]");
assert_eq!(Natural::TWO.to_digits_asc(&Natural::from(6u32)).to_debug_string(), "[2]");
assert_eq!(
    Natural::from(123456u32).to_digits_asc(&Natural::from(3u32)).to_debug_string(),
    "[0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 2]"
);

fn to_digits_desc(&self, base: &Natural) -> Vec<Natural>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

use malachite_base::num::basic::traits::{Two, Zero};
use malachite_base::num::conversion::traits::Digits;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.to_digits_desc(&Natural::from(6u32)).to_debug_string(), "[]");
assert_eq!(Natural::TWO.to_digits_desc(&Natural::from(6u32)).to_debug_string(), "[2]");
assert_eq!(
    Natural::from(123456u32).to_digits_desc(&Natural::from(3u32)).to_debug_string(),
    "[2, 0, 0, 2, 1, 1, 0, 0, 1, 1, 0]"
);

fn from_digits_asc<I: Iterator<Item = Natural>>( base: &Natural, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n, m) = O(nm (\log (nm))^2 \log\log (nm))$

$M(n, m) = O(nm \log (nm))$

where $T$ is time, $M$ is additional memory, $n$ is digits.count(), and $m$ is base.significant_bits().

Panics

Panics if base is less than 2.

Examples

use malachite_base::num::conversion::traits::Digits;
use malachite_base::strings::ToDebugString;
use malachite_base::vecs::vec_from_str;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from_digits_asc(
        &Natural::from(64u32),
        vec_from_str::<Natural>("[0, 0, 0]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(0)"
);
assert_eq!(
    Natural::from_digits_asc(
        &Natural::from(3u32),
        vec_from_str::<Natural>("[0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 2]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(123456)"
);
assert_eq!(
    Natural::from_digits_asc(
        &Natural::from(8u32),
        vec_from_str::<Natural>("[3, 7, 1]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(123)"
);
assert_eq!(
    Natural::from_digits_asc(
        &Natural::from(8u32),
        vec_from_str::<Natural>("[1, 10, 3]").unwrap().into_iter()
    ).to_debug_string(),
    "None"
);

fn from_digits_desc<I: Iterator<Item = Natural>>( base: &Natural, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n, m) = O(nm (\log (nm))^2 \log\log (nm))$

$M(n, m) = O(nm \log (nm))$

where $T$ is time, $M$ is additional memory, $n$ is digits.count(), and $m$ is base.significant_bits().

Panics

Panics if base is less than 2.

Examples

use malachite_base::num::conversion::traits::Digits;
use malachite_base::strings::ToDebugString;
use malachite_base::vecs::vec_from_str;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from_digits_desc(
        &Natural::from(64u32),
        vec_from_str::<Natural>("[0, 0, 0]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(0)"
);
assert_eq!(
    Natural::from_digits_desc(
        &Natural::from(3u32),
        vec_from_str::<Natural>("[2, 0, 0, 2, 1, 1, 0, 0, 1, 1, 0]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(123456)"
);
assert_eq!(
    Natural::from_digits_desc(
        &Natural::from(8u32),
        vec_from_str::<Natural>("[1, 7, 3]").unwrap().into_iter()
    ).to_debug_string(),
    "Some(123)"
);
assert_eq!(
    Natural::from_digits_desc(
        &Natural::from(8u32),
        vec_from_str::<Natural>("[3, 10, 1]").unwrap().into_iter()
    ).to_debug_string(),
    "None"
);

impl Digits<u128> for Natural

fn to_digits_asc(&self, base: &u128) -> Vec<u128>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &u128) -> Vec<u128>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = u128>>( base: &u128, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = u128>>( base: &u128, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Digits<u16> for Natural

fn to_digits_asc(&self, base: &u16) -> Vec<u16>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &u16) -> Vec<u16>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = u16>>( base: &u16, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = u16>>( base: &u16, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Digits<u32> for Natural

fn to_digits_asc(&self, base: &u32) -> Vec<u32>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &u32) -> Vec<u32>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = u32>>( base: &u32, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = u32>>( base: &u32, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Digits<u64> for Natural

fn to_digits_asc(&self, base: &u64) -> Vec<u64>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &u64) -> Vec<u64>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = u64>>( base: &u64, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = u64>>( base: &u64, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Digits<u8> for Natural

fn to_digits_asc(&self, base: &u8) -> Vec<u8>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &u8) -> Vec<u8>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = u8>>( base: &u8, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = u8>>( base: &u8, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Digits<usize> for Natural

fn to_digits_asc(&self, base: &usize) -> Vec<usize>

Returns a Vec containing the digits of a Natural in ascending order (least- to most-significant).

If the Natural is 0, the Vec is empty; otherwise, it ends with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_i = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn to_digits_desc(&self, base: &usize) -> Vec<usize>

Returns a Vec containing the digits of a Natural in descending order (most- to least-significant).

If the Natural is 0, the Vec is empty; otherwise, it begins with a nonzero digit.

$f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or $d_{k-1} \neq 0$, and

$$ \sum_{i=0}^{k-1}b^i d_{k-i-1} = x. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_asc<I: Iterator<Item = usize>>( base: &usize, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in ascending order (least- to most-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

fn from_digits_desc<I: Iterator<Item = usize>>( base: &usize, digits: I ) -> Option<Natural>

Converts an iterator of digits into a Natural.

The input digits are in descending order (most- to least-significant). The function returns None if any of the digits are greater than or equal to the base.

$$ f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i. $$

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is digits.count().

Panics

Panics if base is less than 2.

Examples

See here.

impl Display for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Converts a Natural to a String.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::ZERO.to_string(), "0");
assert_eq!(Natural::from(123u32).to_string(), "123");
assert_eq!(
    Natural::from_str("1000000000000").unwrap().to_string(),
    "1000000000000"
);
assert_eq!(format!("{:05}", Natural::from(123u32)), "00123");

impl<'a, 'b> Div<&'b Natural> for &'a Natural

fn div(self, other: &'b Natural) -> Natural

Divides a Natural by another Natural, taking both by reference. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(&Natural::from(23u32) / &Natural::from(10u32), 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    &Natural::from_str("1000000000000000000000000").unwrap() /
    &Natural::from_str("1234567890987").unwrap(),
    810000006723u64
);

type Output = Natural

The resulting type after applying the / operator.

impl<'a> Div<&'a Natural> for Natural

fn div(self, other: &'a Natural) -> Natural

Divides a Natural by another Natural, taking the first by value and the second by reference. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(Natural::from(23u32) / &Natural::from(10u32), 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap() /
            &Natural::from_str("1234567890987").unwrap(),
    810000006723u64
);

type Output = Natural

The resulting type after applying the / operator.

impl<'a> Div<Natural> for &'a Natural

fn div(self, other: Natural) -> Natural

Divides a Natural by another Natural, taking the first by reference and the second by value. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(&Natural::from(23u32) / Natural::from(10u32), 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    &Natural::from_str("1000000000000000000000000").unwrap() /
            Natural::from_str("1234567890987").unwrap(),
    810000006723u64
);

type Output = Natural

The resulting type after applying the / operator.

impl Div for Natural

fn div(self, other: Natural) -> Natural

Divides a Natural by another Natural, taking both by value. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left \lfloor \frac{x}{y} \right \rfloor. $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(Natural::from(23u32) / Natural::from(10u32), 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap() /
            Natural::from_str("1234567890987").unwrap(),
    810000006723u64
);

type Output = Natural

The resulting type after applying the / operator.

impl<'a> DivAssign<&'a Natural> for Natural

fn div_assign(&mut self, other: &'a Natural)

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by reference. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
x /= &Natural::from(10u32);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
x /= &Natural::from_str("1234567890987").unwrap();
assert_eq!(x, 810000006723u64);

impl DivAssign for Natural

fn div_assign(&mut self, other: Natural)

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value. The quotient is rounded towards negative infinity. The quotient and remainder (which is not computed) satisfy $x = qy + r$ and $0 \leq r < y$.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
x /= Natural::from(10u32);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
x /= Natural::from_str("1234567890987").unwrap();
assert_eq!(x, 810000006723u64);

impl<'a> DivAssignMod<&'a Natural> for Natural

fn div_assign_mod(&mut self, other: &'a Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value and returning the remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor, $$ $$ x \gets \left \lfloor \frac{x}{y} \right \rfloor. $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivAssignMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.div_assign_mod(&Natural::from(10u32)), 3);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(
    x.div_assign_mod(&Natural::from_str("1234567890987").unwrap()),
    530068894399u64
);
assert_eq!(x, 810000006723u64);

type ModOutput = Natural

impl DivAssignMod for Natural

fn div_assign_mod(&mut self, other: Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value and returning the remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor, $$ $$ x \gets \left \lfloor \frac{x}{y} \right \rfloor. $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivAssignMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.div_assign_mod(Natural::from(10u32)), 3);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(x.div_assign_mod(Natural::from_str("1234567890987").unwrap()), 530068894399u64);
assert_eq!(x, 810000006723u64);

type ModOutput = Natural

impl<'a> DivAssignRem<&'a Natural> for Natural

fn div_assign_rem(&mut self, other: &'a Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by reference and returning the remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor, $$ $$ x \gets \left \lfloor \frac{x}{y} \right \rfloor. $$

For Naturals, div_assign_rem is equivalent to div_assign_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivAssignRem;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.div_assign_rem(&Natural::from(10u32)), 3);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(
    x.div_assign_rem(&Natural::from_str("1234567890987").unwrap()),
    530068894399u64
);
assert_eq!(x, 810000006723u64);

type RemOutput = Natural

impl DivAssignRem for Natural

fn div_assign_rem(&mut self, other: Natural) -> Natural

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value and returning the remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor, $$ $$ x \gets \left \lfloor \frac{x}{y} \right \rfloor. $$

For Naturals, div_assign_rem is equivalent to div_assign_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivAssignRem;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
let mut x = Natural::from(23u32);
assert_eq!(x.div_assign_rem(Natural::from(10u32)), 3);
assert_eq!(x, 2);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
let mut x = Natural::from_str("1000000000000000000000000").unwrap();
assert_eq!(x.div_assign_rem(Natural::from_str("1234567890987").unwrap()), 530068894399u64);
assert_eq!(x, 810000006723u64);

type RemOutput = Natural

impl<'a, 'b> DivExact<&'b Natural> for &'a Natural

fn div_exact(self, other: &'b Natural) -> Natural

Divides a Natural by another Natural, taking both by reference. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ f(x, y) = \frac{x}{y}. $$

If you are unsure whether the division will be exact, use &self / &other instead. If you’re unsure and you want to know, use (&self).div_mod(&other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use (&self).div_round(&other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExact;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
assert_eq!((&Natural::from(56088u32)).div_exact(&Natural::from(456u32)), 123);

// 123456789000 * 987654321000 = 121932631112635269000000
assert_eq!(
    (&Natural::from_str("121932631112635269000000").unwrap())
            .div_exact(&Natural::from_str("987654321000").unwrap()),
    123456789000u64
);

type Output = Natural

impl<'a> DivExact<&'a Natural> for Natural

fn div_exact(self, other: &'a Natural) -> Natural

Divides a Natural by another Natural, taking the first by value and the second by reference. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ f(x, y) = \frac{x}{y}. $$

If you are unsure whether the division will be exact, use self / &other instead. If you’re unsure and you want to know, use self.div_mod(&other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use self.div_round(&other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExact;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
assert_eq!(Natural::from(56088u32).div_exact(&Natural::from(456u32)), 123);

// 123456789000 * 987654321000 = 121932631112635269000000
assert_eq!(
    Natural::from_str("121932631112635269000000").unwrap()
            .div_exact(&Natural::from_str("987654321000").unwrap()),
    123456789000u64
);

type Output = Natural

impl<'a> DivExact<Natural> for &'a Natural

fn div_exact(self, other: Natural) -> Natural

Divides a Natural by another Natural, taking the first by reference and the second by value. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ f(x, y) = \frac{x}{y}. $$

If you are unsure whether the division will be exact, use &self / other instead. If you’re unsure and you want to know, use self.div_mod(other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use (&self).div_round(other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExact;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
assert_eq!((&Natural::from(56088u32)).div_exact(Natural::from(456u32)), 123);

// 123456789000 * 987654321000 = 121932631112635269000000
assert_eq!(
    (&Natural::from_str("121932631112635269000000").unwrap())
            .div_exact(Natural::from_str("987654321000").unwrap()),
    123456789000u64
);

type Output = Natural

impl DivExact for Natural

fn div_exact(self, other: Natural) -> Natural

Divides a Natural by another Natural, taking both by value. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ f(x, y) = \frac{x}{y}. $$

If you are unsure whether the division will be exact, use self / other instead. If you’re unsure and you want to know, use self.div_mod(other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use self.div_round(other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExact;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
assert_eq!(Natural::from(56088u32).div_exact(Natural::from(456u32)), 123);

// 123456789000 * 987654321000 = 121932631112635269000000
assert_eq!(
    Natural::from_str("121932631112635269000000").unwrap()
            .div_exact(Natural::from_str("987654321000").unwrap()),
    123456789000u64
);

type Output = Natural

impl<'a> DivExactAssign<&'a Natural> for Natural

fn div_exact_assign(&mut self, other: &'a Natural)

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by reference. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ x \gets \frac{x}{y}. $$

If you are unsure whether the division will be exact, use self /= &other instead. If you’re unsure and you want to know, use self.div_assign_mod(&other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use self.div_round_assign(&other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExactAssign;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
let mut x = Natural::from(56088u32);
x.div_exact_assign(&Natural::from(456u32));
assert_eq!(x, 123);

// 123456789000 * 987654321000 = 121932631112635269000000
let mut x = Natural::from_str("121932631112635269000000").unwrap();
x.div_exact_assign(&Natural::from_str("987654321000").unwrap());
assert_eq!(x, 123456789000u64);

impl DivExactAssign for Natural

fn div_exact_assign(&mut self, other: Natural)

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value. The first Natural must be exactly divisible by the second. If it isn’t, this function may panic or return a meaningless result.

$$ x \gets \frac{x}{y}. $$

If you are unsure whether the division will be exact, use self /= other instead. If you’re unsure and you want to know, use self.div_assign_mod(other) and check whether the remainder is zero. If you want a function that panics if the division is not exact, use self.div_round_assign(other, RoundingMode::Exact).

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero. May panic if self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::DivExactAssign;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 123 * 456 = 56088
let mut x = Natural::from(56088u32);
x.div_exact_assign(Natural::from(456u32));
assert_eq!(x, 123);

// 123456789000 * 987654321000 = 121932631112635269000000
let mut x = Natural::from_str("121932631112635269000000").unwrap();
x.div_exact_assign(Natural::from_str("987654321000").unwrap());
assert_eq!(x, 123456789000u64);

impl<'a, 'b> DivMod<&'b Natural> for &'a Natural

fn div_mod(self, other: &'b Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by reference and returning the quotient and remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).div_mod(&Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .div_mod(&Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a> DivMod<&'a Natural> for Natural

fn div_mod(self, other: &'a Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by value and the second by reference and returning the quotient and remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    Natural::from(23u32).div_mod(&Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .div_mod(&Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a> DivMod<Natural> for &'a Natural

fn div_mod(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by reference and the second by value and returning the quotient and remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).div_mod(Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .div_mod(Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type ModOutput = Natural

impl DivMod for Natural

fn div_mod(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by value and returning the quotient and remainder. The quotient is rounded towards negative infinity.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivMod;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(Natural::from(23u32).div_mod(Natural::from(10u32)).to_debug_string(), "(2, 3)");

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .div_mod(Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type ModOutput = Natural

impl<'a, 'b> DivRem<&'b Natural> for &'a Natural

fn div_rem(self, other: &'b Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by reference and returning the quotient and remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

For Naturals, div_rem is equivalent to div_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivRem;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).div_rem(&Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .div_rem(&Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type RemOutput = Natural

impl<'a> DivRem<&'a Natural> for Natural

fn div_rem(self, other: &'a Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by value and the second by reference and returning the quotient and remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

For Naturals, div_rem is equivalent to div_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivRem;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    Natural::from(23u32).div_rem(&Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .div_rem(&Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type RemOutput = Natural

impl<'a> DivRem<Natural> for &'a Natural

fn div_rem(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking the first by reference and the second by value and returning the quotient and remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

For Naturals, div_rem is equivalent to div_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivRem;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(
    (&Natural::from(23u32)).div_rem(Natural::from(10u32)).to_debug_string(),
    "(2, 3)"
);

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .div_rem(Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type RemOutput = Natural

impl DivRem for Natural

fn div_rem(self, other: Natural) -> (Natural, Natural)

Divides a Natural by another Natural, taking both by value and returning the quotient and remainder. The quotient is rounded towards zero.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

$$ f(x, y) = \left ( \left \lfloor \frac{x}{y} \right \rfloor, \space x - y\left \lfloor \frac{x}{y} \right \rfloor \right ). $$

For Naturals, div_rem is equivalent to div_mod.

Worst-case complexity

$T(n) = O(n \log n \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero.

Examples

use malachite_base::num::arithmetic::traits::DivRem;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;
use std::str::FromStr;

// 2 * 10 + 3 = 23
assert_eq!(Natural::from(23u32).div_rem(Natural::from(10u32)).to_debug_string(), "(2, 3)");

// 810000006723 * 1234567890987 + 530068894399 = 1000000000000000000000000
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .div_rem(Natural::from_str("1234567890987").unwrap()).to_debug_string(),
    "(810000006723, 530068894399)"
);

type DivOutput = Natural

type RemOutput = Natural

impl<'a, 'b> DivRound<&'b Natural> for &'a Natural

fn div_round(self, other: &'b Natural, rm: RoundingMode) -> (Natural, Ordering)

Divides a Natural by another Natural, taking both by reference and rounding according to a specified rounding mode. An Ordering is also returned, indicating whether the returned value is less than, equal to, or greater than the exact value.

Let $q = \frac{x}{y}$, and let $g$ be the function that just returns the first element of the pair, without the Ordering:

$$ g(x, y, \mathrm{Down}) = g(x, y, \mathrm{Floor}) = \lfloor q \rfloor. $$

$$ g(x, y, \mathrm{Up}) = g(x, y, \mathrm{Ceiling}) = \lceil q \rceil. $$

$$ g(x, y, \mathrm{Nearest}) = \begin{cases} \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor < \frac{1}{2}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor > \frac{1}{2}, \\ \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is even}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is odd.} \end{cases} $$

$g(x, y, \mathrm{Exact}) = q$, but panics if $q \notin \N$.

Then $f(x, y, r) = (g(x, y, r), \operatorname{cmp}(g(x, y, r), q))$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRound, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

assert_eq!(
    (&Natural::from(10u32)).div_round(&Natural::from(4u32), RoundingMode::Down),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(10u32).pow(12)).div_round(&Natural::from(3u32), RoundingMode::Floor),
    (Natural::from(333333333333u64), Ordering::Less)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(&Natural::from(4u32), RoundingMode::Up),
    (Natural::from(3u32), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32).pow(12)).div_round(&Natural::from(3u32), RoundingMode::Ceiling),
    (Natural::from(333333333334u64), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(&Natural::from(5u32), RoundingMode::Exact),
    (Natural::from(2u32), Ordering::Equal)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(&Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(3u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(20u32)).div_round(&Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(7u32), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(&Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(14u32)).div_round(&Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(4u32), Ordering::Greater)
);

type Output = Natural

impl<'a> DivRound<&'a Natural> for Natural

fn div_round(self, other: &'a Natural, rm: RoundingMode) -> (Natural, Ordering)

Divides a Natural by another Natural, taking the first by value and the second by reference and rounding according to a specified rounding mode. An Ordering is also returned, indicating whether the returned value is less than, equal to, or greater than the exact value.

Let $q = \frac{x}{y}$, and let $g$ be the function that just returns the first element of the pair, without the Ordering:

$$ g(x, y, \mathrm{Down}) = g(x, y, \mathrm{Floor}) = \lfloor q \rfloor. $$

$$ g(x, y, \mathrm{Up}) = g(x, y, \mathrm{Ceiling}) = \lceil q \rceil. $$

$$ g(x, y, \mathrm{Nearest}) = \begin{cases} \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor < \frac{1}{2}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor > \frac{1}{2}, \\ \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is even}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is odd.} \end{cases} $$

$g(x, y, \mathrm{Exact}) = q$, but panics if $q \notin \N$.

Then $f(x, y, r) = (g(x, y, r), \operatorname{cmp}(g(x, y, r), q))$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRound, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

assert_eq!(
    Natural::from(10u32).div_round(&Natural::from(4u32), RoundingMode::Down),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    Natural::from(10u32).pow(12).div_round(&Natural::from(3u32), RoundingMode::Floor),
    (Natural::from(333333333333u64), Ordering::Less)
);
assert_eq!(
    Natural::from(10u32).div_round(&Natural::from(4u32), RoundingMode::Up),
    (Natural::from(3u32), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).pow(12).div_round(&Natural::from(3u32), RoundingMode::Ceiling),
    (Natural::from(333333333334u64), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).div_round(&Natural::from(5u32), RoundingMode::Exact),
    (Natural::from(2u32), Ordering::Equal)
);
assert_eq!(
    Natural::from(10u32).div_round(&Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(3u32), Ordering::Less)
);
assert_eq!(
    Natural::from(20u32).div_round(&Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(7u32), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).div_round(&Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    Natural::from(14u32).div_round(&Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(4u32), Ordering::Greater)
);

type Output = Natural

impl<'a> DivRound<Natural> for &'a Natural

fn div_round(self, other: Natural, rm: RoundingMode) -> (Natural, Ordering)

Divides a Natural by another Natural, taking the first by reference and the second by value and rounding according to a specified rounding mode. An Ordering is also returned, indicating whether the returned value is less than, equal to, or greater than the exact value.

Let $q = \frac{x}{y}$, and let $g$ be the function that just returns the first element of the pair, without the Ordering:

$$ g(x, y, \mathrm{Down}) = g(x, y, \mathrm{Floor}) = \lfloor q \rfloor. $$

$$ g(x, y, \mathrm{Up}) = g(x, y, \mathrm{Ceiling}) = \lceil q \rceil. $$

$$ g(x, y, \mathrm{Nearest}) = \begin{cases} \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor < \frac{1}{2}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor > \frac{1}{2}, \\ \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is even}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is odd.} \end{cases} $$

$g(x, y, \mathrm{Exact}) = q$, but panics if $q \notin \N$.

Then $f(x, y, r) = (g(x, y, r), \operatorname{cmp}(g(x, y, r), q))$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRound, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

assert_eq!(
    (&Natural::from(10u32)).div_round(Natural::from(4u32), RoundingMode::Down),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(10u32).pow(12)).div_round(Natural::from(3u32), RoundingMode::Floor),
    (Natural::from(333333333333u64), Ordering::Less)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(Natural::from(4u32), RoundingMode::Up),
    (Natural::from(3u32), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32).pow(12)).div_round(Natural::from(3u32), RoundingMode::Ceiling),
    (Natural::from(333333333334u64), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(Natural::from(5u32), RoundingMode::Exact),
    (Natural::from(2u32), Ordering::Equal)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(3u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(20u32)).div_round(Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(7u32), Ordering::Greater)
);
assert_eq!(
    (&Natural::from(10u32)).div_round(Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    (&Natural::from(14u32)).div_round(Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(4u32), Ordering::Greater)
);

type Output = Natural

impl DivRound for Natural

fn div_round(self, other: Natural, rm: RoundingMode) -> (Natural, Ordering)

Divides a Natural by another Natural, taking both by value and rounding according to a specified rounding mode. An Ordering is also returned, indicating whether the returned value is less than, equal to, or greater than the exact value.

Let $q = \frac{x}{y}$, and let $g$ be the function that just returns the first element of the pair, without the Ordering:

$$ g(x, y, \mathrm{Down}) = g(x, y, \mathrm{Floor}) = \lfloor q \rfloor. $$

$$ g(x, y, \mathrm{Up}) = g(x, y, \mathrm{Ceiling}) = \lceil q \rceil. $$

$$ g(x, y, \mathrm{Nearest}) = \begin{cases} \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor < \frac{1}{2}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor > \frac{1}{2}, \\ \lfloor q \rfloor & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is even}, \\ \lceil q \rceil & \text{if} \quad q - \lfloor q \rfloor = \frac{1}{2} \ \text{and} \ \lfloor q \rfloor \ \text{is odd.} \end{cases} $$

$g(x, y, \mathrm{Exact}) = q$, but panics if $q \notin \N$.

Then $f(x, y, r) = (g(x, y, r), \operatorname{cmp}(g(x, y, r), q))$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRound, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

assert_eq!(
    Natural::from(10u32).div_round(Natural::from(4u32), RoundingMode::Down),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    Natural::from(10u32).pow(12).div_round(Natural::from(3u32), RoundingMode::Floor),
    (Natural::from(333333333333u64), Ordering::Less)
);
assert_eq!(
    Natural::from(10u32).div_round(Natural::from(4u32), RoundingMode::Up),
    (Natural::from(3u32), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).pow(12).div_round(Natural::from(3u32), RoundingMode::Ceiling),
    (Natural::from(333333333334u64), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).div_round(Natural::from(5u32), RoundingMode::Exact),
    (Natural::from(2u32), Ordering::Equal)
);
assert_eq!(
    Natural::from(10u32).div_round(Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(3u32), Ordering::Less)
);
assert_eq!(
    Natural::from(20u32).div_round(Natural::from(3u32), RoundingMode::Nearest),
    (Natural::from(7u32), Ordering::Greater)
);
assert_eq!(
    Natural::from(10u32).div_round(Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(2u32), Ordering::Less)
);
assert_eq!(
    Natural::from(14u32).div_round(Natural::from(4u32), RoundingMode::Nearest),
    (Natural::from(4u32), Ordering::Greater)
);

type Output = Natural

impl<'a> DivRoundAssign<&'a Natural> for Natural

fn div_round_assign(&mut self, other: &'a Natural, rm: RoundingMode) -> Ordering

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by reference and rounding according to a specified rounding mode. An Ordering is returned, indicating whether the assigned value is less than, equal to, or greater than the exact value.

See the DivRound documentation for details.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRoundAssign, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(&Natural::from(4u32), RoundingMode::Down), Ordering::Less);
assert_eq!(n, 2);

let mut n = Natural::from(10u32).pow(12);
assert_eq!(n.div_round_assign(&Natural::from(3u32), RoundingMode::Floor), Ordering::Less);
assert_eq!(n, 333333333333u64);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(&Natural::from(4u32), RoundingMode::Up), Ordering::Greater);
assert_eq!(n, 3);

let mut n = Natural::from(10u32).pow(12);
assert_eq!(
    n.div_round_assign(&Natural::from(3u32), RoundingMode::Ceiling),
    Ordering::Greater
);
assert_eq!(n, 333333333334u64);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(&Natural::from(5u32), RoundingMode::Exact), Ordering::Equal);
assert_eq!(n, 2);

let mut n = Natural::from(10u32);
assert_eq!(
    n.div_round_assign(&Natural::from(3u32), RoundingMode::Nearest),
    Ordering::Less
);
assert_eq!(n, 3);

let mut n = Natural::from(20u32);
assert_eq!(
    n.div_round_assign(&Natural::from(3u32), RoundingMode::Nearest),
    Ordering::Greater
);
assert_eq!(n, 7);

let mut n = Natural::from(10u32);
assert_eq!(
    n.div_round_assign(&Natural::from(4u32), RoundingMode::Nearest),
    Ordering::Less
);
assert_eq!(n, 2);

let mut n = Natural::from(14u32);
assert_eq!(
    n.div_round_assign(&Natural::from(4u32), RoundingMode::Nearest),
    Ordering::Greater
);
assert_eq!(n, 4);

impl DivRoundAssign for Natural

fn div_round_assign(&mut self, other: Natural, rm: RoundingMode) -> Ordering

Divides a Natural by another Natural in place, taking the Natural on the right-hand side by value and rounding according to a specified rounding mode. An Ordering is returned, indicating whether the assigned value is less than, equal to, or greater than the exact value.

See the DivRound documentation for details.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if other is zero, or if rm is Exact but self is not divisible by other.

Examples

use malachite_base::num::arithmetic::traits::{DivRoundAssign, Pow};
use malachite_base::rounding_modes::RoundingMode;
use malachite_nz::natural::Natural;
use std::cmp::Ordering;

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(Natural::from(4u32), RoundingMode::Down), Ordering::Less);
assert_eq!(n, 2);

let mut n = Natural::from(10u32).pow(12);
assert_eq!(n.div_round_assign(Natural::from(3u32), RoundingMode::Floor), Ordering::Less);
assert_eq!(n, 333333333333u64);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(Natural::from(4u32), RoundingMode::Up), Ordering::Greater);
assert_eq!(n, 3);

let mut n = Natural::from(10u32).pow(12);
assert_eq!(
    n.div_round_assign(&Natural::from(3u32), RoundingMode::Ceiling),
    Ordering::Greater
);
assert_eq!(n, 333333333334u64);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(Natural::from(5u32), RoundingMode::Exact), Ordering::Equal);
assert_eq!(n, 2);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(Natural::from(3u32), RoundingMode::Nearest), Ordering::Less);
assert_eq!(n, 3);

let mut n = Natural::from(20u32);
assert_eq!(
    n.div_round_assign(Natural::from(3u32), RoundingMode::Nearest),
    Ordering::Greater
);
assert_eq!(n, 7);

let mut n = Natural::from(10u32);
assert_eq!(n.div_round_assign(Natural::from(4u32), RoundingMode::Nearest), Ordering::Less);
assert_eq!(n, 2);

let mut n = Natural::from(14u32);
assert_eq!(
    n.div_round_assign(Natural::from(4u32), RoundingMode::Nearest),
    Ordering::Greater
);
assert_eq!(n, 4);

impl<'a, 'b> DivisibleBy<&'b Natural> for &'a Natural

fn divisible_by(self, other: &'b Natural) -> bool

Returns whether a Natural is divisible by another Natural; in other words, whether the first is a multiple of the second. Both Naturals are taken by reference.

This means that zero is divisible by any Natural, including zero; but a nonzero Natural is never divisible by zero.

It’s more efficient to use this function than to compute the remainder and check whether it’s zero.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::DivisibleBy;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!((&Natural::ZERO).divisible_by(&Natural::ZERO), true);
assert_eq!((&Natural::from(100u32)).divisible_by(&Natural::from(3u32)), false);
assert_eq!((&Natural::from(102u32)).divisible_by(&Natural::from(3u32)), true);
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .divisible_by(&Natural::from_str("1000000000000").unwrap()),
    true
);

impl<'a> DivisibleBy<&'a Natural> for Natural

fn divisible_by(self, other: &'a Natural) -> bool

Returns whether a Natural is divisible by another Natural; in other words, whether the first is a multiple of the second. The first Naturals is taken by reference and the second by value.

This means that zero is divisible by any Natural, including zero; but a nonzero Natural is never divisible by zero.

It’s more efficient to use this function than to compute the remainder and check whether it’s zero.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::DivisibleBy;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::ZERO.divisible_by(&Natural::ZERO), true);
assert_eq!(Natural::from(100u32).divisible_by(&Natural::from(3u32)), false);
assert_eq!(Natural::from(102u32).divisible_by(&Natural::from(3u32)), true);
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .divisible_by(&Natural::from_str("1000000000000").unwrap()),
    true
);

impl<'a> DivisibleBy<Natural> for &'a Natural

fn divisible_by(self, other: Natural) -> bool

Returns whether a Natural is divisible by another Natural; in other words, whether the first is a multiple of the second. The first Naturals are taken by reference and the second by value.

This means that zero is divisible by any Natural, including zero; but a nonzero Natural is never divisible by zero.

It’s more efficient to use this function than to compute the remainder and check whether it’s zero.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::DivisibleBy;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!((&Natural::ZERO).divisible_by(Natural::ZERO), true);
assert_eq!((&Natural::from(100u32)).divisible_by(Natural::from(3u32)), false);
assert_eq!((&Natural::from(102u32)).divisible_by(Natural::from(3u32)), true);
assert_eq!(
    (&Natural::from_str("1000000000000000000000000").unwrap())
            .divisible_by(Natural::from_str("1000000000000").unwrap()),
    true
);

impl DivisibleBy for Natural

fn divisible_by(self, other: Natural) -> bool

Returns whether a Natural is divisible by another Natural; in other words, whether the first is a multiple of the second. Both Naturals are taken by value.

This means that zero is divisible by any Natural, including zero; but a nonzero Natural is never divisible by zero.

It’s more efficient to use this function than to compute the remainder and check whether it’s zero.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::arithmetic::traits::DivisibleBy;
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(Natural::ZERO.divisible_by(Natural::ZERO), true);
assert_eq!(Natural::from(100u32).divisible_by(Natural::from(3u32)), false);
assert_eq!(Natural::from(102u32).divisible_by(Natural::from(3u32)), true);
assert_eq!(
    Natural::from_str("1000000000000000000000000").unwrap()
            .divisible_by(Natural::from_str("1000000000000").unwrap()),
    true
);

impl<'a> DivisibleByPowerOf2 for &'a Natural

fn divisible_by_power_of_2(self, pow: u64) -> bool

Returns whether a Natural is divisible by $2^k$.

$f(x, k) = (2^k|x)$.

$f(x, k) = (\exists n \in \N : \ x = n2^k)$.

If self is 0, the result is always true; otherwise, it is equivalent to self.trailing_zeros().unwrap() <= pow, but more efficient.

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()).

Examples

use malachite_base::num::arithmetic::traits::{DivisibleByPowerOf2, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_nz::natural::Natural;

assert_eq!(Natural::ZERO.divisible_by_power_of_2(100), true);
assert_eq!(Natural::from(100u32).divisible_by_power_of_2(2), true);
assert_eq!(Natural::from(100u32).divisible_by_power_of_2(3), false);
assert_eq!(Natural::from(10u32).pow(12).divisible_by_power_of_2(12), true);
assert_eq!(Natural::from(10u32).pow(12).divisible_by_power_of_2(13), false);

impl DoubleFactorial for Natural

fn double_factorial(n: u64) -> Natural

Computes the double factorial of a number.

$$ f(n) = n!! = n \times (n - 2) \times (n - 4) \times \cdots \times i, $$ where $i$ is 1 if $n$ is odd and $2$ if $n$ is even.

$n!! = O(\sqrt{n}(n/e)^{n/2})$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

Examples

use malachite_base::num::arithmetic::traits::DoubleFactorial;
use malachite_nz::natural::Natural;

assert_eq!(Natural::double_factorial(0), 1);
assert_eq!(Natural::double_factorial(1), 1);
assert_eq!(Natural::double_factorial(2), 2);
assert_eq!(Natural::double_factorial(3), 3);
assert_eq!(Natural::double_factorial(4), 8);
assert_eq!(Natural::double_factorial(5), 15);
assert_eq!(Natural::double_factorial(6), 48);
assert_eq!(Natural::double_factorial(7), 105);
assert_eq!(
    Natural::double_factorial(99).to_string(),
    "2725392139750729502980713245400918633290796330545803413734328823443106201171875"
);
assert_eq!(
    Natural::double_factorial(100).to_string(),
    "34243224702511976248246432895208185975118675053719198827915654463488000000000000"
);

This is equivalent to mpz_2fac_ui from mpz/2fac_ui.c, GMP 6.2.1.

impl EqAbs<Natural> for i128

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for i16

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for i32

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for i64

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for i8

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for isize

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive signed integer and a Natural are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for u128

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for u16

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for u32

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for u64

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for u8

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<Natural> for usize

fn eq_abs(&self, other: &Natural) -> bool

Determines whether the absolute values of a primitive unsigned integer and a Natural are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<i128> for Natural

fn eq_abs(&self, other: &i128) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<i16> for Natural

fn eq_abs(&self, other: &i16) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<i32> for Natural

fn eq_abs(&self, other: &i32) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<i64> for Natural

fn eq_abs(&self, other: &i64) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<i8> for Natural

fn eq_abs(&self, other: &i8) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<isize> for Natural

fn eq_abs(&self, other: &isize) -> bool

Determines whether the absolute values of a Natural and a primitive signed integer are equal.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<u128> for Natural

fn eq_abs(&self, other: &u128) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<u16> for Natural

fn eq_abs(&self, other: &u16) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<u32> for Natural

fn eq_abs(&self, other: &u32) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<u64> for Natural

fn eq_abs(&self, other: &u64) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<u8> for Natural

fn eq_abs(&self, other: &u8) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl EqAbs<usize> for Natural

fn eq_abs(&self, other: &usize) -> bool

Determines whether the absolute values of a Natural and a primitive unsigned integer are equal.

Since both values are non-negative, this is the same as ordinary equality.

Worst-case complexity

Constant time and additional memory.

See here.

fn ne_abs(&self, other: &Rhs) -> bool

Compares the absolute values of two numbers for inequality, taking both by reference.

impl<'a, 'b, 'c> EqMod<&'b Integer, &'c Natural> for &'a Integer

fn eq_mod(self, other: &'b Integer, m: &'c Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. All three numbers are taken by reference.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Integer::from(123)).eq_mod(&Integer::from(223), &Natural::from(100u32)),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        &Integer::from_str("-999999012346").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        &Integer::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<&'a Integer, &'b Natural> for Integer

fn eq_mod(self, other: &'a Integer, m: &'b Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first number is taken by value and the second and third by reference.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Integer::from(123).eq_mod(&Integer::from(223), &Natural::from(100u32)),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        &Integer::from_str("-999999012346").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        &Integer::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<&'b Integer, Natural> for &'a Integer

fn eq_mod(self, other: &'b Integer, m: Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first two numbers are taken by reference and the third by value.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Integer::from(123)).eq_mod(&Integer::from(223), Natural::from(100u32)),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        &Integer::from_str("-999999012346").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        &Integer::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<&'a Integer, Natural> for Integer

fn eq_mod(self, other: &'a Integer, m: Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first and third numbers are taken by value and the second by reference.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Integer::from(123).eq_mod(&Integer::from(223), Natural::from(100u32)),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        &Integer::from_str("-999999012346").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        &Integer::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<&'a Natural> for Natural

fn eq_mod(self, other: &'a Natural, m: Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first and third are taken by value and the second by reference.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from(123u32).eq_mod(&Natural::from(223u32), Natural::from(100u32)),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        &Natural::from_str("2000000987654").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        &Natural::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b, 'c> EqMod<&'b Natural, &'c Natural> for &'a Natural

fn eq_mod(self, other: &'b Natural, m: &'c Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. All three are taken by reference.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Natural::from(123u32)).eq_mod(&Natural::from(223u32), &Natural::from(100u32)),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        &Natural::from_str("2000000987654").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        &Natural::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<&'a Natural, &'b Natural> for Natural

fn eq_mod(self, other: &'a Natural, m: &'b Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first is taken by value and the second and third by reference.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from(123u32).eq_mod(&Natural::from(223u32), &Natural::from(100u32)),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        &Natural::from_str("2000000987654").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        &Natural::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<&'b Natural, Natural> for &'a Natural

fn eq_mod(self, other: &'b Natural, m: Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first and second are taken by reference and the third by value.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Natural::from(123u32)).eq_mod(&Natural::from(223u32), Natural::from(100u32)),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        &Natural::from_str("2000000987654").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        &Natural::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<Integer, &'b Natural> for &'a Integer

fn eq_mod(self, other: Integer, m: &'b Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first and third numbers are taken by reference and the third by value.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Integer::from(123)).eq_mod(Integer::from(223), &Natural::from(100u32)),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        Integer::from_str("-999999012346").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        Integer::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<Integer, &'a Natural> for Integer

fn eq_mod(self, other: Integer, m: &'a Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first two numbers are taken by value and the third by reference.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Integer::from(123).eq_mod(Integer::from(223), &Natural::from(100u32)),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        Integer::from_str("-999999012346").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        Integer::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<Integer, Natural> for &'a Integer

fn eq_mod(self, other: Integer, m: Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. The first number is taken by reference and the second and third by value.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Integer::from(123)).eq_mod(Integer::from(223), Natural::from(100u32)),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        Integer::from_str("-999999012346").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Integer::from_str("1000000987654").unwrap()).eq_mod(
        Integer::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl EqMod<Integer, Natural> for Integer

fn eq_mod(self, other: Integer, m: Natural) -> bool

Returns whether an Integer is equivalent to another Integer modulo a Natural; that is, whether the difference between the two Integers is a multiple of the Natural. All three numbers are taken by value.

Two Integers are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Integer::from(123).eq_mod(Integer::from(223), Natural::from(100u32)),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        Integer::from_str("-999999012346").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Integer::from_str("1000000987654").unwrap().eq_mod(
        Integer::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqMod<Natural, &'b Natural> for &'a Natural

fn eq_mod(self, other: Natural, m: &'b Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first and third are taken by reference and the second by value.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Natural::from(123u32)).eq_mod(Natural::from(223u32), &Natural::from(100u32)),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        Natural::from_str("2000000987654").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        Natural::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<Natural, &'a Natural> for Natural

fn eq_mod(self, other: Natural, m: &'a Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first two are taken by value and the third by reference.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from(123u32).eq_mod(Natural::from(223u32), &Natural::from(100u32)),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        Natural::from_str("2000000987654").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        Natural::from_str("2000000987655").unwrap(),
        &Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a> EqMod<Natural, Natural> for &'a Natural

fn eq_mod(self, other: Natural, m: Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. The first is taken by reference and the second and third by value.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    (&Natural::from(123u32)).eq_mod(Natural::from(223u32), Natural::from(100u32)),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        Natural::from_str("2000000987654").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    (&Natural::from_str("1000000987654").unwrap()).eq_mod(
        Natural::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl EqMod for Natural

fn eq_mod(self, other: Natural, m: Natural) -> bool

Returns whether a Natural is equivalent to another Natural modulo a third; that is, whether the difference between the first two is a multiple of the third. All three are taken by value.

Two Naturals are equal to each other modulo 0 iff they are equal.

$f(x, y, m) = (x \equiv y \mod m)$.

$f(x, y, m) = (\exists k \in \Z : x - y = km)$.

Worst-case complexity

$T(n) = O(n \log n \log \log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::EqMod;
use malachite_nz::natural::Natural;
use std::str::FromStr;

assert_eq!(
    Natural::from(123u32).eq_mod(Natural::from(223u32), Natural::from(100u32)),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        Natural::from_str("2000000987654").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    true
);
assert_eq!(
    Natural::from_str("1000000987654").unwrap().eq_mod(
        Natural::from_str("2000000987655").unwrap(),
        Natural::from_str("1000000000000").unwrap()
    ),
    false
);

impl<'a, 'b> EqModPowerOf2<&'b Natural> for &'a Natural

fn eq_mod_power_of_2(self, other: &'b Natural, pow: u64) -> bool

Returns whether one Natural is equal to another modulo $2^k$; that is, whether their $k$ least-significant bits 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::natural::Natural;

assert_eq!((&Natural::ZERO).eq_mod_power_of_2(&Natural::from(256u32), 8), true);
assert_eq!(
    (&Natural::from(0b1101u32)).eq_mod_power_of_2(&Natural::from(0b10101u32), 3),
    true
);
assert_eq!(
    (&Natural::from(0b1101u32)).eq_mod_power_of_2(&Natural::from(0b10101u32), 4),
    false
);

impl<'a, 'b> ExtendedGcd<&'a Natural> for &'b Natural

fn extended_gcd(self, other: &'a Natural) -> (Natural, Integer, Integer)

Computes the GCD (greatest common divisor) of two Naturals $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$. Both Naturals are taken by reference.

The are infinitely many $x$, $y$ that satisfy the identity for any $a$, $b$, so the full specification is more detailed:

• $f(0, 0) = (0, 0, 0)$.
• $f(a, ak) = (a, 1, 0)$ if $a > 0$ and $k \neq 1$.
• $f(bk, b) = (b, 0, 1)$ if $b > 0$.
• $f(a, b) = (g, x, y)$ if $a \neq 0$ and $b \neq 0$ and $\gcd(a, b) \neq \min(a, b)$, where $g = \gcd(a, b) \geq 0$, $ax + by = g$, $x \leq \lfloor b/g \rfloor$, and $y \leq \lfloor a/g \rfloor$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::ExtendedGcd;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    (&Natural::from(3u32)).extended_gcd(&Natural::from(5u32)).to_debug_string(),
    "(1, 2, -1)"
);
assert_eq!(
    (&Natural::from(240u32)).extended_gcd(&Natural::from(46u32)).to_debug_string(),
    "(2, -9, 47)"
);

type Gcd = Natural

type Cofactor = Integer

impl<'a> ExtendedGcd<&'a Natural> for Natural

fn extended_gcd(self, other: &'a Natural) -> (Natural, Integer, Integer)

Computes the GCD (greatest common divisor) of two Naturals $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$. The first Natural is taken by value and the second by reference.

The are infinitely many $x$, $y$ that satisfy the identity for any $a$, $b$, so the full specification is more detailed:

• $f(0, 0) = (0, 0, 0)$.
• $f(a, ak) = (a, 1, 0)$ if $a > 0$ and $k \neq 1$.
• $f(bk, b) = (b, 0, 1)$ if $b > 0$.
• $f(a, b) = (g, x, y)$ if $a \neq 0$ and $b \neq 0$ and $\gcd(a, b) \neq \min(a, b)$, where $g = \gcd(a, b) \geq 0$, $ax + by = g$, $x \leq \lfloor b/g \rfloor$, and $y \leq \lfloor a/g \rfloor$.

Worst-case complexity

$T(n) = O(n (\log n)^2 \log\log n)$

$M(n) = O(n \log n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), other.significant_bits()).

Examples

use malachite_base::num::arithmetic::traits::ExtendedGcd;
use malachite_base::strings::ToDebugString;
use malachite_nz::natural::Natural;

assert_eq!(
    Natural::from(3u32).extended_gcd(&Natural::from(5u32)).to_debug_string(),
    "(1, 2, -1)"
);
assert_eq!(
    Natural::from(240u32).extended_gcd(&Natural::from(46u32)).to_debug_string(),
    "(2, -9, 47)"
);

type Gcd =