cp-algo/math/poly/impl/base.hpp

• View this file on GitHub
• Last update: 2024-06-30 16:32:16+02:00
• Include: #include "cp-algo/math/poly/impl/base.hpp"

Required by

• cp-algo/linalg/frobenius.hpp
• cp-algo/math/poly.hpp

Verified with

• Characteristic Polynomial (verify/linalg/characteristic.test.cpp)
• Pow of Matrix (Frobenius) (verify/linalg/pow_fast.test.cpp)
• Division of Polynomials (verify/poly/div.test.cpp)
• Exp of Power Series (verify/poly/exp.test.cpp)
• Find Linear Recurrence (verify/poly/find_linrec.test.cpp)
• Polynomial Interpolation (verify/poly/inter.test.cpp)
• Inv of Power Series (verify/poly/inv.test.cpp)
• Inv of Polynomials (verify/poly/inv_mod.test.cpp)
• Consecutive Terms of Linear Recursion (verify/poly/linrec_consecutive.test.cpp)
• Kth term of Linearly Recurrent Sequence (verify/poly/linrec_single.test.cpp)
• Log of Power Series (verify/poly/log.test.cpp)
• Pow of Power Series (verify/poly/pow.test.cpp)
• Product of Polynomial Sequence (verify/poly/prod_sequence.test.cpp)
• Polynomial Root Finding (verify/poly/roots.test.cpp)
• Sqrt of Power Series (verify/poly/sqrt.test.cpp)
• Polynomial Taylor Shift (verify/poly/taylor.test.cpp)

Code

#ifndef CP_ALGO_MATH_POLY_IMPL_BASE_HPP
#define CP_ALGO_MATH_POLY_IMPL_BASE_HPP
#include <functional>
#include <algorithm>
#include <iostream>
// really basic operations, typically taking O(n)
namespace cp_algo::math::poly::impl {
    template<typename polyn>
    void normalize(polyn& p) {
        while(p.deg() >= 0 && p.lead() == typename polyn::base(0)) {
            p.a.pop_back();
        }
    }
    auto neg_inplace(auto &&p) {
        std::ranges::transform(p.a, begin(p.a), std::negate{});
        return p;
    }
    auto& scale(auto &p, auto x) {
        for(auto &it: p.a) {
            it *= x;
        }
        p.normalize();
        return p;
    }
    auto& add(auto &p, auto const& q) {
        p.a.resize(std::max(p.a.size(), q.a.size()));
        std::ranges::transform(p.a, q.a, begin(p.a), std::plus{});
        normalize(p);
        return p;
    }
    auto& sub(auto &p, auto const& q) {
        p.a.resize(std::max(p.a.size(), q.a.size()));
        std::ranges::transform(p.a, q.a, begin(p.a), std::minus{});
        normalize(p);
        return p;
    }
    auto substr(auto const& p, size_t l, size_t k) {
        return std::vector(
            begin(p.a) + std::min(l, p.a.size()),
            begin(p.a) + std::min(l + k, p.a.size())
        );
    }
    auto& reverse(auto &p, size_t n) {
        p.a.resize(n);
        std::ranges::reverse(p.a);
        normalize(p);
        return p;
    }
}
#endif // CP_ALGO_MATH_POLY_IMPL_BASE_HPP

#line 1 "cp-algo/math/poly/impl/base.hpp"


#include <functional>
#include <algorithm>
#include <iostream>
// really basic operations, typically taking O(n)
namespace cp_algo::math::poly::impl {
    template<typename polyn>
    void normalize(polyn& p) {
        while(p.deg() >= 0 && p.lead() == typename polyn::base(0)) {
            p.a.pop_back();
        }
    }
    auto neg_inplace(auto &&p) {
        std::ranges::transform(p.a, begin(p.a), std::negate{});
        return p;
    }
    auto& scale(auto &p, auto x) {
        for(auto &it: p.a) {
            it *= x;
        }
        p.normalize();
        return p;
    }
    auto& add(auto &p, auto const& q) {
        p.a.resize(std::max(p.a.size(), q.a.size()));
        std::ranges::transform(p.a, q.a, begin(p.a), std::plus{});
        normalize(p);
        return p;
    }
    auto& sub(auto &p, auto const& q) {
        p.a.resize(std::max(p.a.size(), q.a.size()));
        std::ranges::transform(p.a, q.a, begin(p.a), std::minus{});
        normalize(p);
        return p;
    }
    auto substr(auto const& p, size_t l, size_t k) {
        return std::vector(
            begin(p.a) + std::min(l, p.a.size()),
            begin(p.a) + std::min(l + k, p.a.size())
        );
    }
    auto& reverse(auto &p, size_t n) {
        p.a.resize(n);
        std::ranges::reverse(p.a);
        normalize(p);
        return p;
    }
}

Back to top page