`GF2::Vector` — Evaluate a Polynomial Over GF(2)

Evaluates a polynomial over GF(2).

template<std::unsigned_integral Block, typename Allocator>
constexpr bool
polynomial_sum(const Vector<Block, Allocator> &p, bool x);

The polynomial’s coefficients are stored in the bit-vector p.
Returns the value of the polynomial at the point x.

\[p(x) = p_0 + p_1 x + p_2 x^2 + \cdots + p_{n-1} x^{n-1}.\]

In GF(2) all arithmetic is done mod 2 which means that

\[p(x) = p_0 + p_1 x + p_2 x + \cdots + p_{n-1} x.\]

If \(x = 0\) this is just p[0], while if \(x = 1\) it is the count of ones (mod 2) in the bit-vector p.

Calling this method for an empty polynomial is likely a mistake and will be flagged as such if the GF2_DEBUG flag is set a compile time. If that flag isn’t set the method will always return false.

Example

#include <GF2/GF2.h>
int main()
{
    GF2::Vector  p1(16, [](size_t k) { return (k + 1) % 2; });
    GF2::Vector  p2(17, [](size_t k) { return (k + 1) % 2; });
    std::cout << "Polynomial of degree " << p1.size() -1 << " with coefficients: " << p1 << '\n'
              << "    evaluated at 0 = "  << polynomial_sum(p1, false) << '\n'
              << "    evaluated at 1 = "  << polynomial_sum(p1, true)  << '\n';
    std::cout << "Polynomial of degree " << p2.size() -1 << " with coefficients: " << p2 << '\n'
              << "    evaluated at 0 = "  << polynomial_sum(p2, false) << '\n'
              << "    evaluated at 1 = "  << polynomial_sum(p2, true)  << '\n';
}

Output

Polynomial of degree 15 with coefficients: 1010101010101010
    evaluated at 0 = 1
    evaluated at 1 = 0
Polynomial of degree 16 with coefficients: 10101010101010101
    evaluated at 0 = 1
    evaluated at 1 = 1

GF2::Vector — Evaluate a Polynomial Over GF(2)

`GF2::Vector` — Evaluate a Polynomial Over GF(2)