ginac/polynomial/gcd_euclid.h

   1 #ifndef GINAC_GCD_EUCLID
   2 #define GINAC_GCD_EUCLID
   3 #include "upoly.h"
   4 #include "remainder.h"
   5 #include "normalize.h"
   6 #include "debug.h"
   7 #include "upoly_io.h"
   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