Loading...
Searching...
No Matches
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
10namespace SymEngine
11{
12// Calculates bit length of number, used in UIntDict*= only
13template <typename T>
14unsigned 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
24class UIntDict : public ODictWrapper<unsigned int, integer_class, UIntDict>
25{
26
27public:
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
115class UIntPoly : public USymEnginePoly<UIntDict, UIntPolyBase, UIntPoly>
116{
117public:
118 IMPLEMENT_TYPEID(SYMENGINE_UINTPOLY)
120 UIntPoly(const RCP<const Basic> &var, UIntDict &&dict);
121
123 hash_t __hash__() const override;
124}; // UIntPoly
125
126// true & sets `out` to b/a if a exactly divides b, otherwise false & undefined
127bool 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
T begin(T... args)
integer_class eval_bit(const unsigned int &x) const
Evaluates the dict_ at value 2**x.
Definition: uintpoly.h:42
hash_t __hash__() const override
Definition: uintpoly.cpp:11
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:352
int unified_compare(const T &a, const T &b)
Definition: dict.h:205
T rbegin(T... args)
T rend(T... args)
T size(T... args)