1 2# Greatest Common Divisor 3 4# This function computes the greatest common divisor (GCD) of the elements 5# of its vector argument. (The input is rounded to integer type.) The 6# scalar return value is the GCD. Its member "factors" contains an integer 7# vector such that gcd(a).factors*a is equal to gcd(a). 8 9# This was adapted from the Octave script written by Kurt Hornik. 10 11gcd = function (a) 12{ 13 local (g; v; k; x; y; r); 14 15 a = integer (vector (a)); 16 g = abs (a[1]); 17 v = sign (a[1]); 18 19 for (k in seq(a.ne-1)+1) 20 { 21 x = g, 1, 0; 22 y = abs (a[k]), 0, 1; 23 while (y[1] > 0) 24 { 25 r = x - y * integer (floor (x[1] / y[1])); 26 x = y; 27 y = r; 28 } 29 g = x[1]; 30 v = x[2] * v, x[3] * sign (a[k]); 31 } 32 33 g.factors = v; 34 return g; 35}; 36