Implemented modular GCD algorithm for univariate polynomials.
[ginac.git] / ginac / polynomial / gcd_euclid.tcc
1 #ifndef GINAC_GCD_EUCLID
2 #define GINAC_GCD_EUCLID
3 #include "upoly.hpp"
4 #include "remainder.tcc"
5 #include "normalize.tcc"
6 #include "debug.hpp"
7 #include "upoly_io.hpp"
8
9 namespace GiNaC
10 {
11
12 static bool
13 gcd_euclid(umodpoly& c, umodpoly /* passed by value */ a, umodpoly b)
14 {
15         if (a.size() == 0) {
16                 c.clear();
17                 return true;
18         }
19         if (b.size() == 0) {
20                 c.clear();
21                 return true;
22         }
23         bug_on(a[0].ring()->modulus != b[0].ring()->modulus,
24                 "different moduli");
25
26         normalize_in_field(a);
27         normalize_in_field(b);
28         if (degree(a) < degree(b))
29                 std::swap(a, b);
30
31         umodpoly r;
32         while (b.size() != 0) {
33                 remainder_in_field(r, a, b); 
34                 a = b;
35                 b = r;
36         }
37         normalize_in_field(a);
38         c = a;
39         return false;
40 }
41
42 } // namespace GiNaC
43
44 #endif // GINAC_GCD_EUCLID
45