Trait malachite_base::num::arithmetic::traits::Gcd
source · [−]Expand description
Calculates the GCD (greatest common divisor) of two numbers.
Required Associated Types
Required Methods
Implementations on Foreign Types
sourceimpl Gcd<u8> for u8
impl Gcd<u8> for u8
sourcefn gcd(self, other: u8) -> u8
fn gcd(self, other: u8) -> u8
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.
type Output = u8
sourceimpl Gcd<u16> for u16
impl Gcd<u16> for u16
sourcefn gcd(self, other: u16) -> u16
fn gcd(self, other: u16) -> u16
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.
type Output = u16
sourceimpl Gcd<u32> for u32
impl Gcd<u32> for u32
sourcefn gcd(self, other: u32) -> u32
fn gcd(self, other: u32) -> u32
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.
type Output = u32
sourceimpl Gcd<u64> for u64
impl Gcd<u64> for u64
sourcefn gcd(self, other: u64) -> u64
fn gcd(self, other: u64) -> u64
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.
type Output = u64
sourceimpl Gcd<u128> for u128
impl Gcd<u128> for u128
sourcefn gcd(self, other: u128) -> u128
fn gcd(self, other: u128) -> u128
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.
type Output = u128
sourceimpl Gcd<usize> for usize
impl Gcd<usize> for usize
sourcefn gcd(self, other: usize) -> usize
fn gcd(self, other: usize) -> usize
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.