// ************************************************************************** // // // // 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 is the original version of Euclid's algorithm for computing greatest // // common divisors of given natural numbers: The core of the algorithm is // // the fact that the common divisors of a and b are the common divisors of b // // and (a-b): // // * Divisors(a,b) <= Divisors(b,a-b) holds, // // since x*t=a and y*t=b imply a-b = (x-y)*t, so that every common divisor // // t of a and b also divides a-b. // // * Divisors(b,a-b) <= Divisors(a,b) holds, // // since x*t=b and y*t=a-b imply a = (a-b)+b = (y+x)*t, thus every common // // divisor t of b and a-b also divides a. // // ************************************************************************** // macro N = 1000; module EuclidSub(nat{N} ?a,?b,x,event !rdy) { nat{N} y; x = a; y = b; do { if(x>=y) next(x) = x-y; else next(y) = y-x; pause; } while(x!=0 & y!=0); if(x==0) next(x) = y; pause; emit(rdy); } drivenby { a = 126; b = 56; await(rdy); }