Aleph::ModularCombinatorics Class Reference

Combinatorics operations modulo a prime. More...

#include <modular_combinatorics.H>

Collaboration diagram for Aleph::ModularCombinatorics:

Public Member Functions
	ModularCombinatorics (size_t max_n, const uint64_t p)
	Precomputes factorials up to 'max_n' modulo 'p'.
uint64_t	nCk (const uint64_t n, const uint64_t k) const
	Calculate nCk modulo p in O(1).
uint64_t	lucas_nCk (const uint64_t n, const uint64_t k) const
	Calculate nCk modulo p using Lucas' theorem.

Private Attributes
uint64_t	mod_
	Prime modulus.
Array< uint64_t >	fact_
	Precomputed factorials.
Array< uint64_t >	invFact_
	Precomputed inverse factorials.

Detailed Description

Combinatorics operations modulo a prime.

Precomputes factorials and inverse factorials up to a certain range to allow O(1) computation of combinations. Supports large n, k through Lucas' Theorem.

Definition at line 56 of file modular_combinatorics.H.

Constructor & Destructor Documentation

ModularCombinatorics()

Aleph::ModularCombinatorics::ModularCombinatorics ( size_t  max_n, const uint64_t  p  )

inline

Precomputes factorials up to 'max_n' modulo 'p'.

Parameters

[in]	max_n	Maximum value for factorials to precompute.
[in]	p	Prime modulus.

Precondition

p is a prime number.

Exceptions

std::invalid_argument

if p is not prime.

Definition at line 70 of file modular_combinatorics.H.

References ah_invalid_argument_if, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), fact_, invFact_, Aleph::miller_rabin(), mod_, Aleph::mod_inv(), Aleph::mod_mul(), Aleph::Array< T >::putn(), and Aleph::Array< T >::reserve().

Member Function Documentation

lucas_nCk()

uint64_t Aleph::ModularCombinatorics::lucas_nCk ( const uint64_t  n, const uint64_t  k  ) const

inline

Calculate nCk modulo p using Lucas' theorem.

Provides an efficient way to compute combinations when n and k are large but the modulus p is relatively small.

Precondition

Internal nCk calls require precomputation up to mod_ - 1 (ensured if constructor's max_n >= mod_ - 1).

Parameters

[in]	n	Total number of items.
[in]	k	Number of items to choose.

Returns

nCk % p.

Note

Complexity: O(p + log_p n).

Exceptions

ah_out_of_range_error

if sub-problem exceeds precomputed range.

Definition at line 127 of file modular_combinatorics.H.

References Aleph::divide_and_conquer_partition_dp(), k, lucas_nCk(), mod_, Aleph::mod_mul(), and nCk().

Referenced by lucas_nCk().

nCk()

uint64_t Aleph::ModularCombinatorics::nCk ( const uint64_t  n, const uint64_t  k  ) const

inline

Calculate nCk modulo p in O(1).

Computes the binomial coefficient (n choose k) modulo p using precomputed factorials.

Parameters

[in]	n	Total number of items.
[in]	k	Number of items to choose.

Returns

nCk % p.

Note

Requires n < fact_.size() (precomputed range).

Exceptions

ah_out_of_range_error

if n exceeds precomputed range.

Definition at line 102 of file modular_combinatorics.H.

References ah_out_of_range_error_if, Aleph::divide_and_conquer_partition_dp(), fact_, invFact_, k, mod_, Aleph::mod_mul(), and Aleph::Array< T >::size().

Referenced by lucas_nCk().

Member Data Documentation

fact_

Array<uint64_t> Aleph::ModularCombinatorics::fact_

private

Precomputed factorials.

Definition at line 59 of file modular_combinatorics.H.

Referenced by ModularCombinatorics(), and nCk().

invFact_

Array<uint64_t> Aleph::ModularCombinatorics::invFact_

private

Precomputed inverse factorials.

Definition at line 60 of file modular_combinatorics.H.

Referenced by ModularCombinatorics(), and nCk().

mod_

uint64_t Aleph::ModularCombinatorics::mod_

private

Prime modulus.

Definition at line 58 of file modular_combinatorics.H.

Referenced by ModularCombinatorics(), lucas_nCk(), and nCk().

---

The documentation for this class was generated from the following file:

• modular_combinatorics.H