G_do_hoelder: fix case with real x values which are not of type cl_R.
[ginac.git] / ginac / polynomial / gcd_euclid.h
1 /** @file gcd_euclid.h
2  *
3  *  GCD using Euclidean algorithm. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2018 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