Aleph::ModularCombinatorics Class Reference

High-performance 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)
	Construct and precompute factorials up to 'max_n' modulo 'p'.
uint64_t	nCk (const uint64_t n, const uint64_t k) const
	Calculate \(\binom{n}{k} \pmod{P}\)in constant time.
uint64_t	lucas_nCk (const uint64_t n, const uint64_t k) const
	Calculate \(\binom{n}{k} \pmod{P}\)using Lucas' Theorem.

Private Attributes
uint64_t	mod_
	Prime modulus \(P\).
Array< uint64_t >	fact_
	Precomputed factorials array.
Array< uint64_t >	invFact_
	Precomputed inverse factorials array.

Detailed Description

High-performance combinatorics operations modulo a prime.

The ModularCombinatorics class encapsulates the state required to compute binomial coefficients modulo a prime \(P\).

It performs an initial precomputation of:

• Factorials: \(n! \pmod{P}\)
• Inverse Factorials: \((n!)^{-1} \pmod{P}\)

This allows computing \(\binom{n}{k} \equiv \frac{n!}{k!(n-k)!} \pmod{P}\) in O(1) time per query.

Note

The modulus must be a prime number for the modular inverse to be well-defined for all factorials within \([1, P-1]\).

Definition at line 73 of file modular_combinatorics.H.

Constructor & Destructor Documentation

ModularCombinatorics()

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

inline

Construct and precompute factorials up to 'max_n' modulo 'p'.

Parameters

[in]	max_n	Maximum value for \(n\)to be used in O(1) nCk queries.
[in]	p	The prime modulus.

Precondition

p must be a prime number.

Exceptions

std::invalid_argument

if p is not prime (verified via Miller-Rabin).

Complexity: Time O(max_n + log p), Space O(max_n).

Definition at line 90 of file modular_combinatorics.H.

References ah_invalid_argument_if, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), 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 \(\binom{n}{k} \pmod{P}\)using Lucas' Theorem.

Provides a way to compute combinations when \(n\)and \(k\)are very large (exceeding max_n) but the prime modulus \(P\)is small.

Lucas' Theorem states:

\[ \binom{n}{k} \equiv \prod_{i=0}^m \binom{n_i}{k_i} \pmod{P} \]

where \(n_i\)and \(k_i\)are the digits of \(n\)and \(k\) in base \(P\).

Precondition

The instance must have been precomputed up to at least mod_ - 1.

Parameters

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

Returns

The value of \(\binom{n}{k} \pmod{P}\).

Complexity: Time \(\binom{n}{k} \pmod{P}\)#77modular multiplications.

Definition at line 154 of file modular_combinatorics.H.

References Aleph::blossom_maximum_cardinality_matching(), 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 \(\binom{n}{k} \pmod{P}\)in constant time.

Computes the binomial coefficient using the precomputed tables.

Parameters

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

Returns

The value of \(\binom{n}{k} \pmod{P}\).

Note

Requires \(n\)to be within the max_n range provided at construction.

Exceptions

ah_out_of_range_error

if \(n\)exceeds the precomputed range.

Complexity: Time O(1).

Definition at line 124 of file modular_combinatorics.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), 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 array.

Definition at line 76 of file modular_combinatorics.H.

Referenced by ModularCombinatorics(), and nCk().

invFact_

Array<uint64_t> Aleph::ModularCombinatorics::invFact_

private

Precomputed inverse factorials array.

Definition at line 77 of file modular_combinatorics.H.

Referenced by ModularCombinatorics(), and nCk().

mod_

uint64_t Aleph::ModularCombinatorics::mod_

private

Prime modulus \(P\).

Definition at line 75 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