Trait EvalOps

Source

pub trait EvalOps<Coeff, Value: ?Sized> {
    type Output;

    // Required methods
    fn init_acc_zero() -> Self::Output;
    fn init_acc_coeff(coeff: Coeff) -> Self::Output;
    fn update_acc_coeff(acc: &mut Self::Output, coeff: Coeff, value: &Value);
    fn update_acc_inner(
        acc: &mut Self::Output,
        inner: Self::Output,
        value: &Value,
    );

    // Provided method
    fn eval<Coeffs, Values>(
        coeffs: &mut Coeffs,
        values: &Values,
        degree: Power,
    ) -> Result<Self::Output, Error>
       where Coeffs: Iterator<Item = Coeff>,
             Values: SequenceRef<OwnedItem = Value> + ?Sized { ... }
}

Expand description

Operations for evaluating polynomials.

The polynomials considered in this crate are of the form

$$ s_{0,[\ ]} = \left( \sum_{k_{n-1}} x_{n-1}^{k_{n-1}} \left( \cdots \sum_{k_1} x_1^{k_1} \left( \sum_{k_0} x_0^{k_0} c_k \right) \right) \right). $$

For brevity the bounds of the summations are omited. The scopes, delimited by parentheses, indicate the order in which the polynomial is being evaluated numerically. The innermost scope eliminates the first variable, the next scope the second, etc.

Let $s_{n,k} = c_k$ and let $s_{i,k}$ be the value of the $i$-th scope,

$$ s_{i,k} = \sum_{j=0}^{m_{i,k}} x_i^j s_{i+1,k+[j]}, $$

where $m_{i,k}$ is the appropriate bound and $k+[j]$ denotes the concatenation of vector $k ∈ ℤ^i$ with vector $[j]$. The summation is rewritten such that the powers of $x_i$ are eliminated:

$$ s_{i,k} = ((((s_{i+1,k+[m_{i,k}]}) \cdots) x_i + s_{i+1,k+[2]}) x_i + s_{i+1,k+[1]}) x_i + s_{i,k+[0]} $$

or equivalently,

$$ s_{i,k} = a_{i,k,0} $$

with $a_{i,k,j}$ defined recursively as

$$ a_{i,k,j} = \begin{cases} s_{i+1,k+[j]} & \text{if } j = m_{i,k} \\ a_{i,k,j+1} x_i + s_{i+1,k+[j]} & \text{if } j < m_{i,k} \\ \end{cases} $$

Method EvalOps::eval() uses this recursion to evaluate the polynomial. The four required methods in this trait perform operations on accumulator $a_{i,k}$ (the aggregation of $a_{i,k,0},a_{i,k,1},\ldots$).