// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// This module implements an algorithm for evaluation of polynomials of degree//
// N in time O(log(N)). To this end, Horner's rule is considered where a poly-//
// with coefficients p[0..N-1] is evaluated by the following recursive rules: //    
//  y[0] = 0                                                                  //
//  y[i+1] = y[i] * x + p[N-i-1] for i=0..N-1                                 //
// Thus, the evaluation is performed by a first order linear recurrence       //
// y[0] := a[0]*y0+b[0], and y[i+1] := a[i+1]*y[i]+b[i+1] with the following  //
// values: y0 := 0, a[i] := x, and b[i] = p[N-1-i]. Thus, we can evaluate the //
// polynomial efficiently in time O(log(N)) using O(N) processors.            //
// ************************************************************************** //

package Algorithms.Polynomials;
import Algorithms.Sequences.FirstOrderLinearRec;
macro N = 8;

module EvalPolynomial(nat ?x,[N]nat ?p,nat !y,event !rdy) {
    int y0;
    [N]int a,b,v;
    y0 = 0;
    for(i=0..N-1) {
        a[i] = x;
        b[i] = p[N-i-1];
    }
    FirstOrderLinearRec(y0,a,b,v,rdy);
    y = abs(v[N-1]);
}
drivenby {
    x = 2;
    for(i=0..N-1)
        p[i]=N-i;
    await(rdy);
    assert(y==sum(i=0..N-1) (p[i]*exp(x,i)));
}