home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 10 / 10.iso / l / l460 / 2.ddi / SPECFUN.DI$ / GCD.M < prev    next >
Encoding:
Text File  |  1993-03-07  |  765 b   |  29 lines
  1. function [g,c,d] = gcd(a,b)
  2. %GCD    Greatest common divisor.
  3. %    G = GCD(A,B) is the greatest common divisor of integers A and B.
  4. %    G = GCD(0,0) is 0 by convention; all other GCDs are positive integers.
  5. %
  6. %    [G,C,D] = GCD(A,B) also returns C and D with G = A*C + B*D.
  7.  
  8. %    Algorithm: See Knuth Volume 2, Section 4.5.2, Algorithm X.
  9. %    Author:    John Gilbert, Xerox PARC
  10. %    Copyright (c) 1992 by Xerox Corporation.  All rights reserved.
  11. %    Copyright (c) 1984-93 by The MathWorks, Inc.
  12.  
  13. if round(a) ~= a | round(b) ~= b
  14.         error('Requires integer input arguments.')
  15. end
  16.  
  17. u = [1 0 abs(a)];
  18. v = [0 1 abs(b)];
  19. while v(3)
  20.     q = floor( u(3)/v(3) );
  21.     t = u - v*q;
  22.     u = v;
  23.     v = t;
  24. end
  25.  
  26. c = u(1) * sign(a);
  27. d = u(2) * sign(b);
  28. g = u(3);
  29.