Debian Codegraph @

third-party/boost-math/include/boost/math/tools/polynomial_gcd.hpp

raw
1 // (C) Copyright Jeremy William Murphy 2016.
2 // (C) Copyright Matt Borland 2021.
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 #ifndef BOOST_MATH_TOOLS_POLYNOMIAL_GCD_HPP
8 #define BOOST_MATH_TOOLS_POLYNOMIAL_GCD_HPP
9
10 #ifdef _MSC_VER
11 #pragma once
12 #endif
13
14 #include <algorithm>
15 #include <type_traits>
16 #include <boost/math/tools/is_standalone.hpp>
17 #include <boost/math/tools/polynomial.hpp>
18
19 #ifndef BOOST_MATH_STANDALONE
20 #include <boost/integer/common_factor_rt.hpp>
21
22 #else
23 #include <numeric>
24 #include <utility>
25 #include <iterator>
26 #include <boost/math/tools/assert.hpp>
27 #include <boost/math/tools/config.hpp>
28
29 namespace boost { namespace integer {
30
31 namespace gcd_detail {
32
33 template <typename EuclideanDomain>
34 inline EuclideanDomain Euclid_gcd(EuclideanDomain a, EuclideanDomain b) noexcept(std::is_arithmetic<EuclideanDomain>::value)
35 {
36 using std::swap;
37 while (b != EuclideanDomain(0))
38 {
39 a %= b;
40 swap(a, b);
41 }
42 return a;
43 }
44
45 enum method_type
46 {
47 method_euclid = 0,
48 method_binary = 1,
49 method_mixed = 2
50 };
51
52 } // gcd_detail
53
54 template <typename Iter, typename T = typename std::iterator_traits<Iter>::value_type>
55 std::pair<T, Iter> gcd_range(Iter first, Iter last) noexcept(std::is_arithmetic<T>::value)
56 {
57 BOOST_MATH_ASSERT(first != last);
58
59 T d = *first;
60 ++first;
61 while (d != T(1) && first != last)
62 {
63 #ifdef BOOST_MATH_HAS_CXX17_NUMERIC
64 d = std::gcd(d, *first);
65 #else
66 d = gcd_detail::Euclid_gcd(d, *first);
67 #endif
68 ++first;
69 }
70 return std::make_pair(d, first);
71 }
72
73 }} // namespace boost::integer
74 #endif
75
76 namespace boost{
77
78 namespace integer {
79
80 namespace gcd_detail {
81
82 template <class T>
83 struct gcd_traits;
84
85 template <class T>
86 struct gcd_traits<boost::math::tools::polynomial<T> >
87 {
88 inline static const boost::math::tools::polynomial<T>& abs(const boost::math::tools::polynomial<T>& val) { return val; }
89
90 static const method_type method = method_euclid;
91 };
92
93 }
94 }
95
96 namespace math{ namespace tools{
97
98 /* From Knuth, 4.6.1:
99 *
100 * We may write any nonzero polynomial u(x) from R[x] where R is a UFD as
101 *
102 * u(x) = cont(u) . pp(u(x))
103 *
104 * where cont(u), the content of u, is an element of S, and pp(u(x)), the primitive
105 * part of u(x), is a primitive polynomial over S.
106 * When u(x) = 0, it is convenient to define cont(u) = pp(u(x)) = O.
107 */
108
109 template <class T>
110 T content(polynomial<T> const &x)
111 {
112 return x ? boost::integer::gcd_range(x.data().begin(), x.data().end()).first : T(0);
113 }
114
115 // Knuth, 4.6.1
116 template <class T>
117 polynomial<T> primitive_part(polynomial<T> const &x, T const &cont)
118 {
119 return x ? x / cont : polynomial<T>();
120 }
121
122
123 template <class T>
124 polynomial<T> primitive_part(polynomial<T> const &x)
125 {
126 return primitive_part(x, content(x));
127 }
128
129
130 // Trivial but useful convenience function referred to simply as l() in Knuth.
131 template <class T>
132 T leading_coefficient(polynomial<T> const &x)
133 {
134 return x ? x.data().back() : T(0);
135 }
136
137
138 namespace detail
139 {
140 /* Reduce u and v to their primitive parts and return the gcd of their
141 * contents. Used in a couple of gcd algorithms.
142 */
143 template <class T>
144 T reduce_to_primitive(polynomial<T> &u, polynomial<T> &v)
145 {
146 T const u_cont = content(u), v_cont = content(v);
147 u /= u_cont;
148 v /= v_cont;
149
150 #ifdef BOOST_MATH_HAS_CXX17_NUMERIC
151 return std::gcd(u_cont, v_cont);
152 #else
153 return boost::integer::gcd_detail::Euclid_gcd(u_cont, v_cont);
154 #endif
155 }
156 }
157
158
159 /**
160 * Knuth, The Art of Computer Programming: Volume 2, Third edition, 1998
161 * Algorithm 4.6.1C: Greatest common divisor over a unique factorization domain.
162 *
163 * The subresultant algorithm by George E. Collins [JACM 14 (1967), 128-142],
164 * later improved by W. S. Brown and J. F. Traub [JACM 18 (1971), 505-514].
165 *
166 * Although step C3 keeps the coefficients to a "reasonable" size, they are
167 * still potentially several binary orders of magnitude larger than the inputs.
168 * Thus, this algorithm should only be used where T is a multi-precision type.
169 *
170 * @tparam T Polynomial coefficient type.
171 * @param u First polynomial.
172 * @param v Second polynomial.
173 * @return Greatest common divisor of polynomials u and v.
174 */
175 template <class T>
176 typename std::enable_if< std::numeric_limits<T>::is_integer, polynomial<T> >::type
177 subresultant_gcd(polynomial<T> u, polynomial<T> v)
178 {
179 using std::swap;
180 BOOST_MATH_ASSERT(u || v);
181
182 if (!u)
183 return v;
184 if (!v)
185 return u;
186
187 typedef typename polynomial<T>::size_type N;
188
189 if (u.degree() < v.degree())
190 swap(u, v);
191
192 T const d = detail::reduce_to_primitive(u, v);
193 T g = 1, h = 1;
194 polynomial<T> r;
195 while (true)
196 {
197 BOOST_MATH_ASSERT(u.degree() >= v.degree());
198 // Pseudo-division.
199 r = u % v;
200 if (!r)
201 return d * primitive_part(v); // Attach the content.
202 if (r.degree() == 0)
203 return d * polynomial<T>(T(1)); // The content is the result.
204 N const delta = u.degree() - v.degree();
205 // Adjust remainder.
206 u = v;
207 v = r / (g * detail::integer_power(h, delta));
208 g = leading_coefficient(u);
209 T const tmp = detail::integer_power(g, delta);
210 if (delta <= N(1))
211 h = tmp * detail::integer_power(h, N(1) - delta);
212 else
213 h = tmp / detail::integer_power(h, delta - N(1));
214 }
215 }
216
217
218 /**
219 * @brief GCD for polynomials with unbounded multi-precision integral coefficients.
220 *
221 * The multi-precision constraint is enforced via numeric_limits.
222 *
223 * Note that intermediate terms in the evaluation can grow arbitrarily large, hence the need for
224 * unbounded integers, otherwise numeric overflow would break the algorithm.
225 *
226 * @tparam T A multi-precision integral type.
227 */
228 template <typename T>
229 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_bounded, polynomial<T> >::type
230 gcd(polynomial<T> const &u, polynomial<T> const &v)
231 {
232 return subresultant_gcd(u, v);
233 }
234 // GCD over bounded integers is not currently allowed:
235 template <typename T>
236 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_bounded, polynomial<T> >::type
237 gcd(polynomial<T> const &u, polynomial<T> const &v)
238 {
239 static_assert(sizeof(v) == 0, "GCD on polynomials of bounded integers is disallowed due to the excessive growth in the size of intermediate terms.");
240 return subresultant_gcd(u, v);
241 }
242 // GCD over polynomials of floats can go via the Euclid algorithm:
243 template <typename T>
244 typename std::enable_if<!std::numeric_limits<T>::is_integer && (std::numeric_limits<T>::min_exponent != std::numeric_limits<T>::max_exponent) && !std::numeric_limits<T>::is_exact, polynomial<T> >::type
245 gcd(polynomial<T> const &u, polynomial<T> const &v)
246 {
247 return boost::integer::gcd_detail::Euclid_gcd(u, v);
248 }
249
250 }
251 //
252 // Using declaration so we overload the default implementation in this namespace:
253 //
254 using boost::math::tools::gcd;
255
256 }
257
258 namespace integer
259 {
260 //
261 // Using declaration so we overload the default implementation in this namespace:
262 //
263 using boost::math::tools::gcd;
264 }
265
266 } // namespace boost::math::tools
267
268 #endif