Trait 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>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so 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