Class which contains all methods required for calculating nCr mod p.
More...
|
| NCRModuloP (const uint64_t &size, const uint64_t &mod) |
| the p from (nCr % p)
|
|
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) |
|
|
std::vector< uint64_t > | fac {} |
|
uint64_t | p = 0 |
| stores precomputed factorial(i) % p value
|
|
Class which contains all methods required for calculating nCr mod p.
◆ 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'
41 {
44 fac[0] = 1;
45 for (int i = 1; i <= size; i++) {
46 fac[i] = (fac[i - 1] * i) %
p;
47 }
48 }
uint64_t p
stores precomputed factorial(i) % p value
Definition ncr_modulo_p.cpp:34
◆ 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
57 {
58 if (a == 0) {
59 *x = 0, *y = 1;
60 return b;
61 }
62
63 int64_t x1 = 0, y1 = 0;
65
66 *x = y1 - (b / a) * x1;
67 *y = x1;
69 }
uint64_t gcdExtended(const uint64_t &a, const uint64_t &b, int64_t *x, int64_t *y)
Definition ncr_modulo_p.cpp:56
int gcd(int num1, int num2)
Definition gcd_iterative_euclidean.cpp:15
◆ 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
76 {
77 int64_t x = 0, y = 0;
79 if (g != 1) {
80 return -1;
81 } else {
82 int64_t res = ((x + m) % m);
83 return res;
84 }
85 }
double g(double x)
Another test function.
Definition composite_simpson_rule.cpp:115
◆ 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
92 {
93
94 if (r > n) {
95 return 0;
96 }
97 if (r == 1) {
99 }
100 if (r == 0 || r == n) {
101 return 1;
102 }
103
105 if (denominator < 0) {
106 return -1;
107 }
108 denominator = (denominator *
modInverse(fac[n - r],
p)) %
p;
109 if (denominator < 0) {
110 return -1;
111 }
112 return (fac[n] * denominator) %
p;
113 }
int64_t modInverse(const uint64_t &a, const uint64_t &m)
Definition ncr_modulo_p.cpp:76
◆ fac
std::vector<uint64_t> math::ncr_modulo_p::NCRModuloP::fac {} |
|
private |
The documentation for this class was generated from the following file: