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

类
class	RecursionFrame

函数
Result< void >	check_term_budget (std::size_t lhs_terms, std::size_t rhs_terms, ComputationContext &context)
Result< void >	collect_polynomial_operands (const std::vector< std::shared_ptr< const SymbolicNode > > &operands, std::set< std::string > &variables, ComputationContext &context)
Result< void >	collect_polynomial_variables (const std::shared_ptr< const SymbolicNode > &node, std::set< std::string > &variables, ComputationContext &context)
MultiPoly	make_monic (const MultiPoly &polynomial)
Result< MultiPoly >	multiply_checked (const MultiPoly &lhs, const MultiPoly &rhs, ComputationContext &context)
Result< std::shared_ptr< SymbolicExpr > >	multivariate_polynomial_to_expression (const MultiPoly &polynomial, detail::RewriteBudget &budget)
Result< MultiPoly >	node_to_multivariate_polynomial (const std::shared_ptr< const SymbolicNode > &node, const std::vector< std::string > &variables, ComputationContext &context)
Result< std::size_t >	polynomial_exponent (const std::shared_ptr< const SymbolicNode > &node)
Result< std::shared_ptr< SymbolicExpr > >	polynomial_term_to_expression (const Monomial &monomial, const Rational &coefficient, const MultiPoly &polynomial, detail::RewriteBudget &budget)
Result< MultiPoly >	power_to_polynomial (const std::shared_ptr< const PowerNode > &power, const std::vector< std::string > &variables, ComputationContext &context)
Result< MultiPoly >	sum_to_polynomial (const std::shared_ptr< const AddNode > &addition, const std::vector< std::string > &variables, ComputationContext &context)
Result< void >	verify_gcd_candidate (const MultiPoly &lhs, const MultiPoly &rhs, const MultiPoly &gcd)

变量
constexpr const char *	kOperation = "symbolic_polynomial_gcd"

函数说明

check_term_budget()

Result< void > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::check_term_budget	(	std::size_t	lhs_terms,
		std::size_t	rhs_terms,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 133 行定义.

                                                            {
    const std::size_t limit = context.limits().max_expansion_terms;
    if (lhs_terms != 0 && rhs_terms > limit / lhs_terms) {
        return Result<void>::failure(
            CasErrc::ResourceLimit,
            "polynomial expansion term budget exhausted", kOperation);
    }
    return context.consume_steps(lhs_terms * rhs_terms + 1, kOperation);
}

引用了 check_term_budget(), LMCAS::context, LMCAS::Result< T >::failure(), kOperation , 以及 LMCAS::ResourceLimit.

被这些函数引用 check_term_budget() , 以及 multiply_checked().

函数调用图:

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

collect_polynomial_operands()

Result< void > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::collect_polynomial_operands	(	const std::vector< std::shared_ptr< const SymbolicNode > > &	operands,
		std::set< std::string > &	variables,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 43 行定义.

                                                               {
    for (const auto& operand : operands) {
        auto result = collect_polynomial_variables(operand, variables, context);
        if (!result) { return result; }
    }
    return Result<void>::success();
}

引用了 collect_polynomial_operands(), collect_polynomial_variables(), LMCAS::context , 以及 LMCAS::Result< T >::success().

被这些函数引用 collect_polynomial_operands() , 以及 collect_polynomial_variables().

函数调用图:

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

collect_polynomial_variables()

Result< void > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::collect_polynomial_variables	(	const std::shared_ptr< const SymbolicNode > &	node,
		std::set< std::string > &	variables,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 53 行定义.

                                 {
    auto entered = context.enter_recursion(kOperation);
    if (!entered) { return entered; }
    RecursionFrame frame(context);
 
    if (!node) {
        return Result<void>::failure(
            CasErrc::InternalInvariant, "polynomial contains a null node",
            kOperation);
    }
    if (std::dynamic_pointer_cast<const NumberNode>(node)) {
        return Result<void>::success();
    }
    if (auto variable = std::dynamic_pointer_cast<const VariableNode>(node)) {
        if (variable->is_constant()) {
            return Result<void>::failure(CasErrc::UnsupportedExpression,
                "mathematical constants are not rational polynomial variables",
                kOperation);
        }
        variables.insert(variable->name());
        return Result<void>::success();
    }
    if (auto addition = std::dynamic_pointer_cast<const AddNode>(node)) {
        return collect_polynomial_operands(addition->operands(), variables, context);
    }
    if (auto product = std::dynamic_pointer_cast<const MultiplyNode>(node)) {
        return collect_polynomial_operands(product->operands(), variables, context);
    }
    if (auto power = std::dynamic_pointer_cast<const PowerNode>(node)) {
        auto exponent = std::dynamic_pointer_cast<const NumberNode>(power->exponent());
        if (!exponent) {
            return Result<void>::failure(
                CasErrc::UnsupportedExpression,
                "polynomial exponents must be exact nonnegative integers",
                kOperation);
        }
        return collect_polynomial_variables(power->base(), variables, context);
    }
    return Result<void>::failure(
        CasErrc::UnsupportedExpression,
        "expression is outside the exact rational polynomial domain",
        kOperation);
}

引用了 collect_polynomial_operands(), collect_polynomial_variables(), LMCAS::context, LMCAS::exponent, LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, kOperation, LMCAS::Result< T >::success(), LMCAS::UnsupportedExpression , 以及 LMCAS::variable.

被这些函数引用 collect_polynomial_operands() , 以及 collect_polynomial_variables().

函数调用图:

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

make_monic()

MultiPoly LMCAS::anonymous_namespace{symbolic_gcd.cpp}::make_monic

(

const MultiPoly &

polynomial

)

在文件 symbolic_gcd.cpp 第 285 行定义.

                                                  {
    if (polynomial.is_zero()) { return polynomial; }
    const Rational leading = polynomial.terms().front().second;
    return polynomial * (Rational(1) / leading);
}

引用了 make_monic().

被这些函数引用 make_monic() , 以及 verify_gcd_candidate().

函数调用图:

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

multiply_checked()

Result< MultiPoly > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::multiply_checked	(	const MultiPoly &	lhs,
		const MultiPoly &	rhs,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 145 行定义.

                                                                {
    auto budget = check_term_budget(
        static_cast<std::size_t>(lhs.num_terms()),
        static_cast<std::size_t>(rhs.num_terms()), context);
    if (!budget) { return Result<MultiPoly>::failure(budget.error()); }
    MultiPoly result = lhs * rhs;
    if (static_cast<std::size_t>(result.num_terms()) >
        context.limits().max_expansion_terms) {
        return Result<MultiPoly>::failure(
            CasErrc::ResourceLimit,
            "polynomial expansion term budget exhausted", kOperation);
    }
    return Result<MultiPoly>::success(std::move(result));
}

引用了 check_term_budget(), LMCAS::context, LMCAS::Result< T >::failure(), kOperation, multiply_checked(), LMCAS::ResourceLimit, LMCAS::rhs , 以及 LMCAS::Result< T >::success().

被这些函数引用 multiply_checked(), node_to_multivariate_polynomial() , 以及 power_to_polynomial().

函数调用图:

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

multivariate_polynomial_to_expression()

Result< std::shared_ptr< SymbolicExpr > > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::multivariate_polynomial_to_expression	(	const MultiPoly &	polynomial,
		detail::RewriteBudget &	budget )

在文件 symbolic_gcd.cpp 第 291 行定义.

                                 {
    if (polynomial.is_zero()) {
        budget.require_nodes(1);
        return Result<std::shared_ptr<SymbolicExpr>>::success(
            SymbolicExpr::number(0));
    }
 
    std::vector<std::shared_ptr<SymbolicExpr>> terms;
    terms.reserve(polynomial.terms().size());
    std::size_t nodes = 0;
    for (const auto& [monomial, coefficient] : polynomial.terms()) {
        auto term = polynomial_term_to_expression(
            monomial, coefficient, polynomial, budget);
        if (!term) { return term; }
        nodes = budget.append_size(nodes, budget.measure(detail::node(term.value())));
        terms.push_back(std::move(term.value()));
    }
 
    auto expression = terms.front();
    for (std::size_t index = 1; index < terms.size(); ++index) {
        expression = SymbolicExpr::add(expression, terms[index]);
        budget.measure(detail::node(expression));
    }
    return Result<std::shared_ptr<SymbolicExpr>>::success(std::move(expression));
}

引用了 LMCAS::detail::RewriteBudget::append_size(), LMCAS::detail::RewriteBudget::measure(), multivariate_polynomial_to_expression(), LMCAS::detail::node(), polynomial_term_to_expression() , 以及 LMCAS::detail::RewriteBudget::require_nodes().

被这些函数引用 multivariate_polynomial_to_expression().

函数调用图:

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

node_to_multivariate_polynomial()

Result< MultiPoly > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::node_to_multivariate_polynomial	(	const std::shared_ptr< const SymbolicNode > &	node,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 236 行定义.

                                 {
    auto entered = context.enter_recursion(kOperation);
    if (!entered) { return Result<MultiPoly>::failure(entered.error()); }
    RecursionFrame frame(context);
 
    if (auto number = std::dynamic_pointer_cast<const NumberNode>(node)) {
        return Result<MultiPoly>::success(
            MultiPoly(exact_number_as_rational(*number), variables));
    }
    if (auto variable = std::dynamic_pointer_cast<const VariableNode>(node)) {
        Monomial monomial(variables.size(), 0);
        auto position = std::find(variables.begin(), variables.end(),
                                  variable->name());
        if (position == variables.end()) {
            return Result<MultiPoly>::failure(
                CasErrc::InternalInvariant,
                "polynomial variable collection is inconsistent", kOperation);
        }
        monomial[static_cast<std::size_t>(position - variables.begin())] = 1;
        return Result<MultiPoly>::success(MultiPoly(
            {{std::move(monomial), Rational(1)}}, variables));
    }
    if (auto addition = std::dynamic_pointer_cast<const AddNode>(node)) {
        return sum_to_polynomial(addition, variables, context);
    }
    if (auto product = std::dynamic_pointer_cast<const MultiplyNode>(node)) {
        MultiPoly result(Rational(1), variables);
        for (const auto& operand : product->operands()) {
            auto converted = node_to_multivariate_polynomial(
                operand, variables, context);
            if (!converted) { return converted; }
            auto multiplied = multiply_checked(result, converted.value(), context);
            if (!multiplied) { return multiplied; }
            result = std::move(multiplied.value());
        }
        return Result<MultiPoly>::success(std::move(result));
    }
    if (auto power = std::dynamic_pointer_cast<const PowerNode>(node)) {
        return power_to_polynomial(power, variables, context);
    }
    return Result<MultiPoly>::failure(
        CasErrc::UnsupportedExpression,
        "expression is outside the exact rational polynomial domain",
        kOperation);
}

引用了 LMCAS::context, LMCAS::exact_number_as_rational(), LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, kOperation, multiply_checked(), node_to_multivariate_polynomial(), power_to_polynomial(), LMCAS::Result< T >::success(), sum_to_polynomial(), LMCAS::UnsupportedExpression , 以及 LMCAS::variable.

被这些函数引用 node_to_multivariate_polynomial(), power_to_polynomial() , 以及 sum_to_polynomial().

函数调用图:

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

polynomial_exponent()

Result< std::size_t > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::polynomial_exponent

(

const std::shared_ptr< const SymbolicNode > &

node

)

在文件 symbolic_gcd.cpp 第 100 行定义.

                                                   {
    auto number = std::dynamic_pointer_cast<const NumberNode>(node);
    if (!number) {
        return Result<std::size_t>::failure(
            CasErrc::UnsupportedExpression,
            "polynomial exponents must be exact nonnegative integers",
            kOperation);
    }
 
    BigInt integer;
    if (std::holds_alternative<BigInt>(number->value())) {
        integer = std::get<BigInt>(number->value());
    } else {
        const Rational& rational = std::get<Rational>(number->value());
        if (!rational.is_integer()) {
            return Result<std::size_t>::failure(
                CasErrc::UnsupportedExpression,
                "polynomial exponents must be integers", kOperation);
        }
        integer = rational.to_bigint();
    }
 
    const auto value = integer.try_to_int64();
    if (!value || *value < 0) {
        return Result<std::size_t>::failure(
            CasErrc::UnsupportedExpression,
            "polynomial exponents must be representable nonnegative integers",
            kOperation);
    }
    return Result<std::size_t>::success(static_cast<std::size_t>(*value));
}

引用了 LMCAS::Result< T >::failure(), LMCAS::integer, kOperation, polynomial_exponent(), LMCAS::rational(), LMCAS::Result< T >::success(), LMCAS::UnsupportedExpression , 以及 LMCAS::value.

被这些函数引用 polynomial_exponent() , 以及 power_to_polynomial().

函数调用图:

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

polynomial_term_to_expression()

Result< std::shared_ptr< SymbolicExpr > > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::polynomial_term_to_expression	(	const Monomial &	monomial,
		const Rational &	coefficient,
		const MultiPoly &	polynomial,
		detail::RewriteBudget &	budget )

在文件 symbolic_gcd.cpp 第 219 行定义.

                                                              {
    auto step = budget.context().consume_steps(1, kOperation);
    if (!step) { return Result<std::shared_ptr<SymbolicExpr>>::failure(step.error()); }
 
    auto factors = detail::multipoly_term_factors(
        monomial, coefficient, polynomial.variables());
    std::size_t nodes = 0;
    for (const auto& factor : factors) {
        nodes = budget.append_size(nodes, budget.measure(detail::node(factor)));
    }
    auto result = detail::multiply_expression_factors(factors);
    budget.measure(detail::node(result));
    return Result<std::shared_ptr<SymbolicExpr>>::success(std::move(result));
}

引用了 LMCAS::detail::RewriteBudget::append_size(), LMCAS::ComputationContext::consume_steps(), LMCAS::detail::RewriteBudget::context(), kOperation, LMCAS::detail::RewriteBudget::measure(), LMCAS::detail::multiply_expression_factors(), LMCAS::detail::multipoly_term_factors(), LMCAS::detail::node() , 以及 polynomial_term_to_expression().

被这些函数引用 multivariate_polynomial_to_expression() , 以及 polynomial_term_to_expression().

函数调用图:

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

power_to_polynomial()

Result< MultiPoly > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::power_to_polynomial	(	const std::shared_ptr< const PowerNode > &	power,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 191 行定义.

                                                                        {
    auto exponent = polynomial_exponent(power->exponent());
    if (!exponent) { return Result<MultiPoly>::failure(exponent.error()); }
    auto base = node_to_multivariate_polynomial(
        power->base(), variables, context);
    if (!base) { return base; }
 
    MultiPoly result(Rational(1), variables);
    MultiPoly factor = std::move(base.value());
    std::size_t remaining = exponent.value();
    while (remaining != 0) {
        if ((remaining & 1U) != 0) {
            auto multiplied = multiply_checked(result, factor, context);
            if (!multiplied) { return multiplied; }
            result = std::move(multiplied.value());
        }
        remaining >>= 1U;
        if (remaining != 0) {
            auto squared = multiply_checked(factor, factor, context);
            if (!squared) { return squared; }
            factor = std::move(squared.value());
        }
    }
    return Result<MultiPoly>::success(std::move(result));
}

引用了 LMCAS::context, LMCAS::exponent, LMCAS::Result< T >::failure(), multiply_checked(), node_to_multivariate_polynomial(), polynomial_exponent(), power_to_polynomial() , 以及 LMCAS::Result< T >::success().

被这些函数引用 node_to_multivariate_polynomial() , 以及 power_to_polynomial().

函数调用图:

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

sum_to_polynomial()

Result< MultiPoly > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::sum_to_polynomial	(	const std::shared_ptr< const AddNode > &	addition,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 symbolic_gcd.cpp 第 167 行定义.

                                                                        {
    MultiPoly result(Rational(0), variables);
    for (const auto& operand : addition->operands()) {
        auto converted = node_to_multivariate_polynomial(
            operand, variables, context);
        if (!converted) { return converted; }
        auto step = context.consume_steps(
            static_cast<std::size_t>(result.num_terms() +
                                     converted.value().num_terms()) + 1,
            kOperation);
        if (!step) { return Result<MultiPoly>::failure(step.error()); }
        result = result + converted.value();
        if (static_cast<std::size_t>(result.num_terms()) >
            context.limits().max_expansion_terms) {
            return Result<MultiPoly>::failure(
                CasErrc::ResourceLimit,
                "polynomial expansion term budget exhausted", kOperation);
        }
    }
    return Result<MultiPoly>::success(std::move(result));
}

引用了 LMCAS::context, LMCAS::Result< T >::failure(), kOperation, node_to_multivariate_polynomial(), LMCAS::ResourceLimit, LMCAS::Result< T >::success() , 以及 sum_to_polynomial().

被这些函数引用 node_to_multivariate_polynomial() , 以及 sum_to_polynomial().

函数调用图:

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

verify_gcd_candidate()

Result< void > LMCAS::anonymous_namespace{symbolic_gcd.cpp}::verify_gcd_candidate	(	const MultiPoly &	lhs,
		const MultiPoly &	rhs,
		const MultiPoly &	gcd )

在文件 symbolic_gcd.cpp 第 318 行定义.

                                                        {
    if (gcd.is_zero()) { return Result<void>::success(); }
    MultiPoly lhs_quotient;
    MultiPoly rhs_quotient;
    try {
        lhs_quotient = lhs.exact_div(gcd);
        rhs_quotient = rhs.exact_div(gcd);
    } catch (const std::bad_alloc&) {
        return Result<void>::failure(
            CasErrc::ResourceLimit,
            "symbolic GCD verification allocation failed", kOperation);
    } catch (const std::runtime_error&) {
        return Result<void>::failure(
            CasErrc::Inconclusive,
            "GCD candidate failed exact divisibility verification",
            kOperation);
    } catch (const std::exception& error) {
        return Result<void>::failure(
            CasErrc::InternalInvariant, error.what(), kOperation);
    }
    MultiPoly residual = make_monic(multivariate_gcd(
        lhs_quotient, rhs_quotient));
    if (!residual.is_constant()) {
        return Result<void>::failure(
            CasErrc::Inconclusive,
            "GCD candidate is not maximal", kOperation);
    }
    return Result<void>::success();
}

引用了 LMCAS::Result< T >::failure(), LMCAS::Inconclusive, LMCAS::InternalInvariant, kOperation, make_monic(), LMCAS::multivariate_gcd(), LMCAS::ResourceLimit, LMCAS::rhs, LMCAS::Result< T >::success() , 以及 verify_gcd_candidate().

被这些函数引用 verify_gcd_candidate().

函数调用图:

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

变量说明

kOperation

const char* LMCAS::anonymous_namespace{symbolic_gcd.cpp}::kOperation = "symbolic_polynomial_gcd"

constexpr

在文件 symbolic_gcd.cpp 第 24 行定义.

被这些函数引用 check_term_budget(), collect_polynomial_variables(), multiply_checked(), node_to_multivariate_polynomial(), polynomial_exponent(), polynomial_term_to_expression(), sum_to_polynomial() , 以及 verify_gcd_candidate().