Trait Binomial 

pub trait Binomial: Sized {
    // Required methods
    fn multinomial2(k: &[Self]) -> Self;
    fn binomial2(n: Self, k: Self) -> Self;
    fn binomial4(n: Self, k: Self) -> Self;
    fn binomial4_rec(n: Self, k: Self) -> Self;
    fn multinomial_odd(p: ValidPrime, l: &mut [Self]) -> Self;
    fn binomial_odd(p: ValidPrime, n: Self, k: Self) -> Self;
    fn binomial_odd_is_zero(p: ValidPrime, n: Self, k: Self) -> bool;

    // Provided methods
    fn multinomial(p: ValidPrime, l: &mut [Self]) -> Self { ... }
    fn binomial(p: ValidPrime, n: Self, k: Self) -> Self { ... }
}

A number satisfying the Binomial trait supports computing various binomial coefficients. This is implemented using a macro, since the implementation for all types is syntactically the same.

Required Methods

fn multinomial2(k: &[Self]) -> Self

mod 2 multinomial coefficient

fn binomial2(n: Self, k: Self) -> Self

mod 2 binomial coefficient n choose k

fn binomial4(n: Self, k: Self) -> Self

Binomial coefficients mod 4. We pre-compute the coefficients for small values of n. For large n, we recursively use the fact that if n = 2^k + l, l < 2^k, then

n choose r = l choose r + 2 (l choose (r - 2^{k - 1})) + (l choose (r - 2^k))

This is easy to verify using the fact that

(x + y)^{2^k} = x^{2^k} + 2 x^{2^{k - 1}} y^{2^{k - 1}} + y^{2^k}

fn binomial4_rec(n: Self, k: Self) -> Self

Compute binomial coefficients mod 4 using the recursion relation in the documentation of Binomial::binomial4. This calls into binomial4 instead of binomial4_rec. The main purpose of this is to separate out the logic for testing.

fn multinomial_odd(p: ValidPrime, l: &mut [Self]) -> Self

Computes the multinomial coefficient mod p using Lucas’ theorem. This modifies the underlying list. For p = 2 it is more efficient to use multinomial2

fn binomial_odd(p: ValidPrime, n: Self, k: Self) -> Self

Compute odd binomial coefficients mod p, where p is odd. For p = 2 it is more efficient to use binomial2

fn binomial_odd_is_zero(p: ValidPrime, n: Self, k: Self) -> bool

Checks whether n choose k is zero mod p. Since we don’t have to compute the value, this is faster than binomial_odd.

Provided Methods

fn multinomial(p: ValidPrime, l: &mut [Self]) -> Self

Multinomial coefficient of the list l

fn binomial(p: ValidPrime, n: Self, k: Self) -> Self

Binomial coefficient n choose k.

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 Binomial for i32

fn multinomial2(l: &[Self]) -> Self

fn binomial2(n: Self, k: Self) -> Self

fn multinomial_odd(p_: ValidPrime, l: &mut [Self]) -> Self

fn binomial_odd(p_: ValidPrime, n: Self, k: Self) -> Self

fn binomial_odd_is_zero(p: ValidPrime, n: Self, k: Self) -> bool

fn binomial4(n: Self, j: Self) -> Self

fn binomial4_rec(n: Self, j: Self) -> Self

impl Binomial for u16

fn multinomial2(l: &[Self]) -> Self

fn binomial2(n: Self, k: Self) -> Self

fn multinomial_odd(p_: ValidPrime, l: &mut [Self]) -> Self

fn binomial_odd(p_: ValidPrime, n: Self, k: Self) -> Self

fn binomial_odd_is_zero(p: ValidPrime, n: Self, k: Self) -> bool

fn binomial4(n: Self, j: Self) -> Self

fn binomial4_rec(n: Self, j: Self) -> Self

impl Binomial for u32

fn multinomial2(l: &[Self]) -> Self

fn binomial2(n: Self, k: Self) -> Self

fn multinomial_odd(p_: ValidPrime, l: &mut [Self]) -> Self

fn binomial_odd(p_: ValidPrime, n: Self, k: Self) -> Self

fn binomial_odd_is_zero(p: ValidPrime, n: Self, k: Self) -> bool

fn binomial4(n: Self, j: Self) -> Self

fn binomial4_rec(n: Self, j: Self) -> Self

Implementors