LMCAS
Lamina Computer Algebra System
载入中...
搜索中...
未找到
limit_visitor.hpp
浏览该文件的文档.
1/**
2 * @file limit_visitor.hpp
3 * @brief 极限访问器，通过代入和 L'Hôpital 法则计算极限。
4 */
5#pragma once
6
7#include "lmcas_export.hpp"
8#include "computation_context.hpp"
9#include "internal/symbolic_ast.hpp"
10#include "assumption_context.hpp"
11#include "internal/visitors/normalization_visitor.hpp"
12#include "internal/visitors/differentiation_visitor.hpp"
13#include <iostream>
14#include <cmath>
15#include <optional>
16#include <limits>
17#include <utility>
18
19namespace LMCAS {
20
21class SymbolicExpr;
22template <typename CoeffType>
23class Polynomial;
24namespace detail {
25class ExactBoundArithmetic;
26}
27class LMCAS_API LimitVisitor : public LMCAS::detail::SymbolicVisitor {
28 std::string var;
29 std::shared_ptr<const SymbolicNode> point;
30 std::string direction;
31 const LMCAS::AssumptionContext* assumption_ctx_ = nullptr;
32 std::optional<ComputationContext> local_context_;
33 ComputationContext* context_ = nullptr;
34 detail::RewriteBudget budget_;
35 void charge() const {
36 if (!context_) return;
37 auto step = context_->consume_steps(1, "limit");
38 if (!step) throw step.error();
39 }
40 int lhopital_depth_ = 0;
41 static constexpr int max_lhopital_depth = 5;
42 static int& active_limit_depth();
43 static constexpr int max_active_limit_depth = 128;
44
45 static std::shared_ptr<const SymbolicNode> make_product_or_one(
46 const std::vector<std::shared_ptr<const SymbolicNode>>& factors);
47
48 struct EvaluationScope {
49 bool entered = false;
50 EvaluationScope();
51 ~EvaluationScope();
52 explicit operator bool() const noexcept { return entered; }
53 };
54
55 enum class IndeterminateForm { None, ZeroTimesInf, InfMinusInf, OnePowInf, ZeroPowZero, InfPowZero };
56
57 bool is_inf(const std::shared_ptr<const SymbolicNode>& node) const;
58 bool is_neg_inf(const std::shared_ptr<const SymbolicNode>& node) const;
59 std::optional<int> get_node_sign(const std::shared_ptr<const SymbolicNode>& node) const;
60 double get_numeric_value(const std::shared_ptr<const NumberNode>& num) const;
61 bool is_bounded(const std::shared_ptr<const SymbolicNode>& node) const;
62 bool is_bounded_expression(const std::shared_ptr<const SymbolicNode>& node) const;
63 bool tends_to_zero(const std::shared_ptr<const SymbolicNode>& node) const;
64 std::shared_ptr<const SymbolicNode> eval_limit(const std::shared_ptr<const SymbolicNode>& expr);
65
66 IndeterminateForm classify_product_form(const std::vector<std::shared_ptr<const SymbolicNode>>& vals);
67 IndeterminateForm classify_power_form(const std::shared_ptr<const SymbolicNode>& bv, const std::shared_ptr<const SymbolicNode>& ev);
68 IndeterminateForm classify_add_form(const std::vector<std::shared_ptr<const SymbolicNode>>& vals);
69
70 std::shared_ptr<const SymbolicNode> try_squeeze(const std::shared_ptr<const SymbolicNode>& expr);
71 std::pair<std::shared_ptr<const SymbolicNode>, std::shared_ptr<const SymbolicNode>> extract_num_den(const std::shared_ptr<const SymbolicNode>& expr);
72 std::shared_ptr<const SymbolicNode> resolve_zero_times_inf(const std::vector<std::shared_ptr<const SymbolicNode>>& factors, const std::vector<std::shared_ptr<const SymbolicNode>>& factor_vals);
73 std::shared_ptr<const SymbolicNode> resolve_inf_minus_inf(const AddNode& node, const std::vector<std::shared_ptr<const SymbolicNode>>& operand_vals);
74 std::shared_ptr<const SymbolicNode> resolve_exponential_form(const std::shared_ptr<const SymbolicNode>& base, const std::shared_ptr<const SymbolicNode>& exponent);
75 std::shared_ptr<const SymbolicNode> apply_lhopital(const std::shared_ptr<const SymbolicNode>& num, const std::shared_ptr<const SymbolicNode>& den);
76
77 std::shared_ptr<const SymbolicNode> taylor_fallback(const std::shared_ptr<const SymbolicNode>& num, const std::shared_ptr<const SymbolicNode>& den, int max_order = 8);
78 std::shared_ptr<const SymbolicNode> simplify_and_eval_ratio(const std::shared_ptr<const SymbolicNode>& ratio_node);
79 std::pair<std::shared_ptr<const SymbolicNode>, int> find_leading_term(const std::shared_ptr<SymbolicExpr>& series_expr, const std::string& expand_var, const std::shared_ptr<SymbolicExpr>& expand_point, int max_order);
80 static int get_sign(const std::shared_ptr<const SymbolicNode>& node);
81
82 bool is_limit_at_infinity() const;
83 bool is_limit_at_neg_infinity() const;
84 int get_polynomial_degree(const std::shared_ptr<const SymbolicNode>& node) const;
85 std::shared_ptr<const SymbolicNode> get_leading_coefficient(const std::shared_ptr<const SymbolicNode>& node) const;
86 std::shared_ptr<const SymbolicNode> limit_rational_at_infinity(const std::shared_ptr<const SymbolicNode>& num, const std::shared_ptr<const SymbolicNode>& den);
87 enum class GrowthClass { Constant, Logarithmic, Polynomial, Exponential, Unknown };
88 GrowthClass classify_growth(const std::shared_ptr<const SymbolicNode>& node) const;
89 std::shared_ptr<const SymbolicNode> limit_by_growth_comparison(const std::shared_ptr<const SymbolicNode>& num, const std::shared_ptr<const SymbolicNode>& den);
90 std::shared_ptr<const SymbolicNode> handle_neg_infinity_limit(const std::shared_ptr<const SymbolicNode>& expr);
91 std::shared_ptr<const SymbolicNode> positive_tail_log_power(const FunctionNode& node) const;
92 bool defined_near_point(const std::shared_ptr<const SymbolicNode>& node) const;
93 std::shared_ptr<const SymbolicNode> substitute_neg_t(const std::shared_ptr<const SymbolicNode>& node, const std::string& t_var) const;
94
95 std::optional<int> determine_sign_near_point(const std::shared_ptr<const SymbolicNode>& expr, const std::string& dir);
96 bool analytic_at_point(const std::shared_ptr<const SymbolicNode>& expr) const;
97 std::optional<Rational> algebraic_growth_degree(const std::shared_ptr<const SymbolicNode>& expr) const;
98 bool proves_superlogarithmic_magnitude(const std::shared_ptr<const SymbolicNode>& expr) const;
99 bool polynomial_logarithmic_bound(const std::shared_ptr<const SymbolicNode>& expr) const;
100 std::optional<std::pair<Rational, int>> exact_leading_at_point(
101 const std::shared_ptr<const SymbolicNode>& expr) const;
102 std::shared_ptr<const SymbolicNode> select_branch_by_direction(const PiecewiseNode& node, const std::string& dir);
103 std::optional<std::shared_ptr<const SymbolicNode>> evaluate_sgn_limit(const std::shared_ptr<const SymbolicNode>& arg);
104 std::optional<std::shared_ptr<const SymbolicNode>> evaluate_abs_limit(const std::shared_ptr<const SymbolicNode>& arg);
105
106 bool is_infinite_power(const PowerNode& node) const;
107 bool is_bounded_product(const MultiplyNode& node) const;
108 bool is_zero_limit(const std::shared_ptr<const SymbolicNode>& node) const;
109 std::shared_ptr<const SymbolicNode> squeeze_product(const MultiplyNode& node);
110 std::shared_ptr<const SymbolicNode> squeeze_sum(const AddNode& node);
111 std::shared_ptr<const SymbolicNode> denominator_factor(const std::shared_ptr<const SymbolicNode>& node) const;
112 std::shared_ptr<const SymbolicNode> resolve_zero_infinity_pair(
113 const std::shared_ptr<const SymbolicNode>& zero,
114 const std::shared_ptr<const SymbolicNode>& infinity);
115 std::shared_ptr<const SymbolicNode> multiply_remaining_limits(
116 const std::shared_ptr<const SymbolicNode>& value,
117 const std::vector<std::shared_ptr<const SymbolicNode>>& factors);
118 std::shared_ptr<const SymbolicNode> resolve_combined_ratio(
119 const std::shared_ptr<const SymbolicNode>& num,
120 const std::shared_ptr<const SymbolicNode>& den);
121 std::shared_ptr<const SymbolicNode> derivative_limit(
122 const std::shared_ptr<const SymbolicNode>& node, bool normalize);
123 std::shared_ptr<const SymbolicNode> derivative_ratio_limit(
124 const std::shared_ptr<const SymbolicNode>& num,
125 const std::shared_ptr<const SymbolicNode>& den,
126 const std::shared_ptr<const SymbolicNode>& num_value,
127 const std::shared_ptr<const SymbolicNode>& den_value);
128 std::shared_ptr<const SymbolicNode> signed_infinity(int sign) const;
129 bool is_limit_variable(const std::shared_ptr<const SymbolicNode>& node) const;
130 bool is_positive_variable_power(const std::shared_ptr<const SymbolicNode>& node) const;
131 bool is_variable_reciprocal(const std::shared_ptr<const SymbolicNode>& node) const;
132 bool is_log_variable(const std::shared_ptr<const SymbolicNode>& node) const;
133 bool logarithmic_zero_product(const MultiplyNode& node) const;
134 std::shared_ptr<const SymbolicNode> one_plus_term(const AddNode& node) const;
135 std::shared_ptr<const SymbolicNode> variable_fraction_numerator(
136 const std::shared_ptr<const SymbolicNode>& node) const;
137 bool logarithmic_product_limit(const MultiplyNode& node);
138 std::optional<std::shared_ptr<const SymbolicNode>> logarithmic_remaining_limit(
139 const MultiplyNode& node, const SymbolicNode* logarithm,
140 const std::shared_ptr<const SymbolicNode>& numerator);
141 bool has_slower_factors(const MultiplyNode& node, const SymbolicNode* exponential) const;
142 bool decaying_exponential_product(const MultiplyNode& node);
143 bool trigonometric_product_limit(const MultiplyNode& node);
144 std::shared_ptr<const SymbolicNode> matching_reciprocal(
145 const MultiplyNode& node, const std::shared_ptr<const SymbolicNode>& argument) const;
146 std::shared_ptr<const SymbolicNode> trigonometric_remaining_limit(
147 const MultiplyNode& node, const SymbolicNode* function, const SymbolicNode* reciprocal);
148 std::shared_ptr<const SymbolicNode> product_ratio_limit(
149 const std::shared_ptr<const SymbolicNode>& num,
150 const std::shared_ptr<const SymbolicNode>& den);
151 std::shared_ptr<const SymbolicNode> linear_exponent_coefficient(
152 const std::shared_ptr<const SymbolicNode>& node) const;
153 bool exponential_power_limit(const PowerNode& node);
154 std::shared_ptr<const SymbolicNode> singular_power_limit(
155 const PowerNode& node, const std::shared_ptr<const SymbolicNode>& base,
156 const std::shared_ptr<const SymbolicNode>& exponent);
157 bool composed_function_limit(const FunctionNode& node);
158 bool infinite_function_limit(FunctionNode::FuncType type, bool negative);
159 GrowthClass function_growth(const FunctionNode& node) const;
160 GrowthClass power_growth(const PowerNode& node) const;
161 GrowthClass operands_growth(const std::vector<std::shared_ptr<const SymbolicNode>>& operands) const;
162 std::shared_ptr<const SymbolicNode> substitute_function_neg_t(const FunctionNode& node, const std::string& t_var) const;
163 std::shared_ptr<const SymbolicNode> leading_terms_limit(
164 const std::pair<std::shared_ptr<const SymbolicNode>, int>& numerator,
165 const std::pair<std::shared_ptr<const SymbolicNode>, int>& denominator);
166 std::shared_ptr<const SymbolicNode> taylor_series_limit(
167 const std::shared_ptr<SymbolicExpr>& numerator,
168 const std::shared_ptr<SymbolicExpr>& denominator,
169 const std::string& expand_var, const std::shared_ptr<SymbolicExpr>& expand_point, int order);
170
171 std::shared_ptr<const SymbolicNode> divergent_leading_ratio(
172 const std::shared_ptr<SymbolicExpr>& ratio, int difference);
173 bool is_infinite_product(const MultiplyNode& product) const;
174 bool is_infinite_sum(const AddNode& sum) const;
175 std::optional<int> assumed_node_sign(
176 const std::shared_ptr<const SymbolicNode>& node) const;
177 std::shared_ptr<const SymbolicNode> infinite_base_power_limit(
178 const std::shared_ptr<const SymbolicNode>& base,
179 const std::shared_ptr<const NumberNode>& number, bool integral, const BigInt& integer);
180 bool rational_denominator_supported(
181 const std::shared_ptr<const SymbolicNode>& leading_denominator,
182 const std::shared_ptr<const SymbolicNode>& num,
183 const std::shared_ptr<const SymbolicNode>& den) const;
184 std::shared_ptr<const SymbolicNode> rational_leading_limit(
185 const std::shared_ptr<const SymbolicNode>& leading_numerator,
186 const std::shared_ptr<const SymbolicNode>& leading_denominator, int degree_difference);
187 std::optional<Rational> algebraic_sum_growth(const AddNode& sum) const;
188 std::optional<Rational> algebraic_product_growth(const MultiplyNode& product) const;
189 std::optional<Rational> algebraic_power_growth(const PowerNode& power) const;
190 bool logarithmic_algebraic_bound(
191 const std::shared_ptr<const SymbolicNode>& expr) const;
192 bool polynomial_logarithmic_operands(
193 const std::vector<std::shared_ptr<const SymbolicNode>>& operands) const;
194 bool exponential_dominates(
195 const std::shared_ptr<const SymbolicNode>& exponential,
196 const std::shared_ptr<const SymbolicNode>& other);
197 bool can_rationalize_sum(const AddNode& node,
198 const std::vector<std::shared_ptr<const SymbolicNode>>& values) const;
199 std::optional<Polynomial<Rational>> square_algebraic_term(
200 const std::shared_ptr<const SymbolicNode>& term) const;
201 std::shared_ptr<const SymbolicNode> rationalized_sum_limit(
202 const AddNode& node, const std::vector<std::shared_ptr<const SymbolicNode>>& values);
203 std::pair<std::shared_ptr<const SymbolicNode>, std::shared_ptr<const SymbolicNode>>
204 combine_sum_ratio(
205 const std::vector<std::shared_ptr<const SymbolicNode>>& numerators,
206 const std::vector<std::shared_ptr<const SymbolicNode>>& denominators);
207 std::optional<std::pair<Rational, int>> exact_polynomial_leading(
208 const Polynomial<Rational>& polynomial, const Rational& point_value,
209 detail::ExactBoundArithmetic& arithmetic) const;
210 bool analytic_defined_at_point(
211 const std::shared_ptr<const SymbolicNode>& expr,
212 const std::shared_ptr<const SymbolicNode>& positive_base) const;
213 bool analytic_power_at_point(const PowerNode& power,
214 const std::shared_ptr<const SymbolicNode>& expr) const;
215 bool analytic_function_at_point(const FunctionNode& function,
216 const std::shared_ptr<const SymbolicNode>& expr) const;
217 bool analytic_operands_at_point(
218 const std::vector<std::shared_ptr<const SymbolicNode>>& operands) const;
219 std::optional<int> rational_sign_at_infinity(
220 const std::shared_ptr<const SymbolicNode>& expr);
221 std::optional<int> product_sign_near_point(
222 const MultiplyNode& product, const std::string& dir);
223 std::optional<int> power_sign_near_point(
224 const PowerNode& power, const std::string& dir);
225 std::optional<int> analytic_sign_near_point(
226 const std::shared_ptr<const SymbolicNode>& expr, const std::string& dir);
227 std::optional<bool> relation_truth_near_point(const RelationalNode& relation);
228 std::optional<bool> logical_truth_near_point(const LogicalNode& logical);
229 std::optional<bool> condition_truth_near_point(
230 const std::shared_ptr<const SymbolicNode>& node);
231 std::shared_ptr<const SymbolicNode> singular_ratio_limit(
232 const std::shared_ptr<const SymbolicNode>& num,
233 const std::shared_ptr<const SymbolicNode>& den);
234 std::optional<std::shared_ptr<const SymbolicNode>> exact_ratio_at_point(
235 const std::shared_ptr<const SymbolicNode>& num,
236 const std::shared_ptr<const SymbolicNode>& den);
237 std::shared_ptr<const SymbolicNode> evaluated_product_ratio(
238 const std::shared_ptr<const SymbolicNode>& num,
239 const std::shared_ptr<const SymbolicNode>& den, bool at_infinity);
240 bool positive_tail_product_limit(const MultiplyNode& node);
241 std::shared_ptr<const SymbolicNode> resolve_product_factors(
242 const MultiplyNode& node, const std::vector<std::shared_ptr<const SymbolicNode>>& values);
243
244public:
245 bool condition_holds_near_point(const std::shared_ptr<const SymbolicNode>& condition);
246 std::optional<int> sign_near_point(const std::shared_ptr<const SymbolicNode>& node) {
247 return determine_sign_near_point(node, direction);
248 }
249 std::shared_ptr<const SymbolicNode> select_piecewise_near_point(const PiecewiseNode& node) {
250 return select_branch_by_direction(node, direction);
251 }
252 std::shared_ptr<const SymbolicNode> result;
253
254 LimitVisitor(std::string v, std::shared_ptr<const SymbolicNode> p, std::string dir = "",
255 const LMCAS::AssumptionContext* ctx = nullptr, ComputationContext* context = nullptr)
256 : SymbolicVisitor(&budget_), var(std::move(v)), point(std::move(p)),
257 direction(std::move(dir)), assumption_ctx_(ctx),
258 local_context_(context ? std::nullopt
259 : std::optional<ComputationContext>(std::in_place)),
260 context_(context ? context : &*local_context_),
261 budget_(*context_, context_->limits().max_recursion_depth,
262 context_->limits().max_ast_nodes, "limit") {
263 if (context_) {
264 auto entered = context_->enter_recursion("limit");
265 if (!entered) throw entered.error();
266 }
267 }
268 ~LimitVisitor() override { if (context_) context_->leave_recursion(); }
269 LimitVisitor(const LimitVisitor&) = delete;
270 LimitVisitor& operator=(const LimitVisitor&) = delete;
271
272 std::shared_ptr<const SymbolicNode> get_result() const;
273
274 void visit(const NumberNode& node) override;
275 void visit(const VariableNode& node) override;
276 void visit(const AddNode& node) override;
277 void visit(const MultiplyNode& node) override;
278 void visit(const PowerNode& node) override;
279 void visit(const FunctionNode& node) override;
280 void visit(const UninterpretedFunctionNode& node) override;
281 void visit(const MatrixNode& node) override;
282 void visit(const RelationalNode& node) override;
283 void visit(const LogicalNode& node) override;
284 void visit(const PiecewiseNode& node) override;
285 void visit(const SummationNode& node) override;
286 void visit(const ProductNode& node) override;
287 void visit(const TransformNode& node) override;
288 void visit(const QuantifierNode& node) override;
289 void visit(const SetBuilderNode& node) override;
290 void visit(const FiniteSetNode& node) override;
291 void visit(const IntervalNode& node) override;
292 void visit(const MembershipNode& node) override;
293 void visit(const QuantityNode& node) override;
294 void visit(const ComplexNode& node) override;
295 void visit(const IntegralNode& node) override;
296 void visit(const LimitNode& node) override;
297 void visit(const RootOfNode& node) override;
298};
299
300}
assumption_context.hpp
AssumptionContext class with scoped push/pop management.
LMCAS::Polynomial
一元多项式模板类
定义 polynomial.hpp:52
LMCAS::detail::ExactBoundArithmetic
常数及根式包围区间共用的内部算术策略。 保守界覆盖未约分 Rational 的交叉乘积及结果；受检入口统一捕获 CasError，仅返回完整结果。
定义 exact_constant_bounds.hpp:23
computation_context.hpp
differentiation_visitor.hpp
微分访问器，对 AST 执行符号求导。
lmcas_export.hpp
LMCAS_API
#define LMCAS_API
定义 lmcas_export.hpp:13
LMCAS::anonymous_namespace{integration_substitution.cpp}::LinearWrapperKind::None
@ None
定义 integration_substitution.cpp:101
LMCAS::detail
多元 Hensel 提升（单变量步）
定义 assumption_context.hpp:31
LMCAS::point
const std::string const LimitExprPtr & point
定义 limit_result.hpp:29
LMCAS::v
__attribute__((visibility("default"))) VectorCalculusExprResult surface_integral_scalar_checked(const std __attribute__((visibility("default"))) VectorCalculusExprResult surface_integral_scalar_checked(const std __attribute__((visibility("default"))) std const VectorField const std::string const std::string & v
定义 vector_calculus_surfaces.hpp:59
LMCAS::context
const std::vector< Polynomial< BigInt > > const BigInt ComputationContext & context
定义 exact_factorization.hpp:65
LMCAS::direction
const std::string const LimitExprPtr LimitDirection direction
定义 limit_result.hpp:30
LMCAS::Parity::Unknown
@ Unknown
Parity not determined
定义 assumption.hpp:39
normalization_visitor.hpp
符号规范化访问器接口。
symbolic_ast.hpp
内部 AST 定义。