27 #ifndef NUMBER_THEORY_H_
28 #define NUMBER_THEORY_H_
50 std::vector <int> result;
52 for (
idx i = 0; i < n; ++i)
54 result.push_back(std::llround(std::floor(x)));
55 x = 1 / (x - std::floor(x));
56 if (!std::isfinite(x) || x > cut)
87 double tmp = 1. / cf[n - 1];
88 for (
idx i = n - 2; i != 0; --i)
90 tmp = 1. / (tmp + cf[i]);
111 double tmp = 1. / cf[cf.size() - 1];
112 for (
idx i = cf.size() - 2; i != 0; --i)
114 tmp = 1. / (tmp + cf[i]);
130 if (m == 0 && n == 0)
133 if (m == 0 || n == 0)
134 return (std::max(m, n));
160 for (
idx i = 1; i < ns.size(); ++i)
162 result =
gcd(result, ns[i]);
178 if (m == 0 || n == 0)
181 return m * n /
gcd(m, n);
199 if (std::find(std::begin(ns), std::end(ns), 0) != std::end(ns))
203 std::accumulate(std::begin(ns),
205 static_cast<ubigint>(1),
206 std::multiplies<ubigint>());
208 return prod /
gcd(ns);
217 inline std::vector <idx>
invperm(
const std::vector <idx>& perm)
223 std::vector <idx> result(perm.size());
224 for (
idx i = 0; i < perm.size(); ++i)
238 inline std::vector <idx>
compperm(
const std::vector <idx>& perm,
239 const std::vector <idx>&
sigma)
245 if (perm.size() != sigma.size())
249 std::vector <idx> result(perm.size());
250 for (
idx i = 0; i < perm.size(); ++i)
251 result[i] = perm[sigma[i]];
266 if (n == 0 || n == 1)
269 std::vector <ubigint> result;
303 if (n == 0 or n == 1)
306 std::vector <ubigint> facts =
factors(n);
308 if (facts.size() == 1)
326 if (p == 0 || (a == 0 && n == 0))
332 for (; n > 0; n /= 2)
335 result = (result * a) % p;
unsigned long long int ubigint
Non-negative big integer.
Definition: types.h:46
Derived::Scalar prod(const Eigen::MatrixBase< Derived > &A)
Element-wise product of A.
Definition: functions.h:213
Quantum++ main namespace.
Definition: codes.h:30
ubigint lcm(ubigint m, ubigint n)
Least common multiple of two positive integers.
Definition: number_theory.h:176
ubigint modpow(ubigint a, ubigint n, ubigint p)
Integer power modulo p.
Definition: number_theory.h:324
std::vector< idx > compperm(const std::vector< idx > &perm, const std::vector< idx > &sigma)
Compose permutations.
Definition: number_theory.h:238
double contfrac2x(const std::vector< int > &cf, idx n)
Real representation of a simple continued fraction.
Definition: number_theory.h:73
std::vector< idx > invperm(const std::vector< idx > &perm)
Inverse permutation.
Definition: number_theory.h:217
double sigma(const std::vector< double > &prob, const Container &X)
Standard deviation.
Definition: statistics.h:181
bool isprime(ubigint n)
Primality test.
Definition: number_theory.h:301
bool _check_perm(const std::vector< idx > &perm)
Definition: util.h:257
Generates custom exceptions, used when validating function parameters.
Definition: exception.h:39
std::vector< ubigint > factors(ubigint n)
Prime factor decomposition.
Definition: number_theory.h:264
ubigint gcd(ubigint m, ubigint n)
Greatest common divisor of two non-negative integers.
Definition: number_theory.h:128
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