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

Implementations on Foreign Types

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Implementors