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

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.

## 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()).

See here.