27 #ifndef NUMBER_THEORY_H_
28 #define NUMBER_THEORY_H_
53 std::vector<int> result;
55 for (
idx i = 0; i < n; ++i)
59 result.push_back(std::llround(std::floor(x)));
60 x = 1 / (x - std::floor(x));
64 result.push_back(std::llround(std::ceil(x)));
65 x = 1 / (x - std::ceil(x));
67 if (!std::isfinite(x) || std::abs(x) > cut)
101 double tmp = 1. / cf[n - 1];
102 for (
idx i = n - 2; i != 0; --i)
104 tmp = 1. / (tmp + cf[i]);
128 double tmp = 1. / cf[cf.size() - 1];
129 for (
idx i = cf.size() - 2; i != 0; --i)
131 tmp = 1. / (tmp + cf[i]);
149 if (m == 0 && n == 0)
153 if (m == 0 || n == 0)
154 return (std::max(std::abs(m), std::abs(n)));
164 return (result > 0) ? result : -result;
183 for (
idx i = 1; i < ns.size(); ++i)
185 result =
gcd(result, ns[i]);
188 return (result > 0) ? result : -result;
201 if (m == 0 && n == 0)
206 return (result > 0) ? result : -result;
226 if (std::find(std::begin(ns), std::end(ns), 0) != std::end(ns))
232 for (
idx i = 1; i < ns.size(); ++i)
234 result =
lcm(result, ns[i]);
237 return (result > 0) ? result : -result;
246 inline std::vector<idx>
invperm(
const std::vector<idx>& perm)
255 std::vector<idx> result(perm.size());
256 for (
idx i = 0; i < perm.size(); ++i)
270 inline std::vector<idx>
compperm(
const std::vector<idx>& perm,
271 const std::vector<idx>&
sigma)
279 if (perm.size() != sigma.size())
284 std::vector<idx> result(perm.size());
285 for (
idx i = 0; i < perm.size(); ++i)
286 result[i] = perm[sigma[i]];
306 if (n == 0 || n == 1)
310 std::vector<bigint> result;
350 if (n == 0 or n == 1)
356 if (facts.size() == 1)
377 if (a < 0 || n < 0 || p < 1)
380 if (a == 0 && n == 0)
388 if (n == 0 && p == 1)
393 for (; n > 0; n /= 2)
396 result = (result * a) % p;
417 if (m == 0 && n == 0)
424 bigint q, r, a1, a2, b1, b2;
426 a2 = 1, a1 = 0, b2 = 0, b1 = 1;
429 q = m / n, r = m - q * n;
430 a = a2 - q * a1, b = b2 - q * b1;
432 a2 = a1, a1 = a, b2 = b1, b1 = b;
434 c = m, a = a2, b = b2;
444 return std::make_tuple(a, b, c);
461 if (a == 0 || p == 0 || a < 0 || p < 0)
466 std::tie(x, y, gcd_ap) =
egcd(p, a);
473 return (y > 0) ? y : y + p;
std::vector< bigint > factors(bigint n)
Prime factor decomposition.
Definition: number_theory.h:299
bigint lcm(bigint m, bigint n)
Least common multiple of two integers.
Definition: number_theory.h:199
bool isprime(bigint n)
Primality test.
Definition: number_theory.h:343
bigint modpow(bigint a, bigint n, bigint p)
Fast integer power modulo p based on the SQUARE-AND-MULTIPLY algorithm.
Definition: number_theory.h:373
Quantum++ main namespace.
Definition: codes.h:30
double sigma(const std::vector< double > &prob, const Container &X, typename std::enable_if< is_iterable< Container >::value >::type *=nullptr)
Standard deviation.
Definition: statistics.h:207
std::tuple< bigint, bigint, bigint > egcd(bigint m, bigint n)
Extended greatest common divisor of two integers.
Definition: number_theory.h:413
std::vector< idx > compperm(const std::vector< idx > &perm, const std::vector< idx > &sigma)
Compose permutations.
Definition: number_theory.h:270
double contfrac2x(const std::vector< int > &cf, idx n)
Real representation of a simple continued fraction.
Definition: number_theory.h:84
std::vector< idx > invperm(const std::vector< idx > &perm)
Inverse permutation.
Definition: number_theory.h:246
bool _check_perm(const std::vector< idx > &perm)
Definition: util.h:242
bigint modinv(bigint a, bigint p)
Modular inverse of a mod p.
Definition: number_theory.h:457
Generates custom exceptions, used when validating function parameters.
Definition: exception.h:39
bigint gcd(bigint m, bigint n)
Greatest common divisor of two integers.
Definition: number_theory.h:145
long long int bigint
Big integer.
Definition: types.h:41
std::vector< int > x2contfrac(double x, idx n, idx cut=1e5)
Simple continued fraction expansion.
Definition: number_theory.h:45
std::size_t idx
Non-negative integer index.
Definition: types.h:36