一元多项式模板类更多...

#include <polynomial.hpp>

类 LMCAS::Polynomial< CoeffType > 继承关系图:

LMCAS::Polynomial< CoeffType > 的协作图:

Public 成员函数
	Polynomial (const CoeffType &c, const std::string &var="x")
	从单个常数构造常数多项式
	Polynomial (const std::string &var="x")
	构造零多项式
	Polynomial (const std::vector< CoeffType > &c, const std::string &var="x")
	从系数向量构造多项式
CoeffType	content () const
	计算多项式的容度(所有系数的 GCD)
int	degree () const
	获取多项式的次数
Polynomial	differentiate () const
	求导
std::pair< Polynomial, Polynomial >	div_mod (const Polynomial &other) const
	多项式带余除法
CoeffType	eval (const CoeffType &val) const
	对多项式求值(Horner 法)
bool	is_zero () const
	判断是否为零多项式
CoeffType	lead_coeff () const
	获取首项系数
Polynomial	make_monic () const
	首一化(使首项系数为 1)
Polynomial	operator* (const Polynomial &other) const
	多项式乘法
Polynomial	operator+ (const Polynomial &other) const
	多项式加法
Polynomial	operator- (const Polynomial &other) const
	多项式减法
bool	operator== (const Polynomial &other) const
	多项式判等
Polynomial	primitive_part () const
	计算多项式的本原部分(除以容度)
std::pair< Polynomial, Polynomial >	pseudo_div_mod (const Polynomial &other) const
	通过系数缩放执行伪除法,运算保持在原系数环
Polynomial	pseudo_div_mod_rem (const Polynomial &other) const
	伪除法取余数
Polynomial	square_free_part () const
	计算无平方因子部分
std::string	to_string () const
	转换为字符串表示
void	trim ()
	去除高次零系数

静态 Public 成员函数
static Polynomial	gcd (Polynomial a, Polynomial b)
	计算两个多项式的最大公因式
static CoeffType	gcd_coeff (const CoeffType &a, const CoeffType &b)
	计算两个系数的 GCD(静态方法)

Public 属性
std::vector< CoeffType >	coeffs
	系数数组,coeffs[i] 为 x^i 的系数
std::string	variable_name
	变量名

Private 成员函数
void	append_string_term (std::string &text, CoeffType coefficient, int power) const
void	require_compatible_variables (const Polynomial &other, const char *operation) const
bool	variables_compatible (const Polynomial &other) const

详细描述

template<typename CoeffType>
class LMCAS::Polynomial< CoeffType >

一元多项式模板类

模板参数

CoeffType 系数类型(支持 BigInt,Rational,int 等)

系数按升幂存储:coeffs[i] 对应 x^i 的系数. 非零操作数必须属于同一命名变量环（包括显式常数），否则算术、带余除法、伪除法和 GCD 抛出 std::invalid_argument，判等返回 false。加减乘中的零元素嵌入非零侧变量环；双方为零时保留左侧变量环。零被除数的商和余数采用除数变量环；零除数始终非法。

在文件 polynomial.hpp 第 52 行定义.

构造及析构函数说明

◆ Polynomial() [1/3]

template<typename CoeffType>

LMCAS::Polynomial< CoeffType >::Polynomial ( const std::string & var = "x" )

inline

构造零多项式

参数

var	变量名,默认 "x"

在文件 polynomial.hpp 第 62 行定义.

62: variable_name(var) {}

LMCAS::Polynomial

一元多项式模板类

定义 polynomial.hpp:52

LMCAS::Polynomial::variable_name

std::string variable_name

变量名

定义 polynomial.hpp:56

被这些函数引用 LMCAS::anonymous_namespace{poly_utils.cpp}::constant_to_poly(), LMCAS::Polynomial< Rational >::differentiate(), LMCAS::Polynomial< Rational >::div_mod(), gcd(), primitive_part(), pseudo_div_mod(), pseudo_div_mod_rem(), LMCAS::rational_to_symbolic_poly(), square_free_part() , 以及 LMCAS::symbolic_to_poly_recursive().

这是这个函数的调用关系图:

◆ Polynomial() [2/3]

template<typename CoeffType>

LMCAS::Polynomial< CoeffType >::Polynomial	(	const std::vector< CoeffType > &	c,
		const std::string &	var = "x" )

inline

从系数向量构造多项式

参数

c	系数向量(升幂排列)
var	变量名

在文件 polynomial.hpp 第 69 行定义.

        : coeffs(c), variable_name(var) {
        trim();
    }

◆ Polynomial() [3/3]

template<typename CoeffType>

LMCAS::Polynomial< CoeffType >::Polynomial	(	const CoeffType &	c,
		const std::string &	var = "x" )

inline

从单个常数构造常数多项式

参数

c	常数值
var	变量名

在文件 polynomial.hpp 第 79 行定义.

        : coeffs{c}, variable_name(var) {
        trim();
    }

成员函数说明

◆ append_string_term()

template<typename CoeffType>

void LMCAS::Polynomial< CoeffType >::append_string_term	(	std::string &	text,
		CoeffType	coefficient,
		int	power ) const

inlineprivate

在文件 polynomial.hpp 第 390 行定义.

                                                                                     {
        const bool positive = !(coefficient < CoeffType(0));
        if (!text.empty()) {
            text += positive ? " + " : " - ";
        } else if (!positive) {
            text += "-";
        }
        if (!positive) {
            coefficient = coefficient * CoeffType(-1);
        }
        if (!(coefficient == CoeffType(1)) || power == 0) {
            if constexpr (std::is_same_v<CoeffType, BigInt> ||
                          std::is_same_v<CoeffType, Rational>) {
                text += coefficient.to_string();
            } else {
                text += std::to_string(coefficient);
            }
            if (power > 0) {
                text += "*";
            }
        }
        if (power > 0) {
            text += variable_name;
        }
        if (power > 1) {
            text += "^" + std::to_string(power);
        }
    }

◆ content()

template<typename CoeffType>

CoeffType LMCAS::Polynomial< CoeffType >::content ( ) const

inline

计算多项式的容度(所有系数的 GCD)

返回: 容度值

在文件 polynomial_division.hpp 第 9 行定义.

                                                      {
    if (is_zero()) return CoeffType(0);
    CoeffType g = coeffs[0];
 
    if constexpr (std::is_same_v<CoeffType, Rational>) {
         return CoeffType(1);
    } else {
 
        for (size_t i = 1; i < coeffs.size(); ++i) {
            g = gcd_coeff(g, coeffs[i]);
            if (g == CoeffType(1)) break;
        }
        return g;
    }
}

引用了 coeffs, gcd_coeff() , 以及 is_zero().

被这些函数引用 primitive_part().

函数调用图:

这是这个函数的调用关系图:

◆ degree()

template<typename CoeffType>

int LMCAS::Polynomial< CoeffType >::degree ( ) const

inline

获取多项式的次数

返回: 次数;零多项式返回 -1

在文件 polynomial.hpp 第 100 行定义.

                       {
        if (coeffs.empty()) return -1;
        return static_cast<int>(coeffs.size()) - 1;
    }

这是这个函数的调用关系图:

◆ differentiate()

template<typename CoeffType>

Polynomial LMCAS::Polynomial< CoeffType >::differentiate ( ) const

inline

求导

返回: 导多项式

在文件 polynomial.hpp 第 307 行定义.

                                     {
        if (degree() < 1) return Polynomial(variable_name);
        Polynomial res(variable_name);
        res.coeffs.resize(coeffs.size() - 1);
        for (size_t i = 1; i < coeffs.size(); ++i) {
            CoeffType c = coeffs[i];
 
            res.coeffs[i-1] = c * CoeffType(i);
        }
        res.trim();
        return res;
    }

被这些函数引用 LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::make_sturm_sequence(), LMCAS::detail::definite::rational_pole_divergence(), LMCAS::detail::definite::roots_checked(), LMCAS::square_free_factorization(), square_free_part() , 以及 LMCAS::tf_square_free().

这是这个函数的调用关系图:

◆ div_mod()

template<typename CoeffType>

std::pair< Polynomial, Polynomial > LMCAS::Polynomial< CoeffType >::div_mod ( const Polynomial< CoeffType > & other ) const

inline

多项式带余除法

参数

other 除数多项式

返回: pair(商, 余数)

异常

std::runtime_error	除数为零多项式时抛出
std::invalid_argument	两个非零操作数的变量名不同时抛出

在文件 polynomial.hpp 第 207 行定义.

                                                                           {
        if (other.is_zero()) throw std::runtime_error("Division by zero polynomial");
        require_compatible_variables(other, "Polynomial::div_mod");
        if (is_zero()) {
            return {Polynomial(other.variable_name), Polynomial(other.variable_name)};
        }
 
        Polynomial quotient(variable_name);
        Polynomial remainder = *this;
 
        int deg_rem = remainder.degree();
        int deg_div = other.degree();
        CoeffType lc_div = other.lead_coeff();
 
        if (deg_rem < deg_div) {
             return {quotient, remainder};
        }
 
        quotient.coeffs.resize(deg_rem - deg_div + 1, CoeffType(0));
 
        while (deg_rem >= deg_div && !remainder.is_zero()) {
 
             CoeffType factor = remainder.lead_coeff() / lc_div;
             int deg_diff = deg_rem - deg_div;
 
             quotient.coeffs[deg_diff] = factor;
 
             Polynomial term(variable_name);
             term.coeffs.resize(deg_diff + 1, CoeffType(0));
             term.coeffs[deg_diff] = factor;
 
             Polynomial subtrahend = other * term;
             remainder = remainder - subtrahend;
             deg_rem = remainder.degree();
        }
 
        quotient.trim();
        return {quotient, remainder};
    }

被这些函数引用 LMCAS::anonymous_namespace{symbolic_cancel.cpp}::cancel_polynomial_gcd(), LMCAS::deflate_rational_root(), LMCAS::exact_factor_roots(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_projection.cpp}::exact_poly_divide(), LMCAS::extended_gcd_poly(), LMCAS::anonymous_namespace{integration_rational_coefficients.cpp}::rd_factor_complements(), LMCAS::anonymous_namespace{integration_rational_factorization.cpp}::rd_factor_piece(), LMCAS::anonymous_namespace{integration_rational_factorization.cpp}::rd_factor_quadratic(), LMCAS::anonymous_namespace{integration_rational.cpp}::rd_integrate_proper_fraction(), LMCAS::anonymous_namespace{integration_rational_collection.cpp}::rd_normalize_fraction(), LMCAS::anonymous_namespace{integration_rational.cpp}::rd_reduce_reciprocal(), LMCAS::reconstruct_rational_roots(), LMCAS::multivariate_checked_detail::restore_specialization_unit(), LMCAS::detail::definite::roots_checked(), LMCAS::polynomial_solver_detail::solve_by_factoring_impl(), LMCAS::solve_diophantine_pair(), LMCAS::solve_exact_factor(), LMCAS::square_free_factorization(), square_free_part(), LMCAS::tf_square_free(), LMCAS::zc_divides_exactly() , 以及 LMCAS::zc_try_candidate().

这是这个函数的调用关系图:

◆ eval()

template<typename CoeffType>

CoeffType LMCAS::Polynomial< CoeffType >::eval ( const CoeffType & val ) const

inline

对多项式求值(Horner 法)

参数

val 自变量的值

返回: 多项式在 val 处的值

在文件 polynomial.hpp 第 294 行定义.

                                               {
        if (coeffs.empty()) return CoeffType(0);
        CoeffType res = coeffs.back();
        for (int i = (int)coeffs.size() - 2; i >= 0; --i) {
            res = res * val + coeffs[i];
        }
        return res;
    }

被这些函数引用 LMCAS::detail::anonymous_namespace{interval_endpoint_order.cpp}::compare_algebraic_to_rational(), LMCAS::deflate_rational_root(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::edge_is_clear(), LMCAS::detail::equal_exact_real_algebraic(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::isolate_grid_row(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::pole_index(), LMCAS::detail::definite::polynomial_at_root_sign(), LMCAS::detail::definite::polynomial_sign_checked(), LMCAS::rational_root_candidate(), LMCAS::detail::definite::recover_rational_cut(), LMCAS::detail::complex_root::refine_interval(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::separate_imaginary_axis() , 以及 LMCAS::detail::inequality_support::snap_verified_integer_root().

这是这个函数的调用关系图:

◆ gcd()

template<typename CoeffType>

Polynomial< CoeffType > LMCAS::Polynomial< CoeffType >::gcd	(	Polynomial< CoeffType >	a,
		Polynomial< CoeffType >	b )

inlinestatic

计算两个多项式的最大公因式

参数

a	第一个多项式
b	第二个多项式

返回: gcd(a, b)

异常

std::invalid_argument 两个非零操作数的变量名不同时抛出

在文件 polynomial_division.hpp 第 107 行定义.

                                                      {
    a.require_compatible_variables(b, "Polynomial::gcd");
    if (b.is_zero()) return a;
    if (a.is_zero()) return b;
 
    if constexpr (std::is_same_v<CoeffType, Rational>) {
 
        while (!b.is_zero()) {
            auto [q, r] = a.div_mod(b);
            a = b;
            b = r;
        }
 
        return a.make_monic();
    } else {
 
        CoeffType cA = a.content();
        CoeffType cB = b.content();
        CoeffType c  = gcd_coeff_impl(cA, cB);
 
        a = a.primitive_part();
        b = b.primitive_part();
 
        while (!b.is_zero()) {
 
            Polynomial r = a.pseudo_div_mod_rem(b);
 
            if (r.is_zero()) {
                a = b;
                b = r;
            } else {
 
                a = b;
                b = r.primitive_part();
            }
        }
 
        if (c == CoeffType(1)) return a;
 
        for (auto& val : a.coeffs) val = val * c;
        return a;
    }
}

引用了 Polynomial(), LMCAS::a, LMCAS::b, LMCAS::c, LMCAS::gcd_coeff_impl() , 以及 LMCAS::r.

被这些函数引用 LMCAS::anonymous_namespace{symbolic_cancel.cpp}::cancel_polynomial_gcd(), LMCAS::detail::anonymous_namespace{exact_algebraic.cpp}::common_root_in_enclosures(), LMCAS::anonymous_namespace{integration_rational_collection.cpp}::rd_normalize_fraction(), LMCAS::square_free_factorization(), square_free_part(), LMCAS::tf_square_free(), LMCAS::univariate_gcd() , 以及 LMCAS::anonymous_namespace{integration_weierstrass.cpp}::weier_reduce_rational().

函数调用图:

这是这个函数的调用关系图:

◆ gcd_coeff()

template<typename CoeffType>

CoeffType LMCAS::Polynomial< CoeffType >::gcd_coeff	(	const CoeffType &	a,
		const CoeffType &	b )

inlinestatic

计算两个系数的 GCD(静态方法)

参数

a	第一个系数
b	第二个系数

返回: gcd(a, b)

在文件 polynomial.hpp 第 253 行定义.

                                                                       {
        if constexpr (std::is_same_v<CoeffType, BigInt>) {
            return BigInt::gcd(a, b);
        } else if constexpr (std::is_same_v<CoeffType, Rational>) {
            return CoeffType(1);
        } else {
 
             if constexpr (std::is_integral_v<CoeffType>) {
                 return std::gcd(a, b);
             }
 
             return CoeffType(1);
        }
    }

被这些函数引用 content().

这是这个函数的调用关系图:

◆ is_zero()

template<typename CoeffType>

bool LMCAS::Polynomial< CoeffType >::is_zero ( ) const

inline

判断是否为零多项式

在文件 polynomial.hpp 第 92 行定义.

                         {
        return coeffs.empty();
    }

这是这个函数的调用关系图:

◆ lead_coeff()

template<typename CoeffType>

CoeffType LMCAS::Polynomial< CoeffType >::lead_coeff ( ) const

inline

获取首项系数

返回: 最高次项的系数;零多项式返回 0

在文件 polynomial.hpp 第 109 行定义.

                                 {
        if (coeffs.empty()) return CoeffType(0);
        return coeffs.back();
    }

被这些函数引用 LMCAS::polynomial_solver_detail::bounded_rational_root_search(), LMCAS::detail::inequality_support::determine_leading_sign(), LMCAS::Polynomial< Rational >::div_mod(), LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::exact_polynomial_sign_intervals(), LMCAS::extended_gcd_poly(), LMCAS::find_rational_roots(), LMCAS::hl_compute_lift_height(), LMCAS::detail::anonymous_namespace{exact_algebraic.cpp}::monic(), LMCAS::detail::definite::polynomial_sign_checked(), primitive_part(), pseudo_div_mod(), LMCAS::rational_root_candidate(), LMCAS::anonymous_namespace{integration_rational_collection.cpp}::rd_normalize_fraction(), LMCAS::reconstruct_rational_roots(), LMCAS::solve_constant_inequality() , 以及 LMCAS::detail::strict_cauchy_root_bound().

这是这个函数的调用关系图:

◆ make_monic()

template<typename CoeffType>

Polynomial LMCAS::Polynomial< CoeffType >::make_monic ( ) const

inline

首一化(使首项系数为 1)

返回: 首一多项式

在文件 polynomial.hpp 第 324 行定义.

                                  {
        if (is_zero()) return *this;
        CoeffType lc = lead_coeff();
        if (lc == CoeffType(1)) return *this;
 
        Polynomial res(variable_name);
        res.coeffs.reserve(coeffs.size());
        for (const auto& c : coeffs) {
            res.coeffs.push_back(c / lc);
        }
        return res;
    }

被这些函数引用 LMCAS::polynomial_solver_detail::bounded_rational_root_search(), LMCAS::anonymous_namespace{univariate_factor_bridge.cpp}::bridge_factor(), LMCAS::anonymous_namespace{univariate_factor_bridge.cpp}::bridge_inconclusive(), LMCAS::detail::count_real_roots_exact(), LMCAS::factor_univariate_bridge_checked(), LMCAS::find_rational_roots(), LMCAS::detail::isolate_exact_roots(), LMCAS::detail::isolate_real_roots_exact(), LMCAS::detail::make_exact_root_id(), LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::make_sturm_sequence(), LMCAS::anonymous_namespace{integration_rational_factorization.cpp}::rd_factor_piece(), LMCAS::anonymous_namespace{integration_rational_factorization.cpp}::rd_factor_quadratic(), LMCAS::square_free_factorization(), LMCAS::tf_square_free(), LMCAS::zassenhaus_combine_impl(), LMCAS::zc_enumerate(), LMCAS::zc_finalize() , 以及 LMCAS::zc_make_primitive().

这是这个函数的调用关系图:

◆ operator*()

template<typename CoeffType>

Polynomial LMCAS::Polynomial< CoeffType >::operator* ( const Polynomial< CoeffType > & other ) const

inline

多项式乘法

参数

other 乘数

返回: 积多项式

在文件 polynomial.hpp 第 163 行定义.

                                                        {
        require_compatible_variables(other, "Polynomial::operator*");
        const auto& result_var = is_zero() && !other.is_zero()
            ? other.variable_name : variable_name;
        Polynomial res(result_var);
        if (is_zero() || other.is_zero()) { return res; }
        res.coeffs.resize(coeffs.size() + other.coeffs.size() - 1, CoeffType(0));
 
        for (size_t i = 0; i < coeffs.size(); ++i) {
            for (size_t j = 0; j < other.coeffs.size(); ++j) {
                res.coeffs[i + j] = res.coeffs[i + j] + coeffs[i] * other.coeffs[j];
            }
        }
        res.trim();
        return res;
    }

◆ operator+()

template<typename CoeffType>

Polynomial LMCAS::Polynomial< CoeffType >::operator+ ( const Polynomial< CoeffType > & other ) const

inline

多项式加法

参数

other 加数

返回: 和多项式

在文件 polynomial.hpp 第 119 行定义.

                                                        {
        require_compatible_variables(other, "Polynomial::operator+");
        const auto& result_var = is_zero() && !other.is_zero()
            ? other.variable_name : variable_name;
        Polynomial res(result_var);
        size_t n = std::max(coeffs.size(), other.coeffs.size());
        res.coeffs.resize(n);
 
        for (size_t i = 0; i < n; ++i) {
            CoeffType a = (i < coeffs.size()) ? coeffs[i] : CoeffType(0);
            CoeffType b = (i < other.coeffs.size()) ? other.coeffs[i] : CoeffType(0);
            res.coeffs[i] = a + b;
        }
        res.trim();
        return res;
    }

◆ operator-()

template<typename CoeffType>

Polynomial LMCAS::Polynomial< CoeffType >::operator- ( const Polynomial< CoeffType > & other ) const

inline

多项式减法

参数

other 减数

返回: 差多项式

在文件 polynomial.hpp 第 141 行定义.

                                                        {
         require_compatible_variables(other, "Polynomial::operator-");
         const auto& result_var = is_zero() && !other.is_zero()
             ? other.variable_name : variable_name;
         Polynomial res(result_var);
         size_t n = std::max(coeffs.size(), other.coeffs.size());
         res.coeffs.resize(n);
 
         for (size_t i = 0; i < n; ++i) {
             CoeffType a = (i < coeffs.size()) ? coeffs[i] : CoeffType(0);
             CoeffType b = (i < other.coeffs.size()) ? other.coeffs[i] : CoeffType(0);
             res.coeffs[i] = a - b;
         }
         res.trim();
         return res;
    }

◆ operator==()

template<typename CoeffType>

bool LMCAS::Polynomial< CoeffType >::operator== ( const Polynomial< CoeffType > & other ) const

inline

多项式判等

参数

other 比较对象

返回: 同一命名变量环内系数完全相同返回 true；所有零多项式相等

在文件 polynomial.hpp 第 185 行定义.

                                                 {
         if (degree() != other.degree()) {
             return false;
         }
         if (!variables_compatible(other)) {
             return false;
         }
         for (size_t i = 0; i < coeffs.size(); ++i) {
             if (coeffs[i] != other.coeffs[i]) {
                 return false;
             }
         }
         return true;
    }

◆ primitive_part()

template<typename CoeffType>

Polynomial< CoeffType > LMCAS::Polynomial< CoeffType >::primitive_part ( ) const

inline

计算多项式的本原部分(除以容度)

返回: 本原多项式

在文件 polynomial_division.hpp 第 26 行定义.

                                                                         {
    if (is_zero()) return *this;
    CoeffType c = content();
    if (c == CoeffType(0)) return *this;
 
    Polynomial res = *this;
    if (c != CoeffType(1)) {
        for (auto& val : res.coeffs) {
            val = val / c;
        }
    }
 
    if (res.lead_coeff() < CoeffType(0)) {
        for (auto& val : res.coeffs) {
            val = CoeffType(0) - val;
        }
    }
    return res;
}

引用了 Polynomial(), LMCAS::c, coeffs, content(), is_zero() , 以及 lead_coeff().

函数调用图:

◆ pseudo_div_mod()

template<typename CoeffType>

std::pair< Polynomial< CoeffType >, Polynomial< CoeffType > > LMCAS::Polynomial< CoeffType >::pseudo_div_mod ( const Polynomial< CoeffType > & other ) const

inline

通过系数缩放执行伪除法,运算保持在原系数环

参数

other 除数多项式

返回: pair(伪商, 伪余数)

异常

std::runtime_error	除数为零多项式时抛出
std::invalid_argument	两个非零操作数的变量名不同时抛出

在文件 polynomial_division.hpp 第 48 行定义.

                                                                              {
    if (other.is_zero()) throw std::runtime_error("Division by zero polynomial");
    require_compatible_variables(other, "Polynomial::pseudo_div_mod");
    if (is_zero()) {
        return {Polynomial(other.variable_name), Polynomial(other.variable_name)};
    }
 
    int deg_rem = degree();
    int deg_div = other.degree();
 
    if (deg_rem < deg_div) {
         return {Polynomial(variable_name), *this};
    }
 
    Polynomial remainder = *this;
    Polynomial quotient(variable_name);
    CoeffType lc_div = other.lead_coeff();
 
    int delta = deg_rem - deg_div;
    quotient.coeffs.resize(delta + 1, CoeffType(0));
 
    while (deg_rem >= deg_div && !remainder.is_zero()) {
         int current_diff = deg_rem - deg_div;
         CoeffType lc_rem = remainder.lead_coeff();
 
         for (auto& c : quotient.coeffs) c = c * lc_div;
 
         quotient.coeffs[current_diff] = quotient.coeffs[current_diff] + lc_rem;
 
         Polynomial term(variable_name);
         term.coeffs.resize(current_diff + 1, CoeffType(0));
         term.coeffs[current_diff] = lc_rem;
 
         for(auto& c : remainder.coeffs) c = c * lc_div;
 
         for (size_t i = 0; i < other.coeffs.size(); ++i) {
             size_t target_idx = i + current_diff;
 
             if (target_idx < remainder.coeffs.size()) {
                remainder.coeffs[target_idx] = remainder.coeffs[target_idx] - other.coeffs[i] * lc_rem;
             }
 
         }
 
         remainder.trim();
         deg_rem = remainder.degree();
    }
 
    return {quotient, remainder};
}

引用了 Polynomial(), LMCAS::c, coeffs, degree(), is_zero(), lead_coeff(), require_compatible_variables(), trim() , 以及 variable_name.

被这些函数引用 pseudo_div_mod_rem().

函数调用图:

这是这个函数的调用关系图:

◆ pseudo_div_mod_rem()

template<typename CoeffType>

Polynomial< CoeffType > LMCAS::Polynomial< CoeffType >::pseudo_div_mod_rem ( const Polynomial< CoeffType > & other ) const

inline

伪除法取余数

参数

other 除数多项式

返回: 伪余数

在文件 polynomial_division.hpp 第 101 行定义.

                                                                                  {
 
    return pseudo_div_mod(other).second;
}

引用了 Polynomial() , 以及 pseudo_div_mod().

函数调用图:

◆ require_compatible_variables()

template<typename CoeffType>

void LMCAS::Polynomial< CoeffType >::require_compatible_variables	(	const Polynomial< CoeffType > &	other,
		const char *	operation ) const

inlineprivate

在文件 polynomial.hpp 第 382 行定义.

                                                                                            {
        if (!variables_compatible(other)) {
            throw std::invalid_argument(
                std::string(operation) + ": variable name mismatch ('" +
                variable_name + "' vs '" + other.variable_name + "')");
        }
    }

被这些函数引用 pseudo_div_mod().

这是这个函数的调用关系图:

◆ square_free_part()

template<typename CoeffType>

Polynomial< CoeffType > LMCAS::Polynomial< CoeffType >::square_free_part ( ) const

inline

计算无平方因子部分

返回: 去除重因子后的多项式

在文件 polynomial_division.hpp 第 153 行定义.

                                                                           {
 
    if (degree() <= 0) return *this;
 
    Polynomial deriv = differentiate();
    Polynomial g = gcd(*this, deriv);
 
    auto [q, r] = div_mod(g);
 
    if constexpr (std::is_same_v<CoeffType, Rational>) {
        return q.make_monic();
    }
    return q;
}

引用了 Polynomial(), degree(), differentiate(), div_mod(), gcd() , 以及 LMCAS::r.

被这些函数引用 LMCAS::detail::count_real_roots_exact(), LMCAS::detail::isolate_exact_roots(), LMCAS::detail::isolate_real_roots_exact(), LMCAS::detail::make_exact_root_id() , 以及 LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::make_sturm_sequence().

函数调用图:

这是这个函数的调用关系图:

◆ to_string()

template<typename CoeffType>

std::string LMCAS::Polynomial< CoeffType >::to_string ( ) const

inline

转换为字符串表示

返回: 多项式的字符串形式

在文件 polynomial.hpp 第 363 行定义.

                                {
        if (is_zero()) {
            return "0";
        }
        std::string s;
        for (int i = degree(); i >= 0; --i) {
            if (coeffs[i] == CoeffType(0)) {
                continue;
            }
            append_string_term(s, coeffs[i], i);
        }
        return s.empty() ? "0" : s;
    }

◆ trim()

template<typename CoeffType>

void LMCAS::Polynomial< CoeffType >::trim ( )

inline

去除高次零系数

在文件 polynomial.hpp 第 85 行定义.

                {
        while (coeffs.size() > 0 && coeffs.back() == CoeffType(0)) {
            coeffs.pop_back();
        }
    }

被这些函数引用 LMCAS::detail::complex_root::clear_denominators(), LMCAS::polynomial_solver_detail::convert_to_rational_poly(), LMCAS::Polynomial< Rational >::differentiate(), LMCAS::Polynomial< Rational >::div_mod(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::edge_image(), LMCAS::anonymous_namespace{residual_verification.cpp}::has_zero_root_remainder(), LMCAS::detail::make_exact_root_id(), LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::make_sturm_sequence(), LMCAS::detail::anonymous_namespace{exact_algebraic.cpp}::monic(), LMCAS::Polynomial< Rational >::operator*(), LMCAS::Polynomial< Rational >::operator+(), LMCAS::Polynomial< Rational >::operator-(), pseudo_div_mod(), LMCAS::anonymous_namespace{integration_rational_collection.cpp}::rd_normalize_fraction(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_projection.cpp}::resultant_determinant() , 以及 LMCAS::detail::complex_root::scale_poly().

这是这个函数的调用关系图:

◆ variables_compatible()

template<typename CoeffType>

bool LMCAS::Polynomial< CoeffType >::variables_compatible ( const Polynomial< CoeffType > & other ) const

inlineprivate

在文件 polynomial.hpp 第 378 行定义.

                                                             {
        return variable_name == other.variable_name || is_zero() || other.is_zero();
    }

类成员变量说明

◆ coeffs

template<typename CoeffType>

std::vector<CoeffType> LMCAS::Polynomial< CoeffType >::coeffs

系数数组,coeffs[i] 为 x^i 的系数

在文件 polynomial.hpp 第 55 行定义.

◆ variable_name

template<typename CoeffType>

std::string LMCAS::Polynomial< CoeffType >::variable_name

变量名

在文件 polynomial.hpp 第 56 行定义.

该类的文档由以下文件生成:

include/polynomial.hpp
include/polynomial_division.hpp

Public 成员函数

静态 Public 成员函数

Public 属性

Private 成员函数

详细描述

构造及析构函数说明

◆ Polynomial() [1/3]

◆ Polynomial() [2/3]

◆ Polynomial() [3/3]

成员函数说明

◆ append_string_term()

◆ content()

◆ degree()

◆ differentiate()

◆ div_mod()

◆ eval()

◆ gcd()

◆ gcd_coeff()

◆ is_zero()

◆ lead_coeff()

◆ make_monic()

◆ operator*()

◆ operator+()

◆ operator-()

◆ operator==()

◆ primitive_part()

◆ pseudo_div_mod()

◆ pseudo_div_mod_rem()

◆ require_compatible_variables()

◆ square_free_part()

◆ to_string()

◆ trim()

◆ variables_compatible()

类成员变量说明

◆ coeffs

◆ variable_name