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