27 #ifndef NUMBER_THEORY_H_
28 #define NUMBER_THEORY_H_
53 std::vector<int> result;
55 for (
idx i = 0; i < n; ++i)
57 result.push_back(std::llround(std::floor(x)));
58 x = 1 / (x - std::floor(x));
59 if (!std::isfinite(x) || x > cut)
93 double tmp = 1. / cf[n - 1];
94 for (
idx i = n - 2; i != 0; --i)
96 tmp = 1. / (tmp + cf[i]);
120 double tmp = 1. / cf[cf.size() - 1];
121 for (
idx i = cf.size() - 2; i != 0; --i)
123 tmp = 1. / (tmp + cf[i]);
141 if (m == 0 && n == 0)
145 if (m == 0 || n == 0)
146 return (std::max(m, n));
175 for (
idx i = 1; i < ns.size(); ++i)
177 result =
gcd(result, ns[i]);
193 if (m == 0 || n == 0)
196 return m * n /
gcd(m, n);
216 if (std::find(std::begin(ns), std::end(ns), 0) != std::end(ns))
221 std::accumulate(std::begin(ns),
223 static_cast<ubigint>(1),
224 std::multiplies<ubigint>());
226 return prod /
gcd(ns);
235 inline std::vector<idx>
invperm(
const std::vector<idx>& perm)
244 std::vector<idx> result(perm.size());
245 for (
idx i = 0; i < perm.size(); ++i)
259 inline std::vector<idx>
compperm(
const std::vector<idx>& perm,
260 const std::vector<idx>&
sigma)
268 if (perm.size() != sigma.size())
273 std::vector<idx> result(perm.size());
274 for (
idx i = 0; i < perm.size(); ++i)
275 result[i] = perm[sigma[i]];
292 if (n == 0 || n == 1)
296 std::vector<ubigint> result;
332 if (n == 0 or n == 1)
336 std::vector<ubigint> facts =
factors(n);
338 if (facts.size() == 1)
358 if (p == 0 || (a == 0 && n == 0))
365 for (; n > 0; n /= 2)
368 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:231
Quantum++ main namespace.
Definition: codes.h:30
ubigint lcm(ubigint m, ubigint n)
Least common multiple of two positive integers.
Definition: number_theory.h:191
ubigint modpow(ubigint a, ubigint n, ubigint p)
Integer power modulo p.
Definition: number_theory.h:354
std::vector< idx > compperm(const std::vector< idx > &perm, const std::vector< idx > &sigma)
Compose permutations.
Definition: number_theory.h:259
double contfrac2x(const std::vector< int > &cf, idx n)
Real representation of a simple continued fraction.
Definition: number_theory.h:76
std::vector< idx > invperm(const std::vector< idx > &perm)
Inverse permutation.
Definition: number_theory.h:235
double sigma(const std::vector< double > &prob, const Container &X)
Standard deviation.
Definition: statistics.h:201
bool isprime(ubigint n)
Primality test.
Definition: number_theory.h:328
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:288
ubigint gcd(ubigint m, ubigint n)
Greatest common divisor of two non-negative integers.
Definition: number_theory.h:137
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