1 #ifndef KBUCKETS_H
2 #define KBUCKETS_H
3 /****************************************
4 * Computer Algebra System SINGULAR *
5 ****************************************/
6
7 //#define HAVE_COEF_BUCKETS
8
9 /////////////////////////////////////////////////////////////////////////
10 // configuration
11 //
12
13 // define to not really use the bucket feature
14 // #define HAVE_PSEUDO_BUCKETS
15 //class kBucket; typedef kBucket* kBucket_pt; // ring.h
16
17 #include "polys/monomials/ring.h" // for ring->p_Procs->p_kBucketSetLm!
18 #include "polys/templates/p_Procs.h" // for p_kBucketSetLm_Proc_Ptr
19
20 //////////////////////////////////////////////////////////////////////////
21 // Creation/Destruction of buckets
22 //
23 kBucket_pt kBucketCreate(const ring r);
24 // only free memory allocated for bucket
25 void kBucketDestroy(kBucket_pt *bucket);
26 // frees polys/monomials in bucket and destroys bucket
27 void kBucketDeleteAndDestroy(kBucket_pt *bucket);
28
29
30 /////////////////////////////////////////////////////////////////////////////
31 // Convertion from/to Bpolys
32 //
33
34 // Converts p into a bucket poly (Bpoly) and destroys p
35 // Assumes length <= 0 || pLength(p) == length
36 void kBucketInit(kBucket_pt bucket, poly p, int length);
37
38 // Converts Bpoly into a poly and clears bucket
39 // i.e., afterwards Bpoly == 0
40 void kBucketClear(kBucket_pt bucket, poly *p, int *length);
41
kBucketClear(kBucket_pt bucket)42 inline poly kBucketClear(kBucket_pt bucket)
43 {
44 int dummy;
45 poly p;
46 kBucketClear(bucket, &p, &dummy);
47 return p;
48 }
49
50 /// Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in
51 /// one bucket: Returns number of bucket into which it is canonicalized
52 int kBucketCanonicalize(kBucket_pt bucket);
53
54 /// apply n_Normalize to all coefficients
55 void kBucketNormalize(kBucket_pt bucket);
56
57 /////////////////////////////////////////////////////////////////////////////
58 // Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
59 // Bpoly == Bpoly - Lm(Bpoly)
60 //
61 inline poly kBucketExtractLm(kBucket_pt bucket);
62
63 /////////////////////////////////////////////////////////////////////////////
64 // Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
65 // Bpoly = Bpoly + m
66 // assumes that m is larger than all monomials of Bpoly
67 void kBucketSetLm(kBucket_pt bucket, poly lm);
68
69
70 //////////////////////////////////////////////////////////////////////////
71 ///
72 /// Bucket number i from bucket is out of length sync, resync
73 ///
74 void kBucketAdjust(kBucket_pt bucket, int i);
75
76 /////////////////////////////////////////////////////////////////////////////
77 // Reduces Bpoly (say, q) with p, i.e.:
78 // q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
79 // Assumes p1 != NULL, Bpoly != NULL
80 // Lm(p1) divides Lm(Bpoly)
81 // pLength(p1) == l1
82 // Returns: Lc(p) / gcd(Lc(p), Lc(q))
83 number kBucketPolyRed(kBucket_pt bucket,
84 poly p, int l,
85 poly spNoether);
86
87
88 /////////////////////////////////////////////////////////////////////////////
89 //
90 // Extract all monomials from bucket with component comp
91 // Return as a polynomial *p with length *l
92 // In other words, afterwards
93 // Bpoly == Bpoly - (poly consisting of all monomials with component comp)
94 // and components of monomials of *p are all 0
95
96 void kBucketTakeOutComp(kBucket_pt bucket,
97 long comp,
98 poly *p, int *l);
99
100 //////////////////////////////////////////////////////////////////////////
101 ///
102 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
103 ///
104 void kBucket_Mult_n(kBucket_pt bucket, number n);
105
106 //////////////////////////////////////////////////////////////////////////
107 ///
108 /// Extract all monomials of bucket which are larger than q
109 /// Append those to append, and return last monomial of append
110 poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
111
112
113 //////////////////////////////////////////////////////////////////////////
114 ///
115 /// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
116 ///
117 void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
118
119 // first, do ExtractLarger
120 // then add q
121 inline poly
kBucket_ExtractLarger_Add_q(kBucket_pt bucket,poly append,poly q,int * lq)122 kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
123 {
124 append = kBucket_ExtractLarger(bucket, q, append);
125 kBucket_Add_q(bucket, q, lq);
126 return append;
127 }
128
129 //////////////////////////////////////////////////////////////////////////
130 ///
131 /// Bpoly == Bpoly - m*p; where m is a monom
132 /// Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?)
133 /// assume (*l <= 0 || pLength(p) == *l)
134 void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
135 poly spNother = NULL);
136
137 //////////////////////////////////////////////////////////////////////////
138 ///
139 /// Bpoly == Bpoly + m*p; where m is a monom
140 /// Does not destroy p and m
141 /// assume (l <= 0 || pLength(p) == l)
142 void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
143
144 //////////////////////////////////////////////////////////////////////////
145 ///
146 /// For changing the ring of the Bpoly to new_tailBin
147 ///
148 void kBucketShallowCopyDelete(kBucket_pt bucket,
149 ring new_tailRing, omBin new_tailBin,
150 pShallowCopyDeleteProc p_shallow_copy_delete);
151
152 //////////////////////////////////////////////////////////////////////////
153 ///
154 /// Tests
155 ///
156 ///
157 #ifdef KDEBUG
158 BOOLEAN kbTest(kBucket_pt bucket);
159 #else
160 #define kbTest(bucket) do {} while (0)
161 #endif
162
163 //////////////////////////////////////////////////////////////////////////
164 ///
165 /// Bucket definition (should be no one elses business, though)
166 ///
167
168 // define this if length of bucket polys are 2, 4, 8, etc
169 // instead of 4, 16, 64 ... --
170 // this seems to be less efficient, both, in theory and in practice
171 // #define BUCKET_TWO_BASE
172 #ifdef BUCKET_TWO_BASE
173 #define MAX_BUCKET 28
174 #else
175 #define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
176 #endif
177
178 class kBucket
179 {
180 public:
181 #ifdef HAVE_PSEUDO_BUCKETS
182 poly p;
183 int l;
184 #else
185 poly buckets[MAX_BUCKET + 1]; // polys in bucket
186 #ifdef HAVE_COEF_BUCKETS
187 poly coef[MAX_BUCKET + 1]; // coeff of polys in bucket or NULL : 2..max
188 #endif
189 int buckets_length[MAX_BUCKET + 1]; // length if i-th poly
190 int buckets_used; // max number of used bucket
191 #endif
192 ring bucket_ring;
193 };
194
195 #ifndef HAVE_PSEUDO_BUCKETS
kBucketAdjustBucketsUsed(kBucket_pt bucket)196 static inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
197 {
198 while ( bucket->buckets_used > 0 &&
199 bucket->buckets[bucket->buckets_used] == NULL)
200 (bucket->buckets_used)--;
201 }
202 #endif
203
204 /////////////////////////////////////////////////////////////////////////////
205 // Gets leading monom of bucket, does NOT change Bpoly!!!!!
206 // Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
207 //
kBucketGetLm(kBucket_pt bucket,p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)208 inline poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
209 {
210 #ifdef HAVE_COEF_BUCKETS
211 assume(bucket->coef[0]==NULL);
212 #endif
213
214 poly& lead = bucket->buckets[0];
215
216 if (lead == NULL)
217 _p_kBucketSetLm(bucket);
218
219 #ifdef HAVE_COEF_BUCKETS
220 assume(bucket->coef[0]==NULL);
221 #endif
222
223 return lead;
224 }
225
kBucketGetLm(kBucket_pt bucket)226 inline poly kBucketGetLm(kBucket_pt bucket)
227 {
228 return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
229 }
230
kBucketExtractLm(kBucket_pt bucket)231 inline poly kBucketExtractLm(kBucket_pt bucket)
232 {
233 poly lm = kBucketGetLm(bucket);
234 #ifdef HAVE_COEF_BUCKETS
235 assume(bucket->coef[0]==NULL);
236 #endif
237 bucket->buckets[0] = NULL;
238 bucket->buckets_length[0] = 0;
239
240 return lm;
241 }
242
243 poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
244 void kBucketSimpleContent(kBucket_pt bucket);
245 BOOLEAN kBucketIsCleared(kBucket_pt bucket);
246 int ksCheckCoeff(number *a, number *b, const coeffs r);
247 #endif /* KBUCKETS_H */
248