// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// The function below computes the greatest common divisor using the extended
// Euclidean algorithm. In addition to the greatest common divisor g of two
// numbers a,b it also computes numbers s,t such that g = s*a + t*b holds.
// ************************************************************************** //

function extendedEuclid(nat a,b) : nat {
    nat q,r,s,t,old_r,old_s,old_t,y;
    r = b;
    s = 0;
    t = 1;
    old_r = a;
    old_s = 1;
    old_t = 0;
    while(r!=0) {
        q = old_r / r;
        y = r;
        r = old_r - q * r;
        old_r = y;
        y = s;
        s = old_s - q * s;
        old_s = y;
        y = t;
        t = old_t - q * t;
        old_t = y;
    }
    return old_r;
}


thread ExtendedEuclid {
    nat x,y,z;
    z = extendedEuclid(x,y);
}