Trait malachite_base::num::arithmetic::traits::ExtendedGcd
source · [−]pub trait ExtendedGcd<RHS = Self> {
type Gcd;
type Cofactor;
fn extended_gcd(
self,
other: RHS
) -> (Self::Gcd, Self::Cofactor, Self::Cofactor);
}
Expand description
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
The are infinitely many $x$, $y$ that satisfy the identity, 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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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$.
Required Associated Types
Required Methods
fn extended_gcd(self, other: RHS) -> (Self::Gcd, Self::Cofactor, Self::Cofactor)
Implementations on Foreign Types
sourceimpl ExtendedGcd<u8> for u8
impl ExtendedGcd<u8> for u8
sourcefn extended_gcd(self, other: u8) -> (u8, i8, i8)
fn extended_gcd(self, other: u8) -> (u8, i8, i8)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = u8
type Cofactor = i8
sourceimpl ExtendedGcd<i8> for i8
impl ExtendedGcd<i8> for i8
sourcefn extended_gcd(self, other: i8) -> (u8, i8, i8)
fn extended_gcd(self, other: i8) -> (u8, i8, i8)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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 Gcd = u8
type Cofactor = i8
sourceimpl ExtendedGcd<u16> for u16
impl ExtendedGcd<u16> for u16
sourcefn extended_gcd(self, other: u16) -> (u16, i16, i16)
fn extended_gcd(self, other: u16) -> (u16, i16, i16)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = u16
type Cofactor = i16
sourceimpl ExtendedGcd<i16> for i16
impl ExtendedGcd<i16> for i16
sourcefn extended_gcd(self, other: i16) -> (u16, i16, i16)
fn extended_gcd(self, other: i16) -> (u16, i16, i16)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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 Gcd = u16
type Cofactor = i16
sourceimpl ExtendedGcd<u32> for u32
impl ExtendedGcd<u32> for u32
sourcefn extended_gcd(self, other: u32) -> (u32, i32, i32)
fn extended_gcd(self, other: u32) -> (u32, i32, i32)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = u32
type Cofactor = i32
sourceimpl ExtendedGcd<i32> for i32
impl ExtendedGcd<i32> for i32
sourcefn extended_gcd(self, other: i32) -> (u32, i32, i32)
fn extended_gcd(self, other: i32) -> (u32, i32, i32)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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 Gcd = u32
type Cofactor = i32
sourceimpl ExtendedGcd<u64> for u64
impl ExtendedGcd<u64> for u64
sourcefn extended_gcd(self, other: u64) -> (u64, i64, i64)
fn extended_gcd(self, other: u64) -> (u64, i64, i64)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = u64
type Cofactor = i64
sourceimpl ExtendedGcd<i64> for i64
impl ExtendedGcd<i64> for i64
sourcefn extended_gcd(self, other: i64) -> (u64, i64, i64)
fn extended_gcd(self, other: i64) -> (u64, i64, i64)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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 Gcd = u64
type Cofactor = i64
sourceimpl ExtendedGcd<u128> for u128
impl ExtendedGcd<u128> for u128
sourcefn extended_gcd(self, other: u128) -> (u128, i128, i128)
fn extended_gcd(self, other: u128) -> (u128, i128, i128)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = u128
type Cofactor = i128
sourceimpl ExtendedGcd<i128> for i128
impl ExtendedGcd<i128> for i128
sourcefn extended_gcd(self, other: i128) -> (u128, i128, i128)
fn extended_gcd(self, other: i128) -> (u128, i128, i128)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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 Gcd = u128
type Cofactor = i128
sourceimpl ExtendedGcd<usize> for usize
impl ExtendedGcd<usize> for usize
sourcefn extended_gcd(self, other: usize) -> (usize, isize, isize)
fn extended_gcd(self, other: usize) -> (usize, isize, isize)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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^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 Gcd = usize
type Cofactor = isize
sourceimpl ExtendedGcd<isize> for isize
impl ExtendedGcd<isize> for isize
sourcefn extended_gcd(self, other: isize) -> (usize, isize, isize)
fn extended_gcd(self, other: isize) -> (usize, isize, isize)
Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients $x$ and $y$ in Bézout’s identity $ax+by=\gcd(a,b)$.
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(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
- $f(bk, b) = (b, 0, 1)$ if $b > 0$.
- $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^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.