home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / octave-1.1.1p1-src.tgz / tar.out / fsf / octave / scripts / elfun / gcd.m < prev    next >
Text File  |  1996-09-28  |  2KB  |  57 lines
  1. # Copyright (C) 1995 John W. Eaton
  2. # 
  3. # This file is part of Octave.
  4. # 
  5. # Octave is free software; you can redistribute it and/or modify it
  6. # under the terms of the GNU General Public License as published by the
  7. # Free Software Foundation; either version 2, or (at your option) any
  8. # later version.
  9. # 
  10. # Octave is distributed in the hope that it will be useful, but WITHOUT
  11. # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12. # FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13. # for more details.
  14. # 
  15. # You should have received a copy of the GNU General Public License
  16. # along with Octave; see the file COPYING.  If not, write to the Free
  17. # Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19. function [g, v] = gcd (a, ...)
  20.  
  21. # usage: gcd (a, ...)
  22. #  
  23. # [g [, v]] = gcd (a) returns the greatest common divisor g of the
  24. # entries of the integer vector a, and an integer vector v such that
  25. # g = v(1) * a(k) + ... + v(k) * a(k).
  26. #
  27. # [g [, v]] = gcd (a1, ..., ak) is the same with a = [a1, ..., ak].
  28.   
  29. # Written by KH (Kurt.Hornik@ci.tuwien.ac.at) on Sep 16, 1994.
  30.  
  31.   if (nargin > 1)
  32.     va_start;
  33.     for k = 2:nargin;
  34.       a = [a, va_arg ()];
  35.     endfor
  36.   endif
  37.   
  38.   if (round (a) != a)
  39.     error ("gcd: all arguments must be integer");
  40.   endif
  41.   
  42.   g = abs (a(1));
  43.   v = sign (a(1));
  44.   for k = 1:(length (a) - 1)
  45.     x = [g, 1, 0];
  46.     y = [abs (a(k+1)), 0, 1];
  47.     while (y(1) > 0)
  48.       r = x - y * floor (x(1) / y(1));
  49.       x = y;
  50.       y = r;
  51.     endwhile
  52.     g = x(1);
  53.     v = [x(2) * v, x(3) * sign (a(k+1))];
  54.   endfor
  55.     
  56. endfunction
  57.