modular_combinatorics.H File Reference

Modular combinatorics utilities for computing binomial coefficients. More...

#include <cstdint>
#include <ah-errors.H>
#include <tpl_array.H>
#include <modular_arithmetic.H>
#include <primality.H>

Include dependency graph for modular_combinatorics.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::ModularCombinatorics
	High-performance combinatorics operations modulo a prime. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Modular combinatorics utilities for computing binomial coefficients.

This header provides tools for computing combinations (n choose k) modulo a prime number. It uses precomputed factorials and modular inverse factorials to achieve O(1) time complexity for queries within a precomputed range.

For values of n and k that exceed the precomputed range (typically when the modulus is small), Lucas' Theorem is provided to compute the result efficiently.

Author

Leandro Rabindranath Leon

Definition in file modular_combinatorics.H.