LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp} 命名空间参考

类
struct	ExactInequalityRoot

函数
Result< void >	append_exact_factor_roots (std::vector< ExactInequalityRoot > &roots, const Polynomial< Rational > &factor, int multiplicity, const std::string &variable, detail::RewriteBudget &budget, std::size_t &root_nodes)
void	check_interval_forest (const std::vector< Interval > &intervals, detail::RewriteBudget &budget)
bool	constant_satisfies (const Rational &value, InequalityType type)
std::vector< Interval >	exact_polynomial_sign_intervals (const Polynomial< Rational > &polynomial, const std::vector< ExactInequalityRoot > &roots, InequalityType type)
Endpoint	finite_endpoint (const std::shared_ptr< SymbolicExpr > &value, bool strict)
bool	rational_is_negative (const Rational &value)
std::shared_ptr< SymbolicExpr >	rational_polynomial_expression (const Polynomial< Rational > &polynomial, detail::RewriteBudget &budget)
Result< IntervalUnion >	solve_exact_affine_inequality_impl (const Polynomial< Rational > &polynomial, InequalityType type, ComputationContext &context)
Result< IntervalUnion >	solve_exact_polynomial_inequality_impl (const Polynomial< Rational > &polynomial, InequalityType type, ComputationContext &context)
Result< void >	sort_exact_inequality_roots (std::vector< ExactInequalityRoot > &roots, ComputationContext &context)
Result< void >	verify_quadratic_boundary (const Polynomial< Rational > &polynomial, const std::shared_ptr< SymbolicExpr > &boundary, const Rational &rational_part, const Rational &radical_coefficient, const Rational &radicand, ComputationContext &context)

变量
constexpr const char *	kCheckedInequalityOperation = "solve_inequality_checked"

---

类说明

LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::ExactInequalityRoot

struct LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::ExactInequalityRoot

在文件 inequality_solver_polynomial.cpp 第 299 行定义.

LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::ExactInequalityRoot 的协作图:

类成员
ExactRealAlgebraic	algebraic
shared_ptr< SymbolicExpr >	expression
int	multiplicity = 1

函数说明

append_exact_factor_roots()

Result< void > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::append_exact_factor_roots	(	std::vector< ExactInequalityRoot > &	roots,
		const Polynomial< Rational > &	factor,
		int	multiplicity,
		const std::string &	variable,
		detail::RewriteBudget &	budget,
		std::size_t &	root_nodes )

在文件 inequality_solver_polynomial.cpp 第 326 行定义.

                           {
    auto& context = budget.context();
    auto isolated = isolate_real_roots_checked(factor, context);
    if (!isolated) {
        return Result<void>::failure(isolated.error());
    }
    const auto& intervals = isolated.value();
    auto factor_expression = rational_polynomial_expression(factor, budget);
    for (std::size_t index = 0; index < intervals.size(); ++index) {
        auto algebraic = LMCAS::detail::make_exact_real_algebraic(
            factor, index, static_cast<std::size_t>(multiplicity), context);
        if (!algebraic) {
            return Result<void>::failure(algebraic.error());
        }
        roots.push_back(ExactInequalityRoot{
            SymbolicExpr::root_of(
                factor_expression, variable,
                static_cast<int>(index)),
            std::move(algebraic.value()),
            multiplicity});
        root_nodes = budget.append_size(root_nodes, budget.measure(detail::node(roots.back().expression)));
    }
    return Result<void>::success();
}

引用了 append_exact_factor_roots(), LMCAS::detail::RewriteBudget::append_size(), LMCAS::context, LMCAS::detail::RewriteBudget::context(), LMCAS::Result< T >::failure(), LMCAS::isolate_real_roots_checked(), LMCAS::detail::make_exact_real_algebraic(), LMCAS::detail::RewriteBudget::measure(), LMCAS::detail::node(), rational_polynomial_expression(), LMCAS::roots(), LMCAS::Result< T >::success() , 以及 LMCAS::variable.

被这些函数引用 append_exact_factor_roots() , 以及 solve_exact_polynomial_inequality_impl().

函数调用图:

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

check_interval_forest()

void LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::check_interval_forest	(	const std::vector< Interval > &	intervals,
		detail::RewriteBudget &	budget )

在文件 inequality_solver_polynomial.cpp 第 25 行定义.

                                                        {
    std::size_t nodes = 0;
    for (const auto& interval : intervals) {
        nodes = budget.append_size(nodes, budget.measure(detail::node(interval.lower.value)));
        nodes = budget.append_size(nodes, budget.measure(detail::node(interval.upper.value)));
    }
}

引用了 LMCAS::detail::RewriteBudget::append_size(), check_interval_forest(), LMCAS::interval(), LMCAS::detail::RewriteBudget::measure(), LMCAS::detail::node() , 以及 LMCAS::Result< T >::value().

被这些函数引用 check_interval_forest(), solve_exact_affine_inequality_impl() , 以及 solve_exact_polynomial_inequality_impl().

函数调用图:

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

constant_satisfies()

bool LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::constant_satisfies	(	const Rational &	value,
		InequalityType	type )

在文件 inequality_solver_polynomial.cpp 第 38 行定义.

                                                                    {
    const bool zero = value == Rational(0);
    const bool negative = rational_is_negative(value);
    switch (type) {
        case InequalityType::GreaterThan: return !negative && !zero;
        case InequalityType::GreaterEqual: return !negative;
        case InequalityType::LessThan: return negative;
        case InequalityType::LessEqual: return negative || zero;
    }
    return false;
}

引用了 constant_satisfies(), LMCAS::GreaterEqual, LMCAS::GreaterThan, LMCAS::LessEqual, LMCAS::LessThan, rational_is_negative() , 以及 LMCAS::value.

被这些函数引用 constant_satisfies() , 以及 solve_exact_affine_inequality_impl().

函数调用图:

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

exact_polynomial_sign_intervals()

std::vector< Interval > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::exact_polynomial_sign_intervals	(	const Polynomial< Rational > &	polynomial,
		const std::vector< ExactInequalityRoot > &	roots,
		InequalityType	type )

在文件 inequality_solver_polynomial.cpp 第 376 行定义.

                                                                      {
    const bool wants_positive =
        type == InequalityType::GreaterThan ||
        type == InequalityType::GreaterEqual;
    const bool strict =
        type == InequalityType::GreaterThan ||
        type == InequalityType::LessThan;
    auto sign_satisfies = [&](int sign_value) {
        return wants_positive ? sign_value > 0 : sign_value < 0;
    };
 
    int sign_value = rational_is_negative(polynomial.lead_coeff()) ? -1 : 1;
    if ((polynomial.degree() & 1) != 0) {
        sign_value = -sign_value;
    }
 
    std::vector<Interval> intervals;
    Endpoint lower = Endpoint::neg_inf();
    for (const auto& root : roots) {
        if (sign_satisfies(sign_value)) {
            intervals.push_back(Interval{
                lower, Endpoint::open(root.expression)});
        }
        if (!strict) {
            intervals.push_back(Interval::point(root.expression));
        }
        lower = Endpoint::open(root.expression);
        if ((root.multiplicity & 1) != 0) {
            sign_value = -sign_value;
        }
    }
    if (sign_satisfies(sign_value)) {
        intervals.push_back(Interval{lower, Endpoint::pos_inf()});
    }
    return intervals;
}

引用了 LMCAS::Polynomial< CoeffType >::degree(), exact_polynomial_sign_intervals(), LMCAS::GreaterEqual, LMCAS::GreaterThan, LMCAS::Polynomial< CoeffType >::lead_coeff(), LMCAS::LessThan, LMCAS::lower, rational_is_negative() , 以及 LMCAS::roots().

被这些函数引用 exact_polynomial_sign_intervals() , 以及 solve_exact_polynomial_inequality_impl().

函数调用图:

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

finite_endpoint()

Endpoint LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::finite_endpoint	(	const std::shared_ptr< SymbolicExpr > &	value,
		bool	strict )

在文件 inequality_solver_polynomial.cpp 第 50 行定义.

                                                                                {
    return strict ? Endpoint::open(value) : Endpoint::closed(value);
}

引用了 finite_endpoint() , 以及 LMCAS::value.

被这些函数引用 finite_endpoint().

函数调用图:

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

rational_is_negative()

bool LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::rational_is_negative

(

const Rational &

value

)

在文件 inequality_solver_polynomial.cpp 第 34 行定义.

                                                 {
    return value.get_numerator().is_negative();
}

引用了 rational_is_negative() , 以及 LMCAS::value.

被这些函数引用 constant_satisfies(), exact_polynomial_sign_intervals(), rational_is_negative() , 以及 solve_exact_affine_inequality_impl().

函数调用图:

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

rational_polynomial_expression()

std::shared_ptr< SymbolicExpr > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::rational_polynomial_expression	(	const Polynomial< Rational > &	polynomial,
		detail::RewriteBudget &	budget )

在文件 inequality_solver_polynomial.cpp 第 305 行定义.

                                                                         {
    auto variable = SymbolicExpr::variable(polynomial.variable_name);
    std::shared_ptr<SymbolicExpr> sum = SymbolicExpr::number(0);
    for (int degree = 0; degree <= polynomial.degree(); ++degree) {
        if (polynomial.coeffs[degree] == Rational(0)) {
            continue;
        }
        auto term = SymbolicExpr::number(polynomial.coeffs[degree]);
        if (degree > 0) {
            auto power = degree == 1
                ? variable
                : SymbolicExpr::power(variable, SymbolicExpr::number(degree));
            term = SymbolicExpr::multiply(term, power);
        }
        sum = SymbolicExpr::add(sum, term);
        budget.measure(detail::node(sum));
    }
    return detail::make_expression_ptr(detail::normalize_node(detail::node(sum), budget));
}

引用了 LMCAS::Polynomial< CoeffType >::coeffs, LMCAS::Polynomial< CoeffType >::degree(), LMCAS::detail::make_expression_ptr(), LMCAS::detail::RewriteBudget::measure(), LMCAS::detail::node(), LMCAS::detail::normalize_node(), rational_polynomial_expression(), LMCAS::variable , 以及 LMCAS::Polynomial< CoeffType >::variable_name.

被这些函数引用 append_exact_factor_roots() , 以及 rational_polynomial_expression().

函数调用图:

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

solve_exact_affine_inequality_impl()

Result< IntervalUnion > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::solve_exact_affine_inequality_impl	(	const Polynomial< Rational > &	polynomial,
		InequalityType	type,
		ComputationContext &	context )

在文件 inequality_solver_polynomial.cpp 第 239 行定义.

                                 {
    auto step = context.consume_steps(1, kCheckedInequalityOperation);
    if (!step) {
        return Result<IntervalUnion>::failure(step.error());
    }
 
    if (polynomial.degree() <= 0) {
        const Rational value = polynomial.is_zero()
            ? Rational(0)
            : polynomial.coeffs[0];
        return Result<IntervalUnion>::success(
            constant_satisfies(value, type)
                ? IntervalUnion::entire_line()
                : IntervalUnion::empty());
    }
 
    if (polynomial.degree() != 1 || polynomial.coeffs.size() < 2) {
        return Result<IntervalUnion>::failure(
            CasErrc::Inconclusive,
            "checked inequality solving currently supports exact polynomials through degree two",
            kCheckedInequalityOperation);
    }
 
    const Rational& intercept = polynomial.coeffs[0];
    const Rational& slope = polynomial.coeffs[1];
    if (slope == Rational(0)) {
        return Result<IntervalUnion>::failure(
            CasErrc::InternalInvariant,
            "affine polynomial has a zero leading coefficient",
            kCheckedInequalityOperation);
    }
 
    const Rational boundary = (Rational(0) - intercept) / slope;
    auto boundary_expr = SymbolicExpr::number(boundary);
    auto nodes = context.require_ast_nodes(1, kCheckedInequalityOperation);
    if (!nodes) {
        return Result<IntervalUnion>::failure(nodes.error());
    }
 
    const bool wants_greater = type == InequalityType::GreaterThan ||
                               type == InequalityType::GreaterEqual;
    const bool strict = type == InequalityType::GreaterThan ||
                        type == InequalityType::LessThan;
    const bool solution_above = wants_greater != rational_is_negative(slope);
    const Endpoint finite = strict
        ? Endpoint::open(boundary_expr)
        : Endpoint::closed(boundary_expr);
    const Interval interval = solution_above
        ? Interval{finite, Endpoint::pos_inf()}
        : Interval{Endpoint::neg_inf(), finite};
    detail::RewriteBudget budget(context, context.limits().max_recursion_depth,
                                 context.limits().max_ast_nodes, kCheckedInequalityOperation);
    check_interval_forest({interval}, budget);
    return Result<IntervalUnion>::success(IntervalUnion::from_single(interval));
}

引用了 check_interval_forest(), LMCAS::Polynomial< CoeffType >::coeffs, constant_satisfies(), LMCAS::context, LMCAS::Polynomial< CoeffType >::degree(), LMCAS::Result< T >::failure(), LMCAS::GreaterEqual, LMCAS::GreaterThan, LMCAS::Inconclusive, LMCAS::InternalInvariant, LMCAS::interval(), LMCAS::Polynomial< CoeffType >::is_zero(), kCheckedInequalityOperation, LMCAS::LessThan, rational_is_negative(), solve_exact_affine_inequality_impl(), LMCAS::Result< T >::success() , 以及 LMCAS::value.

被这些函数引用 solve_exact_affine_inequality_impl().

函数调用图:

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

solve_exact_polynomial_inequality_impl()

Result< IntervalUnion > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::solve_exact_polynomial_inequality_impl	(	const Polynomial< Rational > &	polynomial,
		InequalityType	type,
		ComputationContext &	context )

在文件 inequality_solver_polynomial.cpp 第 415 行定义.

                                 {
    auto factors = square_free_factorization(polynomial);
    std::vector<ExactInequalityRoot> roots;
    try {
        detail::RewriteBudget budget(context, context.limits().max_recursion_depth,
                                     context.limits().max_ast_nodes, kCheckedInequalityOperation);
        std::size_t root_nodes = 0;
        for (const auto& [factor, multiplicity] : factors) {
            if (factor.degree() < 1) {
                continue;
            }
            auto appended = append_exact_factor_roots(
                roots, factor, multiplicity, polynomial.variable_name, budget, root_nodes);
            if (!appended) {
                return Result<IntervalUnion>::failure(appended.error());
            }
        }
        auto sorted = sort_exact_inequality_roots(roots, context);
        if (!sorted) {
            return Result<IntervalUnion>::failure(sorted.error());
        }
        auto intervals = exact_polynomial_sign_intervals(polynomial, roots, type);
        check_interval_forest(intervals, budget);
        return IntervalUnion::from_intervals_checked(std::move(intervals), context);
    } catch (const CasError& error) {
        return Result<IntervalUnion>::failure(error);
    } catch (const std::length_error& error) {
        return Result<IntervalUnion>::failure(
            CasErrc::ResourceLimit, error.what(), kCheckedInequalityOperation);
    } catch (const std::bad_alloc&) {
        return Result<IntervalUnion>::failure(
            CasErrc::ResourceLimit,
            "polynomial inequality root allocation failed",
            kCheckedInequalityOperation);
    } catch (const std::exception& error) {
        return Result<IntervalUnion>::failure(
            CasErrc::InternalInvariant, error.what(),
            kCheckedInequalityOperation);
    }
 
}

引用了 append_exact_factor_roots(), check_interval_forest(), LMCAS::context, exact_polynomial_sign_intervals(), LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, kCheckedInequalityOperation, LMCAS::ResourceLimit, LMCAS::roots(), solve_exact_polynomial_inequality_impl(), sort_exact_inequality_roots(), LMCAS::square_free_factorization() , 以及 LMCAS::Polynomial< CoeffType >::variable_name.

被这些函数引用 solve_exact_polynomial_inequality_impl().

函数调用图:

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

sort_exact_inequality_roots()

Result< void > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::sort_exact_inequality_roots	(	std::vector< ExactInequalityRoot > &	roots,
		ComputationContext &	context )

在文件 inequality_solver_polynomial.cpp 第 354 行定义.

                                                                        {
    for (std::size_t i = 1; i < roots.size(); ++i) {
        auto root = std::move(roots[i]);
        std::size_t position = i;
        while (position > 0) {
            auto order = LMCAS::detail::compare_exact_real_algebraic(
                roots[position - 1].algebraic, root.algebraic, context);
            if (!order) {
                return Result<void>::failure(order.error());
            }
            if (order.value() <= 0) {
                break;
            }
            roots[position] = std::move(roots[position - 1]);
            --position;
        }
        roots[position] = std::move(root);
    }
    return Result<void>::success();
}

引用了 LMCAS::detail::compare_exact_real_algebraic(), LMCAS::context, LMCAS::Result< T >::failure(), LMCAS::order, LMCAS::roots(), sort_exact_inequality_roots() , 以及 LMCAS::Result< T >::success().

被这些函数引用 solve_exact_polynomial_inequality_impl() , 以及 sort_exact_inequality_roots().

函数调用图:

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

verify_quadratic_boundary()

Result< void > LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::verify_quadratic_boundary	(	const Polynomial< Rational > &	polynomial,
		const std::shared_ptr< SymbolicExpr > &	boundary,
		const Rational &	rational_part,
		const Rational &	radical_coefficient,
		const Rational &	radicand,
		ComputationContext &	context )

在文件 inequality_solver_polynomial.cpp 第 54 行定义.

                                 {
    auto steps = context.consume_steps(2, kCheckedInequalityOperation);
    if (!steps) {
        return steps;
    }
 
    if (!boundary || !LMCAS::detail::node(boundary) || polynomial.coeffs.size() < 3) {
        return Result<void>::failure(
            CasErrc::InternalInvariant,
            "quadratic boundary verification could not construct an expression",
            kCheckedInequalityOperation);
    }
 
    const Rational& constant = polynomial.coeffs[0];
    const Rational& linear = polynomial.coeffs[1];
    const Rational& quadratic = polynomial.coeffs[2];
    const Rational residual_rational =
        quadratic * (rational_part * rational_part +
                     radical_coefficient * radical_coefficient * radicand) +
        linear * rational_part + constant;
    const Rational residual_radical =
        Rational(2) * quadratic * rational_part * radical_coefficient +
        linear * radical_coefficient;
    if (residual_rational != Rational(0) ||
        residual_radical != Rational(0)) {
        return Result<void>::failure(
            CasErrc::Inconclusive,
            "quadratic boundary could not be verified by exact substitution",
            kCheckedInequalityOperation);
    }
    return Result<void>::success();
}

引用了 LMCAS::Polynomial< CoeffType >::coeffs, LMCAS::context, LMCAS::Result< T >::failure(), LMCAS::Inconclusive, LMCAS::InternalInvariant, kCheckedInequalityOperation, LMCAS::detail::node(), LMCAS::steps, LMCAS::Result< T >::success() , 以及 verify_quadratic_boundary().

被这些函数引用 verify_quadratic_boundary().

函数调用图:

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

变量说明

kCheckedInequalityOperation

const char* LMCAS::anonymous_namespace{inequality_solver_polynomial.cpp}::kCheckedInequalityOperation = "solve_inequality_checked"

constexpr

在文件 inequality_solver_polynomial.cpp 第 23 行定义.

被这些函数引用 solve_exact_affine_inequality_impl(), solve_exact_polynomial_inequality_impl() , 以及 verify_quadratic_boundary().