Trait malachite_base::num::arithmetic::traits::Gcd

source · 
pub trait Gcd<RHS = Self> {
    type Output;

    fn gcd(self, other: RHS) -> Self::Output;
}
Expand description

Calculates the GCD (greatest common divisor) of two numbers.

Required Associated Types§

Required Methods§

Implementations on Foreign Types§

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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.

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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.

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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.

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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.

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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.

Computes the GCD (greatest common divisor) of two numbers.

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”.

$$ f(x, y) = \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§