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

类
struct	PendingInterval

类型定义
using	SturmSequence = std::vector<Polynomial<Rational>>

函数
Result< void >	clear_isolation_endpoints (const Polynomial< Rational > &square_free, const SturmSequence &sequence, PendingInterval &interval, ComputationContext &context, const std::string &operation)
Result< std::size_t >	count_open_roots (const Polynomial< Rational > &square_free, const SturmSequence &sequence, const Rational &lower, const Rational &upper, ComputationContext &context, const std::string &operation)
Result< std::vector< RationalInterval > >	isolate_sturm_sequence (const Polynomial< Rational > &square_free, const SturmSequence &sequence, ComputationContext &context, const std::string &operation)
Result< SturmSequence >	make_sturm_sequence (Polynomial< Rational > polynomial, ComputationContext &context, const std::string &operation)
int	polynomial_sign_at (const Polynomial< Rational > &polynomial, const Rational &point)
int	sign_changes (const std::vector< int > &signs)
Result< void >	subdivide_isolation (const Polynomial< Rational > &square_free, const SturmSequence &sequence, const PendingInterval &current, std::vector< PendingInterval > &pending, std::vector< RationalInterval > &isolated, ComputationContext &context, const std::string &operation)
Result< int >	variations_at (const SturmSequence &sequence, const Rational &point, ComputationContext &context, const std::string &operation)

---

类说明

LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval

struct LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval

在文件 exact_sturm.cpp 第 137 行定义.

LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval 的协作图:

类成员
size_t	count
Rational	lower
Rational	upper

类型定义说明

SturmSequence

using LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::SturmSequence = std::vector<Polynomial<Rational>>

在文件 exact_sturm.cpp 第 9 行定义.

函数说明

clear_isolation_endpoints()

Result< void > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::clear_isolation_endpoints	(	const Polynomial< Rational > &	square_free,
		const SturmSequence &	sequence,
		PendingInterval &	interval,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 143 行定义.

                                {
    while (polynomial_sign_at(square_free, interval.lower) == 0 ||
           polynomial_sign_at(square_free, interval.upper) == 0) {
        const Rational midpoint = (interval.lower + interval.upper) / Rational(2);
        if (polynomial_sign_at(square_free, midpoint) == 0) {
            interval.lower = midpoint;
            interval.upper = midpoint;
            break;
        }
        const bool lower_is_root = polynomial_sign_at(square_free, interval.lower) == 0;
        auto half = lower_is_root
            ? count_open_roots(square_free, sequence, midpoint, interval.upper,
                               context, operation)
            : count_open_roots(square_free, sequence, interval.lower, midpoint,
                               context, operation);
        if (!half) return Result<void>::failure(half.error());
        if (lower_is_root == (half.value() == 1)) {
            interval.lower = midpoint;
        } else {
            interval.upper = midpoint;
        }
    }
    return Result<void>::success();
}

引用了 clear_isolation_endpoints(), LMCAS::detail::context, count_open_roots(), LMCAS::Result< T >::failure(), LMCAS::interval(), LMCAS::detail::operation, polynomial_sign_at() , 以及 LMCAS::Result< T >::success().

被这些函数引用 clear_isolation_endpoints() , 以及 isolate_sturm_sequence().

函数调用图:

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

count_open_roots()

Result< std::size_t > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::count_open_roots	(	const Polynomial< Rational > &	square_free,
		const SturmSequence &	sequence,
		const Rational &	lower,
		const Rational &	upper,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 107 行定义.

                                {
    if (!(lower < upper) || sequence.empty()) {
        return Result<std::size_t>::success(0);
    }
    auto lower_variations = variations_at(sequence, lower, context, operation);
    if (!lower_variations) {
        return Result<std::size_t>::failure(lower_variations.error());
    }
    auto upper_variations = variations_at(sequence, upper, context, operation);
    if (!upper_variations) {
        return Result<std::size_t>::failure(upper_variations.error());
    }
    int count = lower_variations.value() - upper_variations.value();
    if (polynomial_sign_at(square_free, upper) == 0) --count;
    if (count < 0) {
        return Result<std::size_t>::failure(
            CasErrc::InternalInvariant,
            "Sturm variation produced a negative open-interval count",
            operation);
    }
    return Result<std::size_t>::success(static_cast<std::size_t>(count));
}

引用了 LMCAS::detail::context, count_open_roots(), LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, LMCAS::lower, LMCAS::detail::operation, polynomial_sign_at(), LMCAS::Result< T >::success(), LMCAS::upper , 以及 variations_at().

被这些函数引用 clear_isolation_endpoints(), count_open_roots(), isolate_sturm_sequence() , 以及 subdivide_isolation().

函数调用图:

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

isolate_sturm_sequence()

Result< std::vector< RationalInterval > > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::isolate_sturm_sequence	(	const Polynomial< Rational > &	square_free,
		const SturmSequence &	sequence,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 201 行定义.

                                                             {
    const Rational bound = strict_cauchy_root_bound(square_free);
    auto total = count_open_roots(square_free, sequence, -bound, bound, context, operation);
    if (!total) return Result<std::vector<RationalInterval>>::failure(total.error());
    std::vector<PendingInterval> pending;
    std::vector<RationalInterval> isolated;
    if (total.value() != 0) pending.push_back({-bound, bound, total.value()});
    isolated.reserve(total.value());
    while (!pending.empty()) {
        auto step = context.consume_steps(1, operation);
        if (!step) return Result<std::vector<RationalInterval>>::failure(step.error());
        PendingInterval current = std::move(pending.back());
        pending.pop_back();
        if (current.count == 1) {
            auto cleared = clear_isolation_endpoints(
                square_free, sequence, current, context, operation);
            if (!cleared) return Result<std::vector<RationalInterval>>::failure(cleared.error());
            isolated.emplace_back(current.lower, current.upper);
            continue;
        }
        auto subdivided = subdivide_isolation(
            square_free, sequence, current, pending, isolated, context, operation);
        if (!subdivided) return Result<std::vector<RationalInterval>>::failure(subdivided.error());
    }
    std::sort(isolated.begin(), isolated.end(),
        [](const RationalInterval& left, const RationalInterval& right) {
            if (left.first != right.first) return left.first < right.first;
            return left.second < right.second;
        });
    if (isolated.size() != total.value()) {
        return Result<std::vector<RationalInterval>>::failure(
            CasErrc::InternalInvariant,
            "Sturm isolation lost a distinct real root", operation);
    }
    return Result<std::vector<RationalInterval>>::success(std::move(isolated));
}

引用了 clear_isolation_endpoints(), LMCAS::detail::context, LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::count, count_open_roots(), LMCAS::InternalInvariant, isolate_sturm_sequence(), LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::lower, LMCAS::detail::operation, LMCAS::right, LMCAS::detail::strict_cauchy_root_bound(), subdivide_isolation() , 以及 LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::upper.

被这些函数引用 isolate_sturm_sequence().

函数调用图:

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

make_sturm_sequence()

Result< SturmSequence > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::make_sturm_sequence	(	Polynomial< Rational >	polynomial,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 60 行定义.

                                {
    auto step = context.consume_steps(1, operation);
    if (!step) return Result<SturmSequence>::failure(step.error());
 
    polynomial.trim();
    if (polynomial.degree() <= 0) {
        return Result<SturmSequence>::success({});
    }
    polynomial = polynomial.square_free_part().make_monic();
 
    SturmSequence sequence;
    sequence.push_back(polynomial);
    sequence.push_back(polynomial.differentiate());
    while (!sequence.back().is_zero()) {
        step = context.consume_steps(1, operation);
        if (!step) return Result<SturmSequence>::failure(step.error());
        const auto& dividend = sequence[sequence.size() - 2];
        const auto& divisor = sequence.back();
        auto division = dividend.div_mod(divisor);
        auto remainder = std::move(division.second);
        if (remainder.is_zero()) break;
        for (auto& coefficient : remainder.coeffs) coefficient = -coefficient;
        remainder.trim();
        sequence.push_back(std::move(remainder));
    }
    if (!sequence.empty() && sequence.back().is_zero()) sequence.pop_back();
    return Result<SturmSequence>::success(std::move(sequence));
}

引用了 LMCAS::detail::context, LMCAS::Polynomial< CoeffType >::degree(), LMCAS::Polynomial< CoeffType >::differentiate(), LMCAS::Result< T >::failure(), LMCAS::Polynomial< CoeffType >::make_monic(), make_sturm_sequence(), LMCAS::detail::operation, LMCAS::Polynomial< CoeffType >::square_free_part(), LMCAS::Result< T >::success() , 以及 LMCAS::Polynomial< CoeffType >::trim().

被这些函数引用 make_sturm_sequence().

函数调用图:

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

polynomial_sign_at()

int LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::polynomial_sign_at	(	const Polynomial< Rational > &	polynomial,
		const Rational &	point )

在文件 exact_sturm.cpp 第 22 行定义.

                           {
    if (polynomial.is_zero()) return 0;
    const int degree = polynomial.degree();
    const BigInt numerator = point.get_numerator();
    const BigInt denominator = point.get_denominator();
    BigInt coefficient_denominator(1);
    for (const auto& coefficient : polynomial.coeffs) {
        coefficient_denominator *= coefficient.get_denominator();
    }
    std::vector<BigInt> numerator_powers(
        static_cast<std::size_t>(degree) + 1, BigInt(1));
    std::vector<BigInt> denominator_powers(
        static_cast<std::size_t>(degree) + 1, BigInt(1));
    for (int exponent = 1; exponent <= degree; ++exponent) {
        numerator_powers[static_cast<std::size_t>(exponent)] =
            numerator_powers[static_cast<std::size_t>(exponent - 1)] *
            numerator;
        denominator_powers[static_cast<std::size_t>(exponent)] =
            denominator_powers[static_cast<std::size_t>(exponent - 1)] *
            denominator;
    }
    BigInt value(0);
    for (int exponent = 0; exponent <= degree; ++exponent) {
        const auto& coefficient =
            polynomial.coeffs[static_cast<std::size_t>(exponent)];
        if (coefficient == Rational(0)) continue;
        value += coefficient.get_numerator() *
            (coefficient_denominator / coefficient.get_denominator()) *
            numerator_powers[static_cast<std::size_t>(exponent)] *
            denominator_powers[
                static_cast<std::size_t>(degree - exponent)];
    }
    if (value == BigInt(0)) return 0;
    return value < BigInt(0) ? -1 : 1;
}

引用了 LMCAS::Polynomial< CoeffType >::coeffs, LMCAS::Polynomial< CoeffType >::degree(), LMCAS::denominator, LMCAS::exponent, LMCAS::Polynomial< CoeffType >::is_zero(), LMCAS::point, polynomial_sign_at() , 以及 LMCAS::value.

被这些函数引用 clear_isolation_endpoints(), count_open_roots(), polynomial_sign_at(), subdivide_isolation() , 以及 variations_at().

函数调用图:

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

sign_changes()

int LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::sign_changes

(

const std::vector< int > &

signs

)

在文件 exact_sturm.cpp 第 11 行定义.

                                              {
    int changes = 0;
    int previous = 0;
    for (const int current : signs) {
        if (current == 0) continue;
        if (previous != 0 && current != previous) ++changes;
        previous = current;
    }
    return changes;
}

引用了 sign_changes().

被这些函数引用 sign_changes() , 以及 variations_at().

函数调用图:

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

subdivide_isolation()

Result< void > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::subdivide_isolation	(	const Polynomial< Rational > &	square_free,
		const SturmSequence &	sequence,
		const PendingInterval &	current,
		std::vector< PendingInterval > &	pending,
		std::vector< RationalInterval > &	isolated,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 171 行定义.

                                {
    const Rational midpoint = (current.lower + current.upper) / Rational(2);
    const bool midpoint_is_root = polynomial_sign_at(square_free, midpoint) == 0;
    auto left = count_open_roots(
        square_free, sequence, current.lower, midpoint, context, operation);
    if (!left) return Result<void>::failure(left.error());
    auto right = count_open_roots(
        square_free, sequence, midpoint, current.upper, context, operation);
    if (!right) return Result<void>::failure(right.error());
    const std::size_t accounted = left.value() + right.value() +
        (midpoint_is_root ? 1U : 0U);
    if (accounted != current.count) {
        return Result<void>::failure(
            CasErrc::InternalInvariant,
            "Sturm subdivision did not preserve the root count", operation);
    }
    if (right.value() != 0) {
        pending.push_back({midpoint, current.upper, right.value()});
    }
    if (midpoint_is_root) isolated.emplace_back(midpoint, midpoint);
    if (left.value() != 0) {
        pending.push_back({current.lower, midpoint, left.value()});
    }
    return Result<void>::success();
}

引用了 LMCAS::detail::context, LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::count, count_open_roots(), LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::lower, LMCAS::detail::operation, polynomial_sign_at(), LMCAS::right, subdivide_isolation(), LMCAS::Result< T >::success() , 以及 LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::PendingInterval::upper.

被这些函数引用 isolate_sturm_sequence() , 以及 subdivide_isolation().

函数调用图:

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

variations_at()

Result< int > LMCAS::detail::anonymous_namespace{exact_sturm.cpp}::variations_at	(	const SturmSequence &	sequence,
		const Rational &	point,
		ComputationContext &	context,
		const std::string &	operation )

在文件 exact_sturm.cpp 第 92 行定义.

                                {
    auto step = context.consume_steps(sequence.size() + 1, operation);
    if (!step) return Result<int>::failure(step.error());
    std::vector<int> signs;
    signs.reserve(sequence.size());
    for (const auto& member : sequence) {
        signs.push_back(polynomial_sign_at(member, point));
    }
    return Result<int>::success(sign_changes(signs));
}

引用了 LMCAS::detail::context, LMCAS::Result< T >::failure(), LMCAS::member(), LMCAS::detail::operation, LMCAS::point, polynomial_sign_at(), sign_changes(), LMCAS::Result< T >::success() , 以及 variations_at().

被这些函数引用 count_open_roots() , 以及 variations_at().

函数调用图:

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