// ************************************************************************** // // // // 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 // // // // ************************************************************************** // // A simple implementation of Euclid's algorithm for computing the greatest // // common divisor of two 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, y*t=b, and a=q*b+r // // imply x*t = q*y*t+r, i.e., r = (x-q*y) * t so that each common divisor t// // of a and b also divides r = a%b. // // * Divisors(b,a%b) <= Divisors(a,b) holds, since x*t=b, y*t=r, and a=q*b+r // // imply a = q*x*t+y*t = (q*x+y)*t, so that each common divisor t // // of b and r=a%b also divides a. // // According to Lamé (1844), the algorithm never takes more steps than the // // number of digits of the smaller number (a or b) in base 10. Worst case // // examples are moreover the Fibonacci numbers, i.e. GCD(Fib(i+1),Fib(i)). // // ************************************************************************** // macro N = 1000; module EuclidMod(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); }