// ************************************************************************** // // // // 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); }