// ----------------------------------------------------------------------------- // The extended Euclidean algorithm computes for given integers a,b numbers g, // u and v such that g = gcd(a,b) = u*a + v*b holds. It also computes numbers // s and t such that 0 = s*a + t*b holds. // ----------------------------------------------------------------------------- function ExtEuclid(int a,b):int { int q; int m,n,u,v,s,t; int m1,n1,u1,v1; m = a; n = b; u = +1; v = +0; s = +0; t = +1; assert(m == (u*a + v*b)); assert(n == (s*a + t*b)); // The loop maintains the following invariants: // (1) m == u*a + v*b // (2) n == s*a + t*b // (3) gcd(m,n) = gcd(a,b) // Note that (3) is invariant since gcd(m,n) = gcd(n,m%n), and the other // invariants are immediately seen by expanding the assignments. while(n!= +0) { q = m / n; m1 = n; n1 = m - q * n; u1 = s; v1 = t; s = u - q * s; t = v - q * t; m = m1; n = n1; u = u1; v = v1; assert(m == (u*a + v*b)); assert(n == (s*a + t*b)); } // since n=0 holds, we conclude the following from the invariants // (1) m == u*a + v*b // (2) 0 == s*a + t*b // (3) gcd(m,0) = m = gcd(a,b) return m; } thread main { int g; g = ExtEuclid(+75025,+46368); }