Trait malachite_base::num::arithmetic::traits::GcdAssign

source · [−]
pub trait GcdAssign<RHS = Self> {
    fn gcd_assign(&mut self, other: RHS);
}
Expand description

Replaces a number with the GCD (greatest common divisor) of it and another number.

Required Methods

Implementations on Foreign Types

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Replaces another with the GCD (greatest common divisor) of it and another number.

The GCD of 0 and $n$, for any $n$, is 0. In particular, $\gcd(0, 0) = 0$, which makes sense if we interpret “greatest” to mean “greatest by the divisibility order”.

$$ x \gets \gcd(x, y). $$

Worst-case complexity

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

$M(n) = O(n)$

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

Examples

See here.

Implementors