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]);
128 inline unsigned long long int
129 gcd(
unsigned long long int m,
unsigned long long int n)
131 if (m == 0 && n == 0)
134 if (m == 0 || n == 0)
135 return (std::max(m, n));
137 unsigned long long int result = 1;
155 inline unsigned long long int
156 gcd(
const std::vector<unsigned long long int>& ns)
161 unsigned long long int result = ns[0];
162 for (
idx i = 1; i < ns.size(); ++i)
164 result =
gcd(result, ns[i]);
178 inline unsigned long long int
179 lcm(
unsigned long long int m,
unsigned long long int n)
181 if (m == 0 || n == 0)
184 return m * n /
gcd(m, n);
194 inline unsigned long long int
195 lcm(
const std::vector<unsigned long long int>& ns)
203 if (std::find(std::begin(ns), std::end(ns), 0) != std::end(ns))
206 unsigned long long int prod =
207 std::accumulate(std::begin(ns),
209 static_cast<unsigned long long int>(1),
210 std::multiplies<unsigned long long int>());
212 return prod /
gcd(ns);
221 inline std::vector<idx>
invperm(
const std::vector<idx>& perm)
227 std::vector<idx> result(perm.size());
228 for (
idx i = 0; i < perm.size(); ++i)
242 inline std::vector<idx>
compperm(
const std::vector<idx>& perm,
243 const std::vector<idx>& sigma)
249 if (perm.size() != sigma.size())
253 std::vector<idx> result(perm.size());
254 for (
idx i = 0; i < perm.size(); ++i)
255 result[i] = perm[sigma[i]];
268 inline std::vector<unsigned long long int>
factors(
unsigned long long int n)
270 if (n == 0 || n == 1)
273 std::vector<unsigned long long int> result;
274 unsigned long long int d = 2;
307 if (n == 0 or n == 1)
310 std::vector<unsigned long long int> facts =
factors(n);
312 if (facts.size() == 1)
unsigned long long int lcm(unsigned long long int m, unsigned long long int n)
Least common multiple of two positive integers.
Definition: number_theory.h:179
std::vector< unsigned long long int > factors(unsigned long long int n)
Prime factor decomposition.
Definition: number_theory.h:268
Derived::Scalar prod(const Eigen::MatrixBase< Derived > &A)
Element-wise product of A.
Definition: functions.h:213
bool isprime(unsigned long long int n)
Primality test.
Definition: number_theory.h:305
Quantum++ main namespace.
Definition: codes.h:30
std::vector< idx > compperm(const std::vector< idx > &perm, const std::vector< idx > &sigma)
Compose permutations.
Definition: number_theory.h:242
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:221
bool _check_perm(const std::vector< idx > &perm)
Definition: util.h:256
Generates custom exceptions, used when validating function parameters.
Definition: exception.h:39
unsigned long long int gcd(unsigned long long int m, unsigned long long int n)
Greatest common divisor of two non-negative integers.
Definition: number_theory.h:129
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