ginac/polynomial/gcd_euclid.h

   1 /** @file gcd_euclid.h
   2  *
   3  *  GCD using Euclidean algorithm. */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999-2019 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  */
  22
  23 #ifndef GINAC_GCD_EUCLID_H
  24 #define GINAC_GCD_EUCLID_H
  25
  26 #include "upoly.h"
  27 #include "remainder.h"
  28 #include "normalize.h"
  29 #include "debug.h"
  30 #include "upoly_io.h"
  31
  32 namespace GiNaC {
  33
  34 static bool
  35 gcd_euclid(umodpoly& c, umodpoly /* passed by value */ a, umodpoly b)
  36 {
  37         if (a.size() == 0) {
  38                 c.clear();
  39                 return true;
  40         }
  41         if (b.size() == 0) {
  42                 c.clear();
  43                 return true;
  44         }
  45         bug_on(a[0].ring()->modulus != b[0].ring()->modulus,
  46                 "different moduli");
  47
  48         normalize_in_field(a);
  49         normalize_in_field(b);
  50         if (degree(a) < degree(b))
  51                 std::swap(a, b);
  52
  53         umodpoly r;
  54         while (b.size() != 0) {
  55                 remainder_in_field(r, a, b);
  56                 a = b;
  57                 b = r;
  58         }
  59         normalize_in_field(a);
  60         c = a;
  61         return false;
  62 }
  63
  64 } // namespace GiNaC
  65
  66 #endif // ndef GINAC_GCD_EUCLID_H