|
715
|
1 function [g, v] = gcd (a, ...) |
|
|
2 |
|
904
|
3 # [g [, v]] = gcd (a) returns the greatest common divisor g of the |
|
|
4 # entries of the integer vector a, and an integer vector v such that |
|
|
5 # g = v(1) * a(k) + ... + v(k) * a(k). |
|
|
6 # |
|
|
7 # [g [, v]] = gcd (a1, ..., ak) is the same with a = [a1, ..., ak]. |
|
715
|
8 |
|
904
|
9 # Written by KH (Kurt.Hornik@ci.tuwien.ac.at) on Sep 16, 1994 |
|
|
10 # Copyright Dept of Statistics and Probability Theory TU Wien |
|
715
|
11 |
|
|
12 if (nargin > 1) |
|
|
13 va_start; |
|
904
|
14 for k = 2:nargin; |
|
|
15 a = [a, va_arg ()]; |
|
715
|
16 endfor |
|
|
17 endif |
|
|
18 |
|
904
|
19 if (round (a) != a) |
|
|
20 error ("gcd: all arguments must be integer"); |
|
715
|
21 endif |
|
|
22 |
|
904
|
23 g = abs (a(1)); |
|
|
24 v = sign (a(1)); |
|
|
25 for k = 1:(length (a) - 1) |
|
715
|
26 x = [g, 1, 0]; |
|
904
|
27 y = [abs (a(k+1)), 0, 1]; |
|
715
|
28 while (y(1) > 0) |
|
904
|
29 r = x - y * floor (x(1) / y(1)); |
|
715
|
30 x = y; |
|
|
31 y = r; |
|
|
32 endwhile |
|
|
33 g = x(1); |
|
904
|
34 v = [x(2) * v, x(3) * sign (a(k+1))]; |
|
715
|
35 endfor |
|
|
36 |
|
|
37 endfunction |
|
|
38 |
