Trait malachite_base::num::arithmetic::traits::ExtendedGcd

pub trait ExtendedGcd<RHS = Self> {
    type Gcd;
    type Cofactor;

    // Required method
    fn extended_gcd(
        self,
        other: RHS
    ) -> (Self::Gcd, Self::Cofactor, Self::Cofactor);
}

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

type Gcd

type Cofactor

Required Methods

fn extended_gcd(self, other: RHS) -> (Self::Gcd, Self::Cofactor, Self::Cofactor)

Implementations on Foreign Types

impl ExtendedGcd for 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

impl ExtendedGcd for 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

impl ExtendedGcd for 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

impl ExtendedGcd for 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

impl ExtendedGcd for 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

impl ExtendedGcd for 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.

type Gcd = usize

type Cofactor = isize

impl ExtendedGcd for u8

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

impl ExtendedGcd for u16

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

impl ExtendedGcd for u32

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

impl ExtendedGcd for u64

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

impl ExtendedGcd for u128

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

impl ExtendedGcd for usize

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

Implementors