math::ncr_modulo_p::NCRModuloP Class Reference

Class which contains all methods required for calculating nCr mod p. More...

Collaboration diagram for math::ncr_modulo_p::NCRModuloP:

Public Member Functions
	NCRModuloP (const int64_t &size, const int64_t &p)
	constructs an NCRModuloP object allowing to compute (nCr)p for inputs from 0 to size
int64_t	ncr (const int64_t &n, const int64_t &r) const
	computes nCr % p

Static Private Member Functions
static std::vector< int64_t >	computeFactorialsMod (const int64_t &max_arg_val, const int64_t &mod)
	stores precomputed factorial(i) % p value

Private Attributes
const int64_t	p = 0
const std::vector< int64_t >	fac
	the p from (nCr % p)

Detailed Description

Class which contains all methods required for calculating nCr mod p.

Constructor & Destructor Documentation

NCRModuloP()

math::ncr_modulo_p::NCRModuloP::NCRModuloP ( const int64_t & size, const int64_t & p )

inline

constructs an NCRModuloP object allowing to compute (nCr)p for inputs from 0 to size

        : p(p), fac(computeFactorialsMod(size, p)) {}

Member Function Documentation

computeFactorialsMod()

static std::vector< int64_t > math::ncr_modulo_p::NCRModuloP::computeFactorialsMod ( const int64_t & max_arg_val, const int64_t & mod )

inlinestaticprivate

stores precomputed factorial(i) % p value

computes the array of values of factorials reduced modulo mod

Parameters

max_arg_val	argument of the last factorial stored in the result
mod	value of the divisor used to reduce factorials

Returns

vector storing factorials of the numbers 0, ..., max_arg_val reduced modulo mod

                                                                         {
        auto res = std::vector<int64_t>(max_arg_val + 1);
        res[0] = 1;
        for (int64_t i = 1; i <= max_arg_val; i++) {
            res[i] = (res[i - 1] * i) % mod;
        }
        return res;
    }

ncr()

int64_t math::ncr_modulo_p::NCRModuloP::ncr ( const int64_t & n, const int64_t & r ) const

inline

computes nCr % p

Parameters

[in]	n	the number of objects to be chosen
[in]	r	the number of objects to choose from

Returns

the value nCr % p

                                                          {
        // Base cases
        if (r > n) {
            return 0;
        }
        if (r == 1) {
            return n % p;
        }
        if (r == 0 || r == n) {
            return 1;
        }
        // fac is a global array with fac[r] = (r! % p)
        const auto denominator = (fac[r] * fac[n - r]) % p;
        const auto denominator_inv = utils::modInverse(denominator, p);
        if (denominator_inv < 0) {  // modular inverse doesn't exist
            return -1;
        }
        return (fac[n] * denominator_inv) % p;
    }

---

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

• math/ncr_modulo_p.cpp