Frobby 0.9.5
RawSquareFreeTerm.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
19#include "RawSquareFreeTerm.h"
20
21#include <sstream>
22#include <vector>
23
25 Word* newTermParse(const char* strParam) {
26 string str(strParam);
27 Word* term = newTerm(str.size());
28 for (size_t var = 0; var < str.size(); ++var) {
29 ASSERT(str[var] == '0' || str[var] == '1');
30 setExponent(term, var, str[var] == '1' ? 1 : 0);
31 }
32 return term;
33 }
34
35 void print(FILE* file, const Word* term, size_t varCount) {
36 ostringstream out;
37 print(out, term, varCount);
38 fputs(out.str().c_str(), file);
39 }
40
41 void print(ostream& out, const Word* term, size_t varCount) {
42 ASSERT(term != 0 || varCount == 0);
43
44 out << '(';
45 for (size_t var = 0; var < varCount; ++var) {
46 out << getExponent(term, var);
47 }
48 out << ')';
49 }
50
51 bool isIdentity(const Word* a, Word* aEnd) {
52 for (; a != aEnd; ++a)
53 if (*a != 0)
54 return false;
55 return true;
56 }
57
58 bool isIdentity(const Word* a, size_t varCount) {
59 if (varCount == 0)
60 return true;
61 while (true) {
62 if (*a != 0)
63 return false;
64 if (varCount <= BitsPerWord)
65 return true;
66 ++a;
67 varCount -= BitsPerWord;
68 }
69 }
70
71 size_t getSizeOfSupport(const Word* a, size_t varCount) {
72 if (varCount == 0)
73 return 0;
74 size_t count = 0;
75 while (true) {
76 Word word = *a;
77 // TODO: should be able to improve this set bit counting algorithm.
78 while (word != 0) {
79 if ((word & 1) != 0)
80 ++count;
81 word >>= 1;
82 }
83
84 if (varCount <= BitsPerWord)
85 return count;
86 ++a;
87 varCount -= BitsPerWord;
88 }
89 }
90
91 size_t getWordCount(size_t varCount) {
92 // Compute varCount / BitsPerWord rounded up. Special case for
93 // varCount == 0 as formula has underflow issue for that input.
94 if (varCount == 0)
95 return 1;
96 else
97 return ((varCount - 1) / BitsPerWord) + 1;
98 }
99
100 void compact(Word* compacted, const Word* term,
101 const Word* remove, size_t varCount) {
102 size_t newVarCount = 0;
103 for (size_t var = 0; var < varCount; ++var) {
104 if (getExponent(remove, var) != 0)
105 continue;
106 setExponent(compacted, newVarCount, getExponent(term, var));
107 ++newVarCount;
108 }
109 for (; newVarCount % BitsPerWord != 0; ++newVarCount)
110 setExponent(compacted, newVarCount, 0);
111
112 ASSERT(isValid(compacted, newVarCount));
113 }
114
115 void setToIdentity(Word* res, const Word* resEnd) {
116 for (; res != resEnd; ++res)
117 *res = 0;
118 }
119
120 void setToIdentity(Word* res, size_t varCount) {
121 for (; varCount >= BitsPerWord; ++res, varCount -= BitsPerWord)
122 *res = 0;
123 if (varCount > 0)
124 *res = 0;
125 }
126
128 void setToAllVarProd(Word* res, size_t varCount) {
129 for (; varCount >= BitsPerWord; ++res, varCount -= BitsPerWord)
130 *res = ~0;
131 if (varCount > 0) {
132 const Word fullSupportWord = (((Word)1) << varCount) - 1;
133 *res = fullSupportWord;
134 }
135 }
136
139 Word* newTerm(size_t varCount) {
140 const size_t wordCount = getWordCount(varCount);
141 Word* word = new Word[wordCount];
142 setToIdentity(word, word + wordCount);
143 return word;
144 }
145
151 Word* newTermParse(const char* str);
152
154 void deleteTerm(Word* term) {
155 delete[] term;
156 }
157
158 bool lexLess(const Word* a, const Word* b, size_t varCount) {
159 if (varCount == 0)
160 return false;
161 while (true) {
162 if (*a != *b) {
163 Word xorAB = (*a) ^ (*b);
164 ASSERT(xorAB != 0);
165 Word leastSignificantBit = xorAB & (-xorAB);
166 return (*a & leastSignificantBit) == 0;
167 }
168 if (varCount <= BitsPerWord)
169 return false; // a and b are equal
170 ++a;
171 ++b;
172 varCount -= BitsPerWord;
173 }
174 }
175
176 void colon(Word* res, const Word* resEnd, const Word* a, const Word* b) {
177 for (; res != resEnd; ++res, ++a, ++b)
178 *res = (*a) & (~*b);
179 }
180
181 void colonInPlace(Word* res, const Word* resEnd, const Word* b) {
182 for (; res != resEnd; ++res, ++b)
183 *res &= ~*b;
184 }
185
186 void assign(Word* a, const Word* b, size_t varCount) {
187 for (; varCount >= BitsPerWord; ++a, ++b, varCount -= BitsPerWord)
188 *a = *b;
189 if (varCount > 0)
190 *a = *b;
191 }
192
193 bool encodeTerm(Word* encoded, const Exponent* term, const size_t varCount) {
194 size_t var = 0;
195 while (var < varCount) {
196 Word bit = 1;
197 *encoded = 0;
198 do {
199 if (term[var] == 1)
200 *encoded |= bit;
201 else if (term[var] != 0)
202 return false;
203 bit <<= 1;
204 ++var;
205 } while (bit != 0 && var < varCount);
206 ++encoded;
207 }
208 return true;
209 }
210
211 bool encodeTerm(Word* encoded, const std::vector<mpz_class>& term, const size_t varCount) {
212 size_t var = 0;
213 while (var < varCount) {
214 Word bit = 1;
215 *encoded = 0;
216 do {
217 if (term[var] == 1)
218 *encoded |= bit;
219 else if (term[var] != 0)
220 return false;
221 bit <<= 1;
222 ++var;
223 } while (bit != 0 && var < varCount);
224 ++encoded;
225 }
226 return true;
227 }
228
229 bool encodeTerm(Word* encoded, const std::vector<std::string>& term, const size_t varCount) {
230 size_t var = 0;
231 while (var < varCount) {
232 Word bit = 1;
233 *encoded = 0;
234 do {
235 if (!term[var].empty()) {
236 if (term[var].size() > 1)
237 return false;
238 if (term[var][0] == '1')
239 *encoded |= bit;
240 else if (term[var][0] != '0')
241 return false;
242 }
243 bit <<= 1;
244 ++var;
245 } while (bit != 0 && var < varCount);
246 ++encoded;
247 }
248 return true;
249 }
250
251 void lcm(Word* res, const Word* resEnd,
252 const Word* a, const Word* b) {
253 for (; res != resEnd; ++a, ++b, ++res)
254 *res = (*a) | (*b);
255 }
256
257 void lcm(Word* res, const Word* a, const Word* b, size_t varCount) {
258 for (; varCount >= BitsPerWord; ++a, ++b, ++res, varCount -= BitsPerWord)
259 *res = (*a) | (*b);
260 if (varCount != 0)
261 *res = (*a) | (*b);
262 }
263
264 void lcmInPlace(Word* res, const Word* resEnd, const Word* a) {
265 for (; res != resEnd; ++a, ++res)
266 *res |= *a;
267 }
268
269 void lcmInPlace(Word* res, const Word* a, size_t varCount) {
270 for (; varCount >= BitsPerWord; ++a, ++res, varCount -= BitsPerWord)
271 *res |= *a;
272 if (varCount != 0)
273 *res |= *a;
274 }
275
276 void gcd(Word* res, const Word* resEnd, const Word* a, const Word* b) {
277 for (; res != resEnd; ++a, ++b, ++res)
278 *res = (*a) & (*b);
279 }
280
281 void gcd(Word* res, const Word* a, const Word* b, size_t varCount) {
282 for (; varCount >= BitsPerWord; ++a, ++b, ++res, varCount -= BitsPerWord)
283 *res = (*a) & (*b);
284 if (varCount != 0)
285 *res = (*a) & (*b);
286 }
287
288 void gcdInPlace(Word* res, const Word* resEnd, const Word* a) {
289 for (; res != resEnd; ++a, ++res)
290 *res &= *a;
291 }
292
293 void gcdInPlace(Word* res, const Word* a, size_t varCount) {
294 for (; varCount >= BitsPerWord; ++a, ++res, varCount -= BitsPerWord)
295 *res &= *a;
296 if (varCount != 0)
297 *res &= *a;
298 }
299
300 bool isRelativelyPrime(const Word* a, const Word* b, size_t varCount) {
301 for (; varCount >= BitsPerWord; ++a, ++b, varCount -= BitsPerWord)
302 if ((*a) & (*b))
303 return false;
304 if (varCount != 0)
305 if ((*a) & (*b))
306 return false;
307 return true;
308 }
309
311 void invert(Word* a, size_t varCount) {
312 for (; varCount >= BitsPerWord; ++a, varCount -= BitsPerWord)
313 *a = ~*a;
314 if (varCount > 0) {
315 const Word fullSupportWord = (((Word)1) << varCount) - 1;
316 *a = (~*a) & fullSupportWord;
317 }
318 }
319
322 size_t getVarIfPure(const Word* const a, size_t varCount) {
323 const Word* hit = 0;
324 size_t varsToGo = varCount;
325 const Word* it = a;
326 for (; varsToGo >= BitsPerWord; ++it, varsToGo -= BitsPerWord) {
327 if (*it != 0) {
328 if (hit != 0)
329 return varCount;
330 hit = it;
331 }
332 }
333 if (varsToGo != 0) {
334 if (*it != 0) {
335 if (hit != 0)
336 return varCount;
337 hit = it;
338 }
339 }
340 if (hit == 0)
341 return varCount;
342 size_t hitVar = (hit - a) * BitsPerWord;
343 Word word = *hit;
344 while ((word & 1) == 0) {
345 ASSERT(word != 0);
346 ++hitVar;
347 word >>= 1;
348 }
349 word >>= 1;
350 if (word != 0)
351 return varCount;
352 return hitVar;
353 }
354
356 void decrementAtSupport(const Word* a, size_t* inc, size_t varCount) {
357 if (varCount == 0)
358 return;
359 while (true) {
360 Word word = *a;
361 size_t* intraWordInc = inc;
362 while (word != 0) {
363 *intraWordInc -= word & 1; // -1 if bit set
364 ++intraWordInc;
365 word = word >> 1;
366 }
367 if (varCount <= BitsPerWord)
368 return;
369 varCount -= BitsPerWord;
370 inc += BitsPerWord;
371 ++a;
372 }
373 }
374
376 void toZeroAtSupport(const Word* a, size_t* inc, size_t varCount) {
377 if (varCount == 0)
378 return;
379 while (true) {
380 Word word = *a;
381 size_t* intraWordInc = inc;
382 while (word != 0) {
383 if (word & 1)
384 *intraWordInc = 0;
385 ++intraWordInc;
386 word = word >> 1;
387 }
388 if (varCount <= BitsPerWord)
389 return;
390 varCount -= BitsPerWord;
391 inc += BitsPerWord;
392 ++a;
393 }
394 }
395
397 bool equals(const Word* a, const Word* b, size_t varCount) {
398 if (varCount == 0)
399 return true;
400 while (true) {
401 if (*a != *b)
402 return false;
403 if (varCount <= BitsPerWord)
404 return true;
405 ++a;
406 ++b;
407 varCount -= BitsPerWord;
408 }
409 }
410
415 bool isValid(const Word* a, size_t varCount) {
416 size_t offset = varCount / BitsPerWord;
417 a += offset;
418 varCount -= BitsPerWord * offset;
419 if (varCount == 0)
420 return true;
421 const Word fullSupportWord = (((Word)1) << varCount) - 1;
422 return ((*a) & ~fullSupportWord) == 0;
423 }
424
425 void swap(Word* a, Word* b, size_t varCount) {
426 for (; varCount >= BitsPerWord; ++a, ++b, varCount -= BitsPerWord)
427 std::swap(*a, *b);
428 if (varCount > 0)
429 std::swap(*a, *b);
430 }
431}
void setExponent(Word *a, size_t var, bool value)
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
bool isValid(const Word *a, size_t varCount)
The unused bits at the end of the last word must be zero for the functions here to work correctly.
size_t getWordCount(size_t varCount)
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
bool encodeTerm(Word *encoded, const Exponent *term, const size_t varCount)
Assigns the RawSquareFreeTerm-encoded form of term to encoded and returns true if term is square free...
size_t getVarIfPure(const Word *const a, size_t varCount)
Returns var if a equals var.
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
void decrementAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, decrement inc[var] by one.
bool lexLess(const Word *a, const Word *b, size_t varCount)
bool isIdentity(const Word *a, Word *aEnd)
void toZeroAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, set inc[var] to zero.
size_t getSizeOfSupport(const Word *a, size_t varCount)
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void print(FILE *file, const Word *term, size_t varCount)
void compact(Word *compacted, const Word *term, const Word *remove, size_t varCount)
For every variable var that divides remove, remove the space for that variable in term and put the re...
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
void swap(Word *a, Word *b, size_t varCount)
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToIdentity(Word *res, const Word *resEnd)
This header file includes common definitions and is included as the first line of code in every imple...
unsigned int Exponent
Definition stdinc.h:89
static const size_t BitsPerWord
Definition stdinc.h:94
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
#define ASSERT(X)
Definition stdinc.h:86