uintpoly.h
Go to the documentation of this file.
1 
5 #ifndef SYMENGINE_UINTPOLY_H
6 #define SYMENGINE_UINTPOLY_H
7 
8 #include <symengine/polys/usymenginepoly.h>
9 
10 namespace SymEngine
11 {
12 // Calculates bit length of number, used in UIntDict*= only
13 template <typename T>
14 unsigned int bit_length(T t)
15 {
16  unsigned int count = 0;
17  while (t > 0) {
18  count++;
19  t = t >> 1;
20  }
21  return count;
22 }
23 
24 class UIntDict : public ODictWrapper<unsigned int, integer_class, UIntDict>
25 {
26 
27 public:
28  UIntDict() SYMENGINE_NOEXCEPT {}
29  ~UIntDict() SYMENGINE_NOEXCEPT {}
30  UIntDict(UIntDict &&other) SYMENGINE_NOEXCEPT
31  : ODictWrapper(std::move(other))
32  {
33  }
34  UIntDict(const int &i) : ODictWrapper(i) {}
35  UIntDict(const map_uint_mpz &p) : ODictWrapper(p) {}
36  UIntDict(const integer_class &i) : ODictWrapper(i) {}
37 
38  UIntDict(const UIntDict &) = default;
39  UIntDict &operator=(const UIntDict &) = default;
40 
42  integer_class eval_bit(const unsigned int &x) const
43  {
44  unsigned int last_deg = dict_.rbegin()->first;
45  integer_class result(0);
46 
47  for (auto it = dict_.rbegin(); it != dict_.rend(); ++it) {
48  result <<= x * (last_deg - (*it).first);
49  result += (*it).second;
50  last_deg = (*it).first;
51  }
52  result <<= x * last_deg;
53 
54  return result;
55  }
56 
57  static UIntDict mul(const UIntDict &a, const UIntDict &b)
58  {
59  int mul = 1;
60 
61  unsigned int N = bit_length(std::min(a.degree() + 1, b.degree() + 1))
62  + bit_length(a.max_abs_coef())
63  + bit_length(b.max_abs_coef());
64 
65  integer_class full = integer_class(1), temp, res;
66  full <<= N;
67  integer_class thresh = full / 2;
68  integer_class mask = full - 1;
69  integer_class s_val = a.eval_bit(N) * b.eval_bit(N);
70  if (s_val < 0)
71  mul = -1;
72  s_val = mp_abs(s_val);
73 
74  unsigned int deg = 0, carry = 0;
75  UIntDict r;
76 
77  while (s_val != 0 or carry != 0) {
78  mp_and(temp, s_val, mask);
79  if (temp < thresh) {
80  res = mul * (temp + carry);
81  if (res != 0)
82  r.dict_[deg] = res;
83  carry = 0;
84  } else {
85  res = mul * (temp - full + carry);
86  if (res != 0)
87  r.dict_[deg] = res;
88  carry = 1;
89  }
90  s_val >>= N;
91  deg++;
92  }
93  return r;
94  }
95 
96  int compare(const UIntDict &other) const
97  {
98  if (dict_.size() != other.dict_.size())
99  return (dict_.size() < other.dict_.size()) ? -1 : 1;
100  return unified_compare(dict_, other.dict_);
101  }
102 
103  integer_class max_abs_coef() const
104  {
105  integer_class curr(mp_abs(dict_.begin()->second));
106  for (const auto &it : dict_) {
107  if (mp_abs(it.second) > curr)
108  curr = mp_abs(it.second);
109  }
110  return curr;
111  }
112 
113 }; // UIntDict
114 
115 class UIntPoly : public USymEnginePoly<UIntDict, UIntPolyBase, UIntPoly>
116 {
117 public:
118  IMPLEMENT_TYPEID(SYMENGINE_UINTPOLY)
120  UIntPoly(const RCP<const Basic> &var, UIntDict &&dict);
121 
123  hash_t __hash__() const;
124 }; // UIntPoly
125 
126 // true & sets `out` to b/a if a exactly divides b, otherwise false & undefined
127 bool divides_upoly(const UIntPoly &a, const UIntPoly &b,
128  const Ptr<RCP<const UIntPoly>> &res);
129 
130 } // namespace SymEngine
131 
132 #endif
#define IMPLEMENT_TYPEID(SYMENGINE_ID)
Inline members and functions.
Definition: basic.h:340
integer_class eval_bit(const unsigned int &x) const
Evaluates the dict_ at value 2**x.
Definition: uintpoly.h:42
hash_t __hash__() const
Definition: uintpoly.cpp:11
UIntPoly(const RCP< const Basic > &var, UIntDict &&dict)
Constructor of UIntPoly class.
Definition: uintpoly.cpp:6
T count(T... args)
T min(T... args)
T move(T... args)
Main namespace for SymEngine package.
Definition: add.cpp:19
RCP< const Basic > mul(const RCP< const Basic > &a, const RCP< const Basic > &b)
Multiplication.
Definition: mul.cpp:358
int unified_compare(const T &a, const T &b)
Definition: dict.h:205