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 uint64_t &size, const uint64_t &mod)
	the p from (nCr % p) More...
uint64_t	gcdExtended (const uint64_t &a, const uint64_t &b, int64_t *x, int64_t *y)
int64_t	modInverse (const uint64_t &a, const uint64_t &m)
int64_t	ncr (const uint64_t &n, const uint64_t &r, const uint64_t &p)

Private Attributes
std::vector< uint64_t >	fac {}
uint64_t	p = 0
	stores precomputed factorial(i) % p value

Detailed Description

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

Constructor & Destructor Documentation

NCRModuloP()

math::ncr_modulo_p::NCRModuloP::NCRModuloP ( const uint64_t &  size, const uint64_t &  mod  )

inline

the p from (nCr % p)

Constructor which precomputes the values of n! % mod from n=0 to size and stores them in vector 'fac' @params[in] the numbers 'size', 'mod'

                                                          {
        p = mod;
        fac = std::vector<uint64_t>(size);
        fac[0] = 1;
        for (int i = 1; i <= size; i++) {
            fac[i] = (fac[i - 1] * i) % p;
        }
    }

Member Function Documentation

gcdExtended()

uint64_t math::ncr_modulo_p::NCRModuloP::gcdExtended ( const uint64_t &  a, const uint64_t &  b, int64_t *  x, int64_t *  y  )

inline

Finds the value of x, y such that a*x + b*y = gcd(a,b)

@params[in] the numbers 'a', 'b' and address of 'x' and 'y' from above equation

Returns

the gcd of a and b

                                     {
        if (a == 0) {
            *x = 0, *y = 1;
            return b;
        }
 
        int64_t x1 = 0, y1 = 0;
        uint64_t gcd = gcdExtended(b % a, a, &x1, &y1);
 
        *x = y1 - (b / a) * x1;
        *y = x1;
        return gcd;
    }

Here is the call graph for this function:

modInverse()

int64_t math::ncr_modulo_p::NCRModuloP::modInverse ( const uint64_t &  a, const uint64_t &  m  )

inline

Find modular inverse of a with m i.e. a number x such that (a*x)m = 1

@params[in] the numbers 'a' and 'm' from above equation

Returns

the modular inverse of a

                                                             {
        int64_t x = 0, y = 0;
        uint64_t g = gcdExtended(a, m, &x, &y);
        if (g != 1) {  // modular inverse doesn't exist
            return -1;
        } else {
            int64_t res = ((x + m) % m);
            return res;
        }
    }

Here is the call graph for this function:

ncr()

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

inline

Find nCr % p

@params[in] the numbers 'n', 'r' and 'p'

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)
        int64_t denominator = modInverse(fac[r], p);
        if (denominator < 0) {  // modular inverse doesn't exist
            return -1;
        }
        denominator = (denominator * modInverse(fac[n - r], p)) % p;
        if (denominator < 0) {  // modular inverse doesn't exist
            return -1;
        }
        return (fac[n] * denominator) % p;
    }

Here is the call graph for this function:

---

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

• math/ncr_modulo_p.cpp