Trait malachite_base::num::arithmetic::traits::CheckedBinomialCoefficient

pub trait CheckedBinomialCoefficient<T = Self>: Sized {
    // Required method
    fn checked_binomial_coefficient(n: T, k: T) -> Option<Self>;
}

Required Methods

fn checked_binomial_coefficient(n: T, k: T) -> Option<Self>

Object Safety

This trait is not object safe.

Implementations on Foreign Types

impl CheckedBinomialCoefficient for i8

fn checked_binomial_coefficient(n: i8, k: i8) -> Option<i8>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for i16

fn checked_binomial_coefficient(n: i16, k: i16) -> Option<i16>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for i32

fn checked_binomial_coefficient(n: i32, k: i32) -> Option<i32>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for i64

fn checked_binomial_coefficient(n: i64, k: i64) -> Option<i64>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for i128

fn checked_binomial_coefficient(n: i128, k: i128) -> Option<i128>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for isize

fn checked_binomial_coefficient(n: isize, k: isize) -> Option<isize>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

The second argument must be non-negative, but the first may be negative. If it is, the identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad n \geq 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{Some}((-1)^k \binom{-n+k-1}{k}) & \text{if} \quad n < 0 \ \text{and} \ -2^{W-1} \leq \binom{n}{k} < 2^{W-1}, \\ \operatorname{None} & \quad \text{otherwise}, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.abs().

Examples

See here.

impl CheckedBinomialCoefficient for u8

fn checked_binomial_coefficient(n: u8, k: u8) -> Option<u8>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

impl CheckedBinomialCoefficient for u16

fn checked_binomial_coefficient(n: u16, k: u16) -> Option<u16>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

impl CheckedBinomialCoefficient for u32

fn checked_binomial_coefficient(n: u32, k: u32) -> Option<u32>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

impl CheckedBinomialCoefficient for u64

fn checked_binomial_coefficient(n: u64, k: u64) -> Option<u64>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

impl CheckedBinomialCoefficient for u128

fn checked_binomial_coefficient(n: u128, k: u128) -> Option<u128>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

impl CheckedBinomialCoefficient for usize

fn checked_binomial_coefficient(n: usize, k: usize) -> Option<usize>

Computes the binomial coefficient of two numbers. If the inputs are too large, the function returns None.

$$ f(n, k) = \begin{cases} \operatorname{Some}(\binom{n}{k}) & \text{if} \quad \binom{n}{k} < 2^W, \\ \operatorname{None} & \text{if} \quad \binom{n}{k} \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

Worst-case complexity

$T(k) = O(k)$

$M(k) = O(1)$

where $T$ is time, $M$ is additional memory, and $k$ is k.

Examples

See here.

Implementors