summaryrefslogtreecommitdiff
path: root/boost/math/tools/polynomial_gcd.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/math/tools/polynomial_gcd.hpp')
-rw-r--r--boost/math/tools/polynomial_gcd.hpp48
1 files changed, 24 insertions, 24 deletions
diff --git a/boost/math/tools/polynomial_gcd.hpp b/boost/math/tools/polynomial_gcd.hpp
index f8e8334869..fd0a8c2740 100644
--- a/boost/math/tools/polynomial_gcd.hpp
+++ b/boost/math/tools/polynomial_gcd.hpp
@@ -12,12 +12,12 @@
#endif
#include <boost/math/tools/polynomial.hpp>
-#include <boost/math/common_factor_rt.hpp>
+#include <boost/integer/common_factor_rt.hpp>
#include <boost/type_traits/is_pod.hpp>
-namespace boost{
-
+namespace boost{
+
namespace integer {
namespace gcd_detail {
@@ -35,26 +35,26 @@ namespace boost{
}
}
-
-
-
+
+
+
namespace math{ namespace tools{
-
+
/* From Knuth, 4.6.1:
-*
+*
* We may write any nonzero polynomial u(x) from R[x] where R is a UFD as
*
* u(x) = cont(u) . pp(u(x))
*
* where cont(u), the content of u, is an element of S, and pp(u(x)), the primitive
-* part of u(x), is a primitive polynomial over S.
+* part of u(x), is a primitive polynomial over S.
* When u(x) = 0, it is convenient to define cont(u) = pp(u(x)) = O.
*/
template <class T>
T content(polynomial<T> const &x)
{
- return x ? gcd_range(x.data().begin(), x.data().end()).first : T(0);
+ return x ? boost::integer::gcd_range(x.data().begin(), x.data().end()).first : T(0);
}
// Knuth, 4.6.1
@@ -82,13 +82,13 @@ T leading_coefficient(polynomial<T> const &x)
namespace detail
{
- /* Reduce u and v to their primitive parts and return the gcd of their
+ /* Reduce u and v to their primitive parts and return the gcd of their
* contents. Used in a couple of gcd algorithms.
*/
template <class T>
T reduce_to_primitive(polynomial<T> &u, polynomial<T> &v)
{
- using boost::math::gcd;
+ using boost::integer::gcd;
T const u_cont = content(u), v_cont = content(v);
u /= u_cont;
v /= v_cont;
@@ -100,14 +100,14 @@ namespace detail
/**
* Knuth, The Art of Computer Programming: Volume 2, Third edition, 1998
* Algorithm 4.6.1C: Greatest common divisor over a unique factorization domain.
-*
-* The subresultant algorithm by George E. Collins [JACM 14 (1967), 128-142],
+*
+* The subresultant algorithm by George E. Collins [JACM 14 (1967), 128-142],
* later improved by W. S. Brown and J. F. Traub [JACM 18 (1971), 505-514].
-*
+*
* Although step C3 keeps the coefficients to a "reasonable" size, they are
* still potentially several binary orders of magnitude larger than the inputs.
* Thus, this algorithm should only be used where T is a multi-precision type.
-*
+*
* @tparam T Polynomial coefficient type.
* @param u First polynomial.
* @param v Second polynomial.
@@ -119,17 +119,17 @@ subresultant_gcd(polynomial<T> u, polynomial<T> v)
{
using std::swap;
BOOST_ASSERT(u || v);
-
+
if (!u)
return v;
if (!v)
return u;
-
+
typedef typename polynomial<T>::size_type N;
-
+
if (u.degree() < v.degree())
swap(u, v);
-
+
T const d = detail::reduce_to_primitive(u, v);
T g = 1, h = 1;
polynomial<T> r;
@@ -154,16 +154,16 @@ subresultant_gcd(polynomial<T> u, polynomial<T> v)
h = tmp / detail::integer_power(h, delta - N(1));
}
}
-
-
+
+
/**
* @brief GCD for polynomials with unbounded multi-precision integral coefficients.
- *
+ *
* The multi-precision constraint is enforced via numeric_limits.
*
* Note that intermediate terms in the evaluation can grow arbitrarily large, hence the need for
* unbounded integers, otherwise numeric loverflow would break the algorithm.
- *
+ *
* @tparam T A multi-precision integral type.
*/
template <typename T>