[35aab3] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
| 4 | /*************************************************************** |
---|
| 5 | * File: pInline1.h |
---|
| 6 | * Purpose: implementation of poly procs which iter over ExpVector |
---|
| 7 | * Author: obachman (Olaf Bachmann) |
---|
| 8 | * Created: 8/00 |
---|
[3f685c] | 9 | * Version: $Id: pInline1.h,v 1.16 2008-07-24 16:33:57 Singular Exp $ |
---|
[35aab3] | 10 | *******************************************************************/ |
---|
| 11 | #ifndef PINLINE1_H |
---|
| 12 | #define PINLINE1_H |
---|
| 13 | |
---|
| 14 | #ifndef PDIV_DEBUG |
---|
| 15 | // define to enable debugging/statistics of pLmShortDivisibleBy |
---|
| 16 | // #define PDIV_DEBUG |
---|
| 17 | #endif |
---|
| 18 | #include <mylimits.h> |
---|
| 19 | #include "p_MemCmp.h" |
---|
| 20 | #include "structs.h" |
---|
| 21 | #include "numbers.h" |
---|
| 22 | |
---|
| 23 | #if PDEBUG > 0 || defined(NO_PINLINE1) |
---|
| 24 | |
---|
| 25 | #define _p_LmCmpAction(p, q, r, actionE, actionG, actionS) \ |
---|
| 26 | do \ |
---|
| 27 | { \ |
---|
| 28 | int _cmp = p_LmCmp(p,q,r); \ |
---|
| 29 | if (_cmp == 0) actionE; \ |
---|
| 30 | if (_cmp == 1) actionG; \ |
---|
| 31 | actionS; \ |
---|
| 32 | } \ |
---|
| 33 | while(0) |
---|
| 34 | |
---|
| 35 | #else |
---|
| 36 | |
---|
| 37 | #define _p_LmCmpAction(p, q, r, actionE, actionG, actionS) \ |
---|
| 38 | p_MemCmp_LengthGeneral_OrdGeneral(p->exp, q->exp, r->CmpL_Size, r->ordsgn, \ |
---|
| 39 | actionE, actionG, actionS) |
---|
| 40 | |
---|
| 41 | #endif |
---|
| 42 | |
---|
| 43 | #ifdef PDIV_DEBUG |
---|
[3f685c] | 44 | BOOLEAN pDebugLmShortDivisibleBy(poly p1, unsigned long sev_1, const ring r_1, |
---|
| 45 | poly p2, unsigned long not_sev_2, const ring r_2); |
---|
| 46 | BOOLEAN p_DebugLmDivisibleByNoComp(poly a, poly b, const ring r); |
---|
[35aab3] | 47 | #define pDivAssume pAssume |
---|
| 48 | #else |
---|
| 49 | #define pDivAssume(x) ((void)0) |
---|
| 50 | #endif |
---|
| 51 | |
---|
| 52 | #if !defined(NO_PINLINE1) || defined(PINLINE1_CC) |
---|
| 53 | |
---|
| 54 | #include "omalloc.h" |
---|
| 55 | #include "numbers.h" |
---|
| 56 | #include "p_polys.h" |
---|
| 57 | #include "p_MemAdd.h" |
---|
| 58 | #include "p_MemCopy.h" |
---|
| 59 | |
---|
| 60 | /*************************************************************** |
---|
| 61 | * |
---|
| 62 | * Allocation/Initalization/Deletion |
---|
| 63 | * |
---|
| 64 | ***************************************************************/ |
---|
| 65 | // adjustments for negative weights |
---|
[3f685c] | 66 | PINLINE1 void p_MemAdd_NegWeightAdjust(poly p, const ring r) |
---|
[35aab3] | 67 | { |
---|
| 68 | if (r->NegWeightL_Offset != NULL) |
---|
| 69 | { |
---|
| 70 | for (int i=r->NegWeightL_Size-1; i>=0; i--) |
---|
| 71 | { |
---|
| 72 | p->exp[r->NegWeightL_Offset[i]] -= POLY_NEGWEIGHT_OFFSET; |
---|
| 73 | } |
---|
| 74 | } |
---|
| 75 | } |
---|
[3f685c] | 76 | PINLINE1 void p_MemSub_NegWeightAdjust(poly p, const ring r) |
---|
[35aab3] | 77 | { |
---|
| 78 | if (r->NegWeightL_Offset != NULL) |
---|
| 79 | { |
---|
| 80 | for (int i=r->NegWeightL_Size-1; i>=0; i--) |
---|
| 81 | { |
---|
| 82 | p->exp[r->NegWeightL_Offset[i]] += POLY_NEGWEIGHT_OFFSET; |
---|
| 83 | } |
---|
| 84 | } |
---|
| 85 | } |
---|
| 86 | // ExpVextor(d_p) = ExpVector(s_p) |
---|
[3f685c] | 87 | PINLINE1 void p_ExpVectorCopy(poly d_p, poly s_p, const ring r) |
---|
[35aab3] | 88 | { |
---|
| 89 | p_LmCheckPolyRing1(d_p, r); |
---|
| 90 | p_LmCheckPolyRing1(s_p, r); |
---|
| 91 | p_MemCopy_LengthGeneral(d_p->exp, s_p->exp, r->ExpL_Size); |
---|
| 92 | } |
---|
| 93 | |
---|
[3f685c] | 94 | PINLINE1 poly p_Init(const ring r, omBin bin) |
---|
[35aab3] | 95 | { |
---|
| 96 | p_CheckRing1(r); |
---|
| 97 | pAssume1(bin != NULL && r->PolyBin->sizeW == bin->sizeW); |
---|
| 98 | poly p; |
---|
| 99 | omTypeAlloc0Bin(poly, p, bin); |
---|
| 100 | p_MemAdd_NegWeightAdjust(p, r); |
---|
| 101 | p_SetRingOfLm(p, r); |
---|
| 102 | return p; |
---|
| 103 | } |
---|
[3f685c] | 104 | PINLINE1 poly p_Init(const ring r) |
---|
[35aab3] | 105 | { |
---|
| 106 | return p_Init(r, r->PolyBin); |
---|
| 107 | } |
---|
| 108 | |
---|
[3f685c] | 109 | PINLINE1 poly p_LmInit(poly p, const ring r) |
---|
[35aab3] | 110 | { |
---|
| 111 | p_LmCheckPolyRing1(p, r); |
---|
| 112 | poly np; |
---|
| 113 | omTypeAllocBin(poly, np, r->PolyBin); |
---|
| 114 | p_SetRingOfLm(np, r); |
---|
| 115 | p_ExpVectorCopy(np, p, r); |
---|
| 116 | _pNext(np) = NULL; |
---|
| 117 | _pSetCoeff0(np, NULL); |
---|
| 118 | return np; |
---|
| 119 | } |
---|
[3f685c] | 120 | PINLINE1 poly p_LmInit(poly s_p, const ring s_r, const ring d_r) |
---|
[35aab3] | 121 | { |
---|
| 122 | pAssume1(d_r != NULL); |
---|
| 123 | return p_LmInit(s_p, s_r, d_r, d_r->PolyBin); |
---|
| 124 | } |
---|
[3f685c] | 125 | PINLINE1 poly p_LmInit(poly s_p, const ring s_r, const ring d_r, omBin d_bin) |
---|
[35aab3] | 126 | { |
---|
| 127 | p_LmCheckPolyRing1(s_p, s_r); |
---|
| 128 | p_CheckRing(d_r); |
---|
| 129 | pAssume1(d_r->N <= s_r->N); |
---|
| 130 | poly d_p = p_Init(d_r, d_bin); |
---|
| 131 | for (int i=d_r->N; i>0; i--) |
---|
| 132 | { |
---|
| 133 | p_SetExp(d_p, i, p_GetExp(s_p, i,s_r), d_r); |
---|
| 134 | } |
---|
| 135 | if (rRing_has_Comp(d_r)) |
---|
| 136 | { |
---|
| 137 | p_SetComp(d_p, p_GetComp(s_p,s_r), d_r); |
---|
| 138 | } |
---|
| 139 | p_Setm(d_p, d_r); |
---|
| 140 | return d_p; |
---|
| 141 | } |
---|
[3f685c] | 142 | PINLINE1 poly p_Head(poly p, const ring r) |
---|
[35aab3] | 143 | { |
---|
| 144 | if (p == NULL) return NULL; |
---|
| 145 | p_LmCheckPolyRing1(p, r); |
---|
| 146 | poly np; |
---|
| 147 | omTypeAllocBin(poly, np, r->PolyBin); |
---|
| 148 | p_SetRingOfLm(np, r); |
---|
| 149 | p_ExpVectorCopy(np, p, r); |
---|
| 150 | _pNext(np) = NULL; |
---|
| 151 | _pSetCoeff0(np, n_Copy(_pGetCoeff(p), r)); |
---|
| 152 | return np; |
---|
| 153 | } |
---|
[b8027c] | 154 | // set all exponents l..k to 0, assume exp. k+1..n and 1..l-1 are in |
---|
| 155 | // different blocks |
---|
| 156 | // set coeff to 1 |
---|
[3f685c] | 157 | PINLINE1 poly p_GetExp_k_n(poly p, int l, int k, const ring r) |
---|
[b8027c] | 158 | { |
---|
| 159 | if (p == NULL) return NULL; |
---|
| 160 | p_LmCheckPolyRing1(p, r); |
---|
| 161 | poly np; |
---|
| 162 | omTypeAllocBin(poly, np, r->PolyBin); |
---|
| 163 | p_SetRingOfLm(np, r); |
---|
| 164 | p_ExpVectorCopy(np, p, r); |
---|
| 165 | _pNext(np) = NULL; |
---|
| 166 | _pSetCoeff0(np, n_Init(1, r)); |
---|
| 167 | int i; |
---|
| 168 | for(i=l;i<=k;i++) |
---|
| 169 | { |
---|
[9fb610] | 170 | //np->exp[(r->VarOffset[i] & 0xffffff)] =0; |
---|
| 171 | p_SetExp(np,i,0,r); |
---|
[b8027c] | 172 | } |
---|
| 173 | p_Setm(np,r); |
---|
| 174 | return np; |
---|
| 175 | } |
---|
[35aab3] | 176 | |
---|
| 177 | PINLINE1 poly p_LmShallowCopyDelete(poly p, const ring r, omBin bin) |
---|
| 178 | { |
---|
| 179 | p_LmCheckPolyRing1(p, r); |
---|
| 180 | pAssume1(bin->sizeW == r->PolyBin->sizeW); |
---|
| 181 | poly new_p = p_New(r); |
---|
| 182 | p_MemCopy_LengthGeneral(new_p->exp, p->exp, r->ExpL_Size); |
---|
| 183 | pSetCoeff0(new_p, pGetCoeff(p)); |
---|
| 184 | pNext(new_p) = pNext(p); |
---|
| 185 | omFreeBinAddr(p); |
---|
| 186 | return new_p; |
---|
| 187 | } |
---|
| 188 | |
---|
| 189 | /*************************************************************** |
---|
| 190 | * |
---|
| 191 | * Operation on ExpVectors |
---|
| 192 | * |
---|
| 193 | ***************************************************************/ |
---|
| 194 | // ExpVector(p1) += ExpVector(p2) |
---|
[3f685c] | 195 | PINLINE1 void p_ExpVectorAdd(poly p1, poly p2, const ring r) |
---|
[35aab3] | 196 | { |
---|
| 197 | p_LmCheckPolyRing1(p1, r); |
---|
| 198 | p_LmCheckPolyRing1(p2, r); |
---|
| 199 | #if PDEBUG >= 1 |
---|
| 200 | for (int i=1; i<=r->N; i++) |
---|
| 201 | pAssume1((unsigned long) (p_GetExp(p1, i, r) + p_GetExp(p2, i, r)) <= r->bitmask); |
---|
| 202 | pAssume1(p_GetComp(p1, r) == 0 || p_GetComp(p2, r) == 0); |
---|
| 203 | #endif |
---|
| 204 | |
---|
| 205 | p_MemAdd_LengthGeneral(p1->exp, p2->exp, r->ExpL_Size); |
---|
| 206 | p_MemAdd_NegWeightAdjust(p1, r); |
---|
| 207 | } |
---|
| 208 | // ExpVector(p1) -= ExpVector(p2) |
---|
[3f685c] | 209 | PINLINE1 void p_ExpVectorSub(poly p1, poly p2, const ring r) |
---|
[35aab3] | 210 | { |
---|
| 211 | p_LmCheckPolyRing1(p1, r); |
---|
| 212 | p_LmCheckPolyRing1(p2, r); |
---|
| 213 | #if PDEBUG >= 1 |
---|
| 214 | for (int i=1; i<=r->N; i++) |
---|
| 215 | pAssume1(p_GetExp(p1, i, r) >= p_GetExp(p2, i, r)); |
---|
| 216 | pAssume1(p_GetComp(p1, r) == 0 || p_GetComp(p2, r) == 0 || |
---|
| 217 | p_GetComp(p1, r) == p_GetComp(p2, r)); |
---|
| 218 | #endif |
---|
| 219 | |
---|
| 220 | p_MemSub_LengthGeneral(p1->exp, p2->exp, r->ExpL_Size); |
---|
| 221 | p_MemSub_NegWeightAdjust(p1, r); |
---|
| 222 | |
---|
| 223 | } |
---|
| 224 | // ExpVector(p1) += ExpVector(p2) - ExpVector(p3) |
---|
[3f685c] | 225 | PINLINE1 void p_ExpVectorAddSub(poly p1, poly p2, poly p3, const ring r) |
---|
[35aab3] | 226 | { |
---|
| 227 | p_LmCheckPolyRing1(p1, r); |
---|
| 228 | p_LmCheckPolyRing1(p2, r); |
---|
| 229 | p_LmCheckPolyRing1(p3, r); |
---|
| 230 | #if PDEBUG >= 1 |
---|
| 231 | for (int i=1; i<=r->N; i++) |
---|
| 232 | pAssume1(p_GetExp(p1, i, r) + p_GetExp(p2, i, r) >= p_GetExp(p3, i, r)); |
---|
| 233 | pAssume1(p_GetComp(p1, r) == 0 || |
---|
| 234 | (p_GetComp(p2, r) - p_GetComp(p3, r) == 0) || |
---|
| 235 | (p_GetComp(p1, r) == p_GetComp(p2, r) - p_GetComp(p3, r))); |
---|
| 236 | #endif |
---|
| 237 | |
---|
| 238 | p_MemAddSub_LengthGeneral(p1->exp, p2->exp, p3->exp, r->ExpL_Size); |
---|
| 239 | // no need to adjust in case of NegWeights |
---|
| 240 | } |
---|
| 241 | |
---|
| 242 | // ExpVector(pr) = ExpVector(p1) + ExpVector(p2) |
---|
[3f685c] | 243 | PINLINE1 void p_ExpVectorSum(poly pr, poly p1, poly p2, const ring r) |
---|
[35aab3] | 244 | { |
---|
| 245 | p_LmCheckPolyRing1(p1, r); |
---|
| 246 | p_LmCheckPolyRing1(p2, r); |
---|
| 247 | p_LmCheckPolyRing1(pr, r); |
---|
| 248 | #if PDEBUG >= 1 |
---|
| 249 | for (int i=1; i<=r->N; i++) |
---|
| 250 | pAssume1((unsigned long) (p_GetExp(p1, i, r) + p_GetExp(p2, i, r)) <= r->bitmask); |
---|
| 251 | pAssume1(p_GetComp(p1, r) == 0 || p_GetComp(p2, r) == 0); |
---|
| 252 | #endif |
---|
| 253 | |
---|
| 254 | p_MemSum_LengthGeneral(pr->exp, p1->exp, p2->exp, r->ExpL_Size); |
---|
[347f0c] | 255 | p_MemAdd_NegWeightAdjust(pr, r); |
---|
[35aab3] | 256 | } |
---|
| 257 | // ExpVector(pr) = ExpVector(p1) - ExpVector(p2) |
---|
[3f685c] | 258 | PINLINE1 void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r) |
---|
[35aab3] | 259 | { |
---|
| 260 | p_LmCheckPolyRing1(p1, r); |
---|
| 261 | p_LmCheckPolyRing1(p2, r); |
---|
| 262 | p_LmCheckPolyRing1(pr, r); |
---|
| 263 | #if PDEBUG >= 2 |
---|
| 264 | for (int i=1; i<=r->N; i++) |
---|
| 265 | pAssume1(p_GetExp(p1, i, r) >= p_GetExp(p2, i, r)); |
---|
| 266 | pAssume1(!rRing_has_Comp(r) || p_GetComp(p1, r) == p_GetComp(p2, r)); |
---|
| 267 | #endif |
---|
| 268 | |
---|
| 269 | p_MemDiff_LengthGeneral(pr->exp, p1->exp, p2->exp, r->ExpL_Size); |
---|
[347f0c] | 270 | p_MemSub_NegWeightAdjust(pr, r); |
---|
[35aab3] | 271 | } |
---|
| 272 | |
---|
[3f685c] | 273 | PINLINE1 BOOLEAN p_ExpVectorEqual(poly p1, poly p2, const ring r) |
---|
[35aab3] | 274 | { |
---|
| 275 | p_LmCheckPolyRing1(p1, r); |
---|
| 276 | p_LmCheckPolyRing1(p2, r); |
---|
| 277 | |
---|
| 278 | int i = r->ExpL_Size; |
---|
| 279 | unsigned long *ep = p1->exp; |
---|
| 280 | unsigned long *eq = p2->exp; |
---|
| 281 | |
---|
| 282 | do |
---|
| 283 | { |
---|
| 284 | i--; |
---|
| 285 | if (ep[i] != eq[i]) return FALSE; |
---|
| 286 | } |
---|
| 287 | while (i); |
---|
| 288 | return TRUE; |
---|
| 289 | } |
---|
| 290 | |
---|
[3f685c] | 291 | PINLINE1 unsigned long p_ExpVectorQuerSum(poly p, const ring r) |
---|
[35aab3] | 292 | { |
---|
| 293 | p_LmCheckPolyRing1(p, r); |
---|
| 294 | unsigned long s = p_GetTotalDegree(p->exp[r->VarL_Offset[0]], |
---|
| 295 | r, |
---|
| 296 | r->MinExpPerLong); |
---|
| 297 | for (int i=r->VarL_Size-1; i>0; i--) |
---|
| 298 | { |
---|
| 299 | s += p_GetTotalDegree(p->exp[r->VarL_Offset[i]], r); |
---|
| 300 | } |
---|
| 301 | return s; |
---|
| 302 | } |
---|
| 303 | |
---|
[3f685c] | 304 | PINLINE1 void p_GetExpV(poly p, int *ev, const ring r) |
---|
[35aab3] | 305 | { |
---|
| 306 | p_LmCheckPolyRing1(p, r); |
---|
| 307 | for (int j = r->N; j; j--) |
---|
| 308 | ev[j] = p_GetExp(p, j, r); |
---|
| 309 | |
---|
| 310 | ev[0] = _p_GetComp(p, r); |
---|
| 311 | } |
---|
[3f685c] | 312 | PINLINE1 void p_SetExpV(poly p, int *ev, const ring r) |
---|
[35aab3] | 313 | { |
---|
| 314 | p_LmCheckPolyRing1(p, r); |
---|
| 315 | for (int j = r->N; j; j--) |
---|
| 316 | p_SetExp(p, j, ev[j], r); |
---|
| 317 | |
---|
| 318 | p_SetComp(p, ev[0],r); |
---|
| 319 | p_Setm(p, r); |
---|
| 320 | } |
---|
| 321 | |
---|
| 322 | /*************************************************************** |
---|
| 323 | * |
---|
| 324 | * Comparison w.r.t. monomial ordering |
---|
| 325 | * |
---|
| 326 | ***************************************************************/ |
---|
[3f685c] | 327 | PINLINE1 int p_LmCmp(poly p, poly q, const ring r) |
---|
[35aab3] | 328 | { |
---|
| 329 | p_LmCheckPolyRing1(p, r); |
---|
| 330 | p_LmCheckPolyRing1(q, r); |
---|
| 331 | |
---|
| 332 | p_MemCmp_LengthGeneral_OrdGeneral(p->exp, q->exp, r->CmpL_Size, r->ordsgn, |
---|
| 333 | return 0, return 1, return -1); |
---|
| 334 | } |
---|
| 335 | |
---|
| 336 | |
---|
| 337 | /*************************************************************** |
---|
| 338 | * |
---|
| 339 | * divisibility |
---|
| 340 | * |
---|
| 341 | ***************************************************************/ |
---|
| 342 | // return: FALSE, if there exists i, such that a->exp[i] > b->exp[i] |
---|
| 343 | // TRUE, otherwise |
---|
| 344 | // (1) Consider long vars, instead of single exponents |
---|
| 345 | // (2) Clearly, if la > lb, then FALSE |
---|
| 346 | // (3) Suppose la <= lb, and consider first bits of single exponents in l: |
---|
| 347 | // if TRUE, then value of these bits is la ^ lb |
---|
| 348 | // if FALSE, then la-lb causes an "overflow" into one of those bits, i.e., |
---|
| 349 | // la ^ lb != la - lb |
---|
[3f685c] | 350 | static inline BOOLEAN _p_LmDivisibleByNoComp(poly a, poly b, const ring r) |
---|
[35aab3] | 351 | { |
---|
| 352 | int i=r->VarL_Size - 1; |
---|
| 353 | unsigned long divmask = r->divmask; |
---|
| 354 | unsigned long la, lb; |
---|
| 355 | |
---|
| 356 | if (r->VarL_LowIndex >= 0) |
---|
| 357 | { |
---|
| 358 | i += r->VarL_LowIndex; |
---|
| 359 | do |
---|
| 360 | { |
---|
| 361 | la = a->exp[i]; |
---|
| 362 | lb = b->exp[i]; |
---|
| 363 | if ((la > lb) || |
---|
| 364 | (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask))) |
---|
| 365 | { |
---|
| 366 | pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE); |
---|
| 367 | return FALSE; |
---|
| 368 | } |
---|
| 369 | i--; |
---|
| 370 | } |
---|
| 371 | while (i>=r->VarL_LowIndex); |
---|
| 372 | } |
---|
| 373 | else |
---|
| 374 | { |
---|
| 375 | do |
---|
| 376 | { |
---|
| 377 | la = a->exp[r->VarL_Offset[i]]; |
---|
| 378 | lb = b->exp[r->VarL_Offset[i]]; |
---|
| 379 | if ((la > lb) || |
---|
| 380 | (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask))) |
---|
| 381 | { |
---|
| 382 | pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE); |
---|
| 383 | return FALSE; |
---|
| 384 | } |
---|
| 385 | i--; |
---|
| 386 | } |
---|
| 387 | while (i>=0); |
---|
| 388 | } |
---|
[009d80] | 389 | #ifdef HAVE_RINGS |
---|
[6cb539] | 390 | pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == nDivBy(p_GetCoeff(b, r), p_GetCoeff(a, r))); |
---|
[93ebe1] | 391 | return (!rField_is_Ring(r)) || nDivBy(p_GetCoeff(b, r), p_GetCoeff(a, r)); |
---|
[009d80] | 392 | #else |
---|
[04d04e0] | 393 | pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == TRUE); |
---|
[35aab3] | 394 | return TRUE; |
---|
[009d80] | 395 | #endif |
---|
[35aab3] | 396 | } |
---|
| 397 | |
---|
[3f685c] | 398 | static inline BOOLEAN _p_LmDivisibleByNoComp(poly a, const ring r_a, poly b, const ring r_b) |
---|
[35aab3] | 399 | { |
---|
| 400 | int i=r_a->N; |
---|
| 401 | pAssume1(r_a->N == r_b->N); |
---|
| 402 | |
---|
| 403 | do |
---|
| 404 | { |
---|
| 405 | if (p_GetExp(a,i,r_a) > p_GetExp(b,i,r_b)) |
---|
| 406 | return FALSE; |
---|
| 407 | i--; |
---|
| 408 | } |
---|
| 409 | while (i); |
---|
[009d80] | 410 | #ifdef HAVE_RINGS |
---|
| 411 | return nDivBy(p_GetCoeff(b, r), p_GetCoeff(a, r)); |
---|
| 412 | #else |
---|
| 413 | return TRUE; |
---|
[cea6f3] | 414 | #endif |
---|
[35aab3] | 415 | } |
---|
[585bbcb] | 416 | |
---|
[3f685c] | 417 | static inline BOOLEAN _p_LmDivisibleByNoCompPart(poly a, const ring r_a, poly b, const ring r_b,const int start, const int end) |
---|
| 418 | { |
---|
| 419 | int i=end; |
---|
| 420 | pAssume1(r_a->N == r_b->N); |
---|
| 421 | |
---|
| 422 | do |
---|
| 423 | { |
---|
| 424 | if (p_GetExp(a,i,r_a) > p_GetExp(b,i,r_b)) |
---|
| 425 | return FALSE; |
---|
| 426 | i--; |
---|
| 427 | } |
---|
| 428 | while (i>=start); |
---|
| 429 | #ifdef HAVE_RINGS |
---|
| 430 | return nDivBy(p_GetCoeff(b, r), p_GetCoeff(a, r)); |
---|
| 431 | #else |
---|
| 432 | return TRUE; |
---|
| 433 | #endif |
---|
| 434 | } |
---|
| 435 | static inline BOOLEAN _p_LmDivisibleBy(poly a, poly b, const ring r) |
---|
[35aab3] | 436 | { |
---|
| 437 | if (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r)) |
---|
| 438 | return _p_LmDivisibleByNoComp(a, b, r); |
---|
| 439 | return FALSE; |
---|
| 440 | } |
---|
[3f685c] | 441 | static inline BOOLEAN _p_LmDivisibleBy(poly a, const ring r_a, poly b, const ring r_b) |
---|
[35aab3] | 442 | { |
---|
| 443 | if (p_GetComp(a, r_a) == 0 || p_GetComp(a,r_a) == p_GetComp(b,r_b)) |
---|
| 444 | return _p_LmDivisibleByNoComp(a, r_a, b, r_b); |
---|
| 445 | return FALSE; |
---|
| 446 | } |
---|
[3f685c] | 447 | static inline BOOLEAN _p_LmDivisibleByPart(poly a, const ring r_a, poly b, const ring r_b,const int start, const int end) |
---|
| 448 | { |
---|
| 449 | if (p_GetComp(a, r_a) == 0 || p_GetComp(a,r_a) == p_GetComp(b,r_b)) |
---|
| 450 | return _p_LmDivisibleByNoCompPart(a, r_a, b, r_b,start,end); |
---|
| 451 | return FALSE; |
---|
| 452 | } |
---|
| 453 | PINLINE1 BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, const ring r) |
---|
[35aab3] | 454 | { |
---|
| 455 | p_LmCheckPolyRing1(a, r); |
---|
| 456 | p_LmCheckPolyRing1(b, r); |
---|
| 457 | return _p_LmDivisibleByNoComp(a, b, r); |
---|
| 458 | } |
---|
[3f685c] | 459 | PINLINE1 BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r) |
---|
[35aab3] | 460 | { |
---|
| 461 | p_LmCheckPolyRing1(b, r); |
---|
| 462 | pIfThen1(a != NULL, p_LmCheckPolyRing1(b, r)); |
---|
| 463 | if (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r)) |
---|
| 464 | return _p_LmDivisibleByNoComp(a, b, r); |
---|
| 465 | return FALSE; |
---|
| 466 | } |
---|
[3f685c] | 467 | PINLINE1 BOOLEAN p_LmDivisibleByPart(poly a, poly b, const ring r,const int start, const int end) |
---|
| 468 | { |
---|
| 469 | p_LmCheckPolyRing1(b, r); |
---|
| 470 | pIfThen1(a != NULL, p_LmCheckPolyRing1(b, r)); |
---|
| 471 | if (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r)) |
---|
| 472 | return _p_LmDivisibleByNoCompPart(a, r, b, r,start, end); |
---|
| 473 | return FALSE; |
---|
| 474 | } |
---|
[585bbcb] | 475 | |
---|
[3f685c] | 476 | PINLINE1 BOOLEAN p_DivisibleBy(poly a, poly b, const ring r) |
---|
[35aab3] | 477 | { |
---|
| 478 | pIfThen1(b!=NULL, p_LmCheckPolyRing1(b, r)); |
---|
| 479 | pIfThen1(a!=NULL, p_LmCheckPolyRing1(a, r)); |
---|
| 480 | |
---|
| 481 | if (a != NULL && (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r))) |
---|
[cea6f3] | 482 | return _p_LmDivisibleByNoComp(a,b,r); |
---|
[35aab3] | 483 | return FALSE; |
---|
| 484 | } |
---|
[3f685c] | 485 | PINLINE1 BOOLEAN p_DivisibleBy(poly a, const ring r_a, poly b, const ring r_b) |
---|
[35aab3] | 486 | { |
---|
| 487 | pIfThen1(b!=NULL, p_LmCheckPolyRing1(b, r_b)); |
---|
| 488 | pIfThen1(a!=NULL, p_LmCheckPolyRing1(a, r_a)); |
---|
[cea6f3] | 489 | if (a != NULL) { |
---|
| 490 | return _p_LmDivisibleBy(a, r_a, b, r_b); |
---|
| 491 | } |
---|
[35aab3] | 492 | return FALSE; |
---|
| 493 | } |
---|
[3f685c] | 494 | PINLINE1 BOOLEAN p_LmDivisibleBy(poly a, const ring r_a, poly b, const ring r_b) |
---|
[35aab3] | 495 | { |
---|
| 496 | p_LmCheckPolyRing(a, r_a); |
---|
| 497 | p_LmCheckPolyRing(b, r_b); |
---|
| 498 | return _p_LmDivisibleBy(a, r_a, b, r_b); |
---|
| 499 | } |
---|
| 500 | PINLINE1 BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, |
---|
[3f685c] | 501 | poly b, unsigned long not_sev_b, const ring r) |
---|
[35aab3] | 502 | { |
---|
| 503 | p_LmCheckPolyRing1(a, r); |
---|
| 504 | p_LmCheckPolyRing1(b, r); |
---|
| 505 | #ifndef PDIV_DEBUG |
---|
| 506 | _pPolyAssume2(p_GetShortExpVector(a, r) == sev_a, a, r); |
---|
| 507 | _pPolyAssume2(p_GetShortExpVector(b, r) == ~ not_sev_b, b, r); |
---|
| 508 | |
---|
| 509 | if (sev_a & not_sev_b) |
---|
| 510 | { |
---|
| 511 | pAssume1(p_LmDivisibleByNoComp(a, b, r) == FALSE); |
---|
| 512 | return FALSE; |
---|
| 513 | } |
---|
| 514 | return p_LmDivisibleBy(a, b, r); |
---|
| 515 | #else |
---|
| 516 | return pDebugLmShortDivisibleBy(a, sev_a, r, b, not_sev_b, r); |
---|
| 517 | #endif |
---|
| 518 | } |
---|
| 519 | |
---|
[3f685c] | 520 | PINLINE1 BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, const ring r_a, |
---|
| 521 | poly b, unsigned long not_sev_b, const ring r_b) |
---|
[35aab3] | 522 | { |
---|
| 523 | p_LmCheckPolyRing1(a, r_a); |
---|
| 524 | p_LmCheckPolyRing1(b, r_b); |
---|
| 525 | #ifndef PDIV_DEBUG |
---|
| 526 | _pPolyAssume2(p_GetShortExpVector(a, r_a) == sev_a, a, r_a); |
---|
| 527 | _pPolyAssume2(p_GetShortExpVector(b, r_b) == ~ not_sev_b, b, r_b); |
---|
| 528 | |
---|
| 529 | if (sev_a & not_sev_b) |
---|
| 530 | { |
---|
| 531 | pAssume1(_p_LmDivisibleByNoComp(a, r_a, b, r_b) == FALSE); |
---|
| 532 | return FALSE; |
---|
| 533 | } |
---|
| 534 | return _p_LmDivisibleBy(a, r_a, b, r_b); |
---|
| 535 | #else |
---|
| 536 | return pDebugLmShortDivisibleBy(a, sev_a, r_a, b, not_sev_b, r_b); |
---|
| 537 | #endif |
---|
| 538 | } |
---|
| 539 | |
---|
| 540 | /*************************************************************** |
---|
| 541 | * |
---|
| 542 | * Misc things on Lm |
---|
| 543 | * |
---|
| 544 | ***************************************************************/ |
---|
| 545 | // test if the monomial is a constant as a vector component |
---|
| 546 | // i.e., test if all exponents are zero |
---|
| 547 | PINLINE1 BOOLEAN p_LmIsConstantComp(const poly p, const ring r) |
---|
| 548 | { |
---|
| 549 | //p_LmCheckPolyRing(p, r); |
---|
| 550 | int i = r->VarL_Size - 1; |
---|
| 551 | |
---|
| 552 | do |
---|
| 553 | { |
---|
| 554 | if (p->exp[r->VarL_Offset[i]] != 0) |
---|
| 555 | return FALSE; |
---|
| 556 | i--; |
---|
| 557 | } |
---|
| 558 | while (i >= 0); |
---|
| 559 | return TRUE; |
---|
| 560 | } |
---|
| 561 | // test if monomial is a constant, i.e. if all exponents and the component |
---|
| 562 | // is zero |
---|
| 563 | PINLINE1 BOOLEAN p_LmIsConstant(const poly p, const ring r) |
---|
| 564 | { |
---|
| 565 | if (p_LmIsConstantComp(p, r)) |
---|
| 566 | return (p_GetComp(p, r) == 0); |
---|
| 567 | return FALSE; |
---|
| 568 | } |
---|
| 569 | |
---|
| 570 | // like the respective p_LmIs* routines, except that p might be empty |
---|
| 571 | PINLINE1 BOOLEAN p_IsConstantComp(const poly p, const ring r) |
---|
| 572 | { |
---|
| 573 | if (p == NULL) return TRUE; |
---|
| 574 | return (pNext(p)==NULL) && p_LmIsConstantComp(p, r); |
---|
| 575 | } |
---|
| 576 | |
---|
| 577 | PINLINE1 BOOLEAN p_IsConstant(const poly p, const ring r) |
---|
| 578 | { |
---|
| 579 | if (p == NULL) return TRUE; |
---|
| 580 | return (pNext(p)==NULL) && p_LmIsConstant(p, r); |
---|
| 581 | } |
---|
| 582 | |
---|
| 583 | PINLINE1 BOOLEAN p_IsUnit(const poly p, const ring r) |
---|
| 584 | { |
---|
| 585 | if (p == NULL) return FALSE; |
---|
| 586 | return p_LmIsConstant(p, r); |
---|
| 587 | } |
---|
| 588 | |
---|
| 589 | PINLINE1 BOOLEAN p_LmExpVectorAddIsOk(const poly p1, const poly p2, |
---|
| 590 | const ring r) |
---|
| 591 | { |
---|
| 592 | p_LmCheckPolyRing(p1, r); |
---|
| 593 | p_LmCheckPolyRing(p2, r); |
---|
| 594 | unsigned long l1, l2, divmask = r->divmask; |
---|
| 595 | int i; |
---|
| 596 | |
---|
| 597 | for (i=0; i<r->VarL_Size; i++) |
---|
| 598 | { |
---|
| 599 | l1 = p1->exp[r->VarL_Offset[i]]; |
---|
| 600 | l2 = p2->exp[r->VarL_Offset[i]]; |
---|
| 601 | // do the divisiblity trick |
---|
| 602 | if ( (l1 > ULONG_MAX - l2) || |
---|
| 603 | (((l1 & divmask) ^ (l2 & divmask)) != ((l1 + l2) & divmask))) |
---|
| 604 | return FALSE; |
---|
| 605 | } |
---|
| 606 | return TRUE; |
---|
| 607 | } |
---|
[f1e33bb] | 608 | #else |
---|
| 609 | PINLINE1 BOOLEAN p_IsUnit(const poly p, const ring r); |
---|
[35aab3] | 610 | |
---|
| 611 | #endif // !defined(NO_PINLINE1) || defined(PINLINE1_CC) |
---|
| 612 | #endif // PINLINE1_CC |
---|