binomial_coefficient.cpp File Reference

Primary module interface unit for module binomial_coefficient. More...

#include <algorithm>
#include <cassert>
#include <vector>
import prime_decomposition;
import modulo;
import prime_test;
import chinese_remainder;
import base;

Include dependency graph for binomial_coefficient.cpp:

Functions
template<Integer T>
constexpr T	ntlib::binom (T n, T k) noexcept
	Computes a single binomial coefficient.
template<Integer T>
constexpr T	ntlib::mod_p_binom (T n, T k, T p) noexcept
	Compute a single binomial coefficient module a sufficiently large prime.
template<Integer T>
constexpr T	ntlib::mod_pp_binom (T n, T k, T p, T e)
	Computes a single binomial coefficient modulo a prime power.
template<Integer T>
constexpr T	ntlib::mod_binom (T n, T k, T m)
	Computes a single binomial coefficient modulo an arbitrary number.
template<Integer T>
constexpr std::vector< std::vector< T > >	ntlib::binom_table (T N)
	Computes the first \(N\) rows of Pascal's triangle.
template<Integer T>
constexpr std::vector< std::vector< T > >	ntlib::mod_binom_table (std::size_t N, T m)
	Computes the first \(N\) rows of Pascal's triangle module some number \(m\).

Detailed Description

Primary module interface unit for module binomial_coefficient.

Function Documentation

binom()

template<Integer T>

T ntlib::binom ( T n, T k )

nodiscardconstexprexportnoexcept

Computes a single binomial coefficient.

Intermediate results are at most \(k\) times as big as the result.

Runtime: \(O(k)\)

Template Parameters

T	An integer-like type.

Parameters

n	Size of universe.
k	Size of the subsets.

Returns

The binomial coefficient \({n \choose k}\).

binom_table()

template<Integer T>

std::vector< std::vector< T > > ntlib::binom_table ( T N )

nodiscardconstexprexport

Computes the first \(N\) rows of Pascal's triangle.

Computes a table of all binomial coefficiets \({i \choose j}\) with \(0 \leq i,j \leq N\).

Intermediate results do not exceed the final results.

Runtime: \(O(N^2)\)

Template Parameters

T	An integer-like type.

Parameters

N	The number of rows to compute.

Returns

Two-dimensional std::vector containing the binomial coefficients.

mod_binom()

template<Integer T>

T ntlib::mod_binom ( T n, T k, T m )

nodiscardconstexprexport

Computes a single binomial coefficient modulo an arbitrary number.

Template Parameters

T	An integer-like type.

Parameters

n	The size of the universe.
k	The size of the subsets.
m	The modulus.

Returns

The binomial coefficient \({n \choose k} \mod m\).

mod_binom_table()

template<Integer T>

std::vector< std::vector< T > > ntlib::mod_binom_table ( std::size_t N, T m )

nodiscardconstexprexport

Computes the first \(N\) rows of Pascal's triangle module some number \(m\).

Computes a table of all binomial coefficiets \({i \choose j} \mod m\) with \(0 \leq i,j \leq N\).

Runtime: \(O(N^2)\)

Template Parameters

T	An integer-like type.

Parameters

N	The number of rows to compute.
m	The modulus.

Returns

Two-dimensional std::vector containing the binomial coefficients.

mod_p_binom()

template<Integer T>

T ntlib::mod_p_binom ( T n, T k, T p )

nodiscardconstexprexportnoexcept

Compute a single binomial coefficient module a sufficiently large prime.

To compute \({n \choose k} \mod p\) we need \(p > \max\{k, n-k\}\).

Template Parameters

T	An integer-like type.

Parameters

n	Size of the universe.
k	Size of the subsets.
p	The modulus. Must be prime and sufficiently large.

Returns

The binomial coefficient \({n \choose k} \mod p\).

mod_pp_binom()

template<Integer T>

T ntlib::mod_pp_binom ( T n, T k, T p, T e )

nodiscardconstexprexport

Computes a single binomial coefficient modulo a prime power.

For a prime \(p\) and a positive integer \(e\) this computes \({n \choose k} \mod p^e\).

Template Parameters

T	An integer-like type.

Parameters

n	Size of universe.
k	Size of the subsets.
p	A prime number.
e	The exponent of the prime.

Returns

The binomial coefficient \({n \choose k} \mod p^e\).