From feb8ebaeb76fa1c94de2dd7c4e5a0999b313f8c6 Mon Sep 17 00:00:00 2001
From: David Monniaux <david.monniaux@univ-grenoble-alpes.fr>
Date: Thu, 6 Jun 2019 20:09:32 +0200
Subject: GLPK 4.65

---
 test/monniaux/glpk-4.65/src/misc/gcd.c | 102 +++++++++++++++++++++++++++++++++
 1 file changed, 102 insertions(+)
 create mode 100644 test/monniaux/glpk-4.65/src/misc/gcd.c

(limited to 'test/monniaux/glpk-4.65/src/misc/gcd.c')

diff --git a/test/monniaux/glpk-4.65/src/misc/gcd.c b/test/monniaux/glpk-4.65/src/misc/gcd.c
new file mode 100644
index 00000000..95c48cc0
--- /dev/null
+++ b/test/monniaux/glpk-4.65/src/misc/gcd.c
@@ -0,0 +1,102 @@
+/* gcd.c (greatest common divisor) */
+
+/***********************************************************************
+*  This code is part of GLPK (GNU Linear Programming Kit).
+*
+*  Copyright (C) 2000-2013 Andrew Makhorin, Department for Applied
+*  Informatics, Moscow Aviation Institute, Moscow, Russia. All rights
+*  reserved. E-mail: <mao@gnu.org>.
+*
+*  GLPK is free software: you can redistribute it and/or modify it
+*  under the terms of the GNU General Public License as published by
+*  the Free Software Foundation, either version 3 of the License, or
+*  (at your option) any later version.
+*
+*  GLPK is distributed in the hope that it will be useful, but WITHOUT
+*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+*  License for more details.
+*
+*  You should have received a copy of the GNU General Public License
+*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
+***********************************************************************/
+
+#include "env.h"
+#include "misc.h"
+
+/***********************************************************************
+*  NAME
+*
+*  gcd - find greatest common divisor of two integers
+*
+*  SYNOPSIS
+*
+*  #include "misc.h"
+*  int gcd(int x, int y);
+*
+*  RETURNS
+*
+*  The routine gcd returns gcd(x, y), the greatest common divisor of
+*  the two positive integers given.
+*
+*  ALGORITHM
+*
+*  The routine gcd is based on Euclid's algorithm.
+*
+*  REFERENCES
+*
+*  Don Knuth, The Art of Computer Programming, Vol.2: Seminumerical
+*  Algorithms, 3rd Edition, Addison-Wesley, 1997. Section 4.5.2: The
+*  Greatest Common Divisor, pp. 333-56. */
+
+int gcd(int x, int y)
+{     int r;
+      xassert(x > 0 && y > 0);
+      while (y > 0)
+         r = x % y, x = y, y = r;
+      return x;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  gcdn - find greatest common divisor of n integers
+*
+*  SYNOPSIS
+*
+*  #include "misc.h"
+*  int gcdn(int n, int x[]);
+*
+*  RETURNS
+*
+*  The routine gcdn returns gcd(x[1], x[2], ..., x[n]), the greatest
+*  common divisor of n positive integers given, n > 0.
+*
+*  BACKGROUND
+*
+*  The routine gcdn is based on the following identity:
+*
+*     gcd(x, y, z) = gcd(gcd(x, y), z).
+*
+*  REFERENCES
+*
+*  Don Knuth, The Art of Computer Programming, Vol.2: Seminumerical
+*  Algorithms, 3rd Edition, Addison-Wesley, 1997. Section 4.5.2: The
+*  Greatest Common Divisor, pp. 333-56. */
+
+int gcdn(int n, int x[])
+{     int d, j;
+      xassert(n > 0);
+      for (j = 1; j <= n; j++)
+      {  xassert(x[j] > 0);
+         if (j == 1)
+            d = x[1];
+         else
+            d = gcd(d, x[j]);
+         if (d == 1)
+            break;
+      }
+      return d;
+}
+
+/* eof */
-- 
cgit