// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// Binomial numbers are recursively defined as B(n,k) := B(n-1,k-1)+B(n-1,k). //
// The following PRAM algorithm computes all B(n,k) for k=0,...,n in time O(n)//
// and work O(n^2). Using the equation B(n,k) = F(n)/(F(k)*F(n-k)) we can     //
// compute the same numbers in time O(log(n)) with O(n) work.                 //
// ************************************************************************** //

macro N = 10;

module Binomial2([N]nat b, event !rdy) {
    // initialize the array
    b[0] = 1;
    b[1] = 1;
    for(n=2..N-1) {
        for(k=1..n-1)
            next(b[k]) = b[k]+b[k-1];
        next(b[n]) = 1;
        pause;
    }

    // termination signal
    emit(rdy);
}
drivenby {
    await(rdy);
}