[a6a239] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
| 4 | /*************************************************************** |
---|
| 5 | * File: pInline2.h |
---|
| 6 | * Purpose: implementation of poly procs which are of constant time |
---|
| 7 | * Author: obachman (Olaf Bachmann) |
---|
| 8 | * Created: 8/00 |
---|
[cb66fa] | 9 | * Version: $Id: pInline2.h,v 1.3 2000-09-14 13:04:39 obachman Exp $ |
---|
[a6a239] | 10 | *******************************************************************/ |
---|
| 11 | #ifndef PINLINE2_H |
---|
| 12 | #define PINLINE2_H |
---|
| 13 | |
---|
| 14 | /*************************************************************** |
---|
| 15 | * |
---|
| 16 | * Primitives for accessing and setting fields of a poly |
---|
| 17 | * |
---|
| 18 | ***************************************************************/ |
---|
| 19 | #if !defined(NO_PINLINE2) || defined(PINLINE2_CC) |
---|
| 20 | |
---|
| 21 | #include "mod2.h" |
---|
| 22 | #include "omalloc.h" |
---|
| 23 | #include "structs.h" |
---|
| 24 | #include "polys.h" |
---|
| 25 | #include "numbers.h" |
---|
| 26 | #include "p_Procs.h" |
---|
| 27 | |
---|
| 28 | |
---|
| 29 | PINLINE2 number p_SetCoeff(poly p, number n, ring r) |
---|
| 30 | { |
---|
[cb66fa] | 31 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 32 | p_nDelete(&(p->coef), r); |
---|
| 33 | (p)->coef=n; |
---|
| 34 | return n; |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | // order |
---|
| 38 | PINLINE2 Order_t p_GetOrder(poly p, ring r) |
---|
| 39 | { |
---|
[cb66fa] | 40 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 41 | return ((p)->exp[r->pOrdIndex]); |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | PINLINE2 Order_t p_SetOrder(poly p, long o, ring r) |
---|
| 45 | { |
---|
[cb66fa] | 46 | p_CheckPolyRing2(p, r); |
---|
| 47 | pAssume2(o >= 0); |
---|
[a6a239] | 48 | return (p)->exp[r->pOrdIndex] = o; |
---|
| 49 | } |
---|
| 50 | |
---|
| 51 | // component |
---|
| 52 | PINLINE2 unsigned long p_SetComp(poly p, unsigned long c, ring r) |
---|
| 53 | { |
---|
[cb66fa] | 54 | p_CheckPolyRing2(p, r); |
---|
| 55 | pAssume2(rRing_has_Comp(r)); |
---|
[a6a239] | 56 | __p_GetComp(p,r) = c; |
---|
| 57 | return c; |
---|
| 58 | } |
---|
| 59 | PINLINE2 unsigned long p_IncrComp(poly p, ring r) |
---|
| 60 | { |
---|
[cb66fa] | 61 | p_CheckPolyRing2(p, r); |
---|
| 62 | pAssume2(rRing_has_Comp(r)); |
---|
[a6a239] | 63 | return ++(__p_GetComp(p,r)); |
---|
| 64 | } |
---|
| 65 | PINLINE2 unsigned long p_DecrComp(poly p, ring r) |
---|
| 66 | { |
---|
[cb66fa] | 67 | p_CheckPolyRing2(p, r); |
---|
| 68 | pAssume2(rRing_has_Comp(r)); |
---|
| 69 | pPolyAssume2(__p_GetComp(p,r) > 0); |
---|
[a6a239] | 70 | return --(__p_GetComp(p,r)); |
---|
| 71 | } |
---|
| 72 | PINLINE2 unsigned long p_AddComp(poly p, unsigned long v, ring r) |
---|
| 73 | { |
---|
[cb66fa] | 74 | p_CheckPolyRing2(p, r); |
---|
| 75 | pAssume2(rRing_has_Comp(r)); |
---|
[a6a239] | 76 | return __p_GetComp(p,r) += v; |
---|
| 77 | } |
---|
| 78 | PINLINE2 unsigned long p_SubComp(poly p, unsigned long v, ring r) |
---|
| 79 | { |
---|
[cb66fa] | 80 | p_CheckPolyRing2(p, r); |
---|
| 81 | pAssume2(rRing_has_Comp(r)); |
---|
| 82 | pPolyAssume2(__p_GetComp(p,r) >= v); |
---|
[a6a239] | 83 | return __p_GetComp(p,r) -= v; |
---|
| 84 | } |
---|
| 85 | |
---|
| 86 | // exponent |
---|
[7150eb] | 87 | // r->VarOffset encodes the position in p->exp (lower 24 bits) |
---|
| 88 | // and number of bits to shift to the right in the upper 8 bits |
---|
[a6a239] | 89 | PINLINE2 Exponent_t p_GetExp(poly p, int v, ring r) |
---|
| 90 | { |
---|
[cb66fa] | 91 | p_CheckPolyRing2(p, r); |
---|
| 92 | pAssume2(v > 0 && v <= r->N); |
---|
[a6a239] | 93 | return (p->exp[(r->VarOffset[v] & 0xffffff)] >> (r->VarOffset[v] >> 24)) |
---|
| 94 | & r->bitmask; |
---|
| 95 | } |
---|
| 96 | PINLINE2 Exponent_t p_SetExp(poly p, int v, int e, ring r) |
---|
| 97 | { |
---|
[cb66fa] | 98 | p_CheckPolyRing2(p, r); |
---|
| 99 | pAssume2(v>0 && v <= r->N); |
---|
| 100 | pAssume2(e>=0); |
---|
| 101 | pAssume2((unsigned int) e<=r->bitmask); |
---|
[a6a239] | 102 | |
---|
| 103 | // shift e to the left: |
---|
| 104 | register int shift = r->VarOffset[v] >> 24; |
---|
| 105 | unsigned long ee = ((unsigned long)e) << shift /*(r->VarOffset[v] >> 24)*/; |
---|
| 106 | // clear the bits in the exponent vector: |
---|
| 107 | register int offset = (r->VarOffset[v] & 0xffffff); |
---|
| 108 | p->exp[offset] &= |
---|
| 109 | ~( r->bitmask << shift ); |
---|
| 110 | // insert e with | |
---|
| 111 | p->exp[ offset ] |= ee; |
---|
| 112 | return e; |
---|
| 113 | } |
---|
| 114 | |
---|
| 115 | // the following should be implemented more efficiently |
---|
| 116 | PINLINE2 Exponent_t p_IncrExp(poly p, int v, ring r) |
---|
| 117 | { |
---|
[cb66fa] | 118 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 119 | Exponent_t e = p_GetExp(p,v,r); |
---|
| 120 | e++; |
---|
| 121 | return p_SetExp(p,v,e,r); |
---|
| 122 | } |
---|
| 123 | PINLINE2 Exponent_t p_DecrExp(poly p, int v, ring r) |
---|
| 124 | { |
---|
[cb66fa] | 125 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 126 | Exponent_t e = p_GetExp(p,v,r); |
---|
[cb66fa] | 127 | pAssume2(e > 0); |
---|
[a6a239] | 128 | e--; |
---|
| 129 | return p_SetExp(p,v,e,r); |
---|
| 130 | } |
---|
| 131 | PINLINE2 Exponent_t p_AddExp(poly p, int v, Exponent_t ee, ring r) |
---|
| 132 | { |
---|
[cb66fa] | 133 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 134 | Exponent_t e = p_GetExp(p,v,r); |
---|
| 135 | e += ee; |
---|
| 136 | return p_SetExp(p,v,e,r); |
---|
| 137 | } |
---|
| 138 | PINLINE2 Exponent_t p_SubExp(poly p, int v, Exponent_t ee, ring r) |
---|
| 139 | { |
---|
[cb66fa] | 140 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 141 | Exponent_t e = p_GetExp(p,v,r); |
---|
[cb66fa] | 142 | pAssume2(e >= ee); |
---|
[a6a239] | 143 | e -= ee; |
---|
| 144 | return p_SetExp(p,v,e,r); |
---|
| 145 | } |
---|
| 146 | PINLINE2 Exponent_t p_MultExp(poly p, int v, Exponent_t ee, ring r) |
---|
| 147 | { |
---|
[cb66fa] | 148 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 149 | Exponent_t e = p_GetExp(p,v,r); |
---|
| 150 | e *= ee; |
---|
| 151 | return p_SetExp(p,v,e,r); |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | PINLINE2 Exponent_t p_GetExpSum(poly p1, poly p2, int i, ring r) |
---|
| 155 | { |
---|
[cb66fa] | 156 | p_CheckPolyRing2(p1, r); |
---|
| 157 | p_CheckPolyRing2(p2, r); |
---|
[a6a239] | 158 | return p_GetExp(p1,i,r) + p_GetExp(p2,i,r); |
---|
| 159 | } |
---|
| 160 | PINLINE2 Exponent_t p_GetExpDiff(poly p1, poly p2, int i, ring r) |
---|
| 161 | { |
---|
| 162 | return p_GetExp(p1,i,r) - p_GetExp(p2,i,r); |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | |
---|
| 166 | /*************************************************************** |
---|
| 167 | * |
---|
[7150eb] | 168 | * Allocation/Initalization/Deletion |
---|
[a6a239] | 169 | * |
---|
| 170 | ***************************************************************/ |
---|
| 171 | PINLINE2 poly p_New(ring r) |
---|
| 172 | { |
---|
[cb66fa] | 173 | p_CheckRing2(r); |
---|
[a6a239] | 174 | poly p; |
---|
| 175 | omTypeAllocBin(poly, p, r->PolyBin); |
---|
| 176 | p_SetRingOfPoly(p, r); |
---|
| 177 | return p; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | PINLINE2 void p_Delete1(poly *p, ring r) |
---|
| 181 | { |
---|
[cb66fa] | 182 | pIfThen2(*p != NULL, p_CheckPolyRing2(*p, r)); |
---|
[a6a239] | 183 | poly h = *p; |
---|
| 184 | if (h != NULL) |
---|
| 185 | { |
---|
| 186 | p_nDelete(&_pGetCoeff(h), r); |
---|
| 187 | *p = _pNext(h); |
---|
| 188 | omFreeBinAddr(h); |
---|
| 189 | } |
---|
| 190 | |
---|
| 191 | } |
---|
| 192 | PINLINE2 void p_Free(poly p, ring r) |
---|
| 193 | { |
---|
[cb66fa] | 194 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 195 | omFreeBinAddr(p); |
---|
| 196 | } |
---|
| 197 | PINLINE2 poly p_FreeAndNext(poly p, ring r) |
---|
| 198 | { |
---|
[cb66fa] | 199 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 200 | poly pnext = _pNext(p); |
---|
| 201 | omFreeBinAddr(p); |
---|
| 202 | return pnext; |
---|
| 203 | } |
---|
| 204 | PINLINE2 void p_LmDelete(poly p, ring r) |
---|
| 205 | { |
---|
[cb66fa] | 206 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 207 | p_nDelete(&_pGetCoeff(p), r); |
---|
| 208 | omFreeBinAddr(p); |
---|
| 209 | } |
---|
| 210 | PINLINE2 poly p_LmDeleteAndNext(poly p, ring r) |
---|
| 211 | { |
---|
[cb66fa] | 212 | p_CheckPolyRing2(p, r); |
---|
[a6a239] | 213 | poly pnext = _pNext(p); |
---|
| 214 | p_nDelete(&_pGetCoeff(p), r); |
---|
| 215 | omFreeBinAddr(p); |
---|
| 216 | return pnext; |
---|
| 217 | } |
---|
| 218 | |
---|
| 219 | /*************************************************************** |
---|
| 220 | * |
---|
| 221 | * Misc routines |
---|
| 222 | * |
---|
| 223 | ***************************************************************/ |
---|
| 224 | PINLINE2 int p_Cmp(poly p1, poly p2, ring r) |
---|
| 225 | { |
---|
| 226 | if (p2==NULL) |
---|
| 227 | return 1; |
---|
| 228 | if (p1==NULL) |
---|
| 229 | return -1; |
---|
| 230 | return p_LmCmp(p1,p2,r); |
---|
| 231 | } |
---|
| 232 | |
---|
| 233 | /*************************************************************** |
---|
| 234 | * |
---|
[cb66fa] | 235 | * Dispatcher to r->p_Procs, they do the tests/checks |
---|
[a6a239] | 236 | * |
---|
| 237 | ***************************************************************/ |
---|
| 238 | // returns a copy of p |
---|
| 239 | PINLINE2 poly p_Copy(poly p, const ring r) |
---|
| 240 | { |
---|
| 241 | return r->p_Procs->p_Copy(p, r); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | // deletes *p, and sets *p to NULL |
---|
| 245 | PINLINE2 void p_Delete(poly *p, const ring r) |
---|
| 246 | { |
---|
| 247 | r->p_Procs->p_Delete(p, r); |
---|
| 248 | } |
---|
| 249 | |
---|
| 250 | // returns p+q, destroys p and q |
---|
| 251 | PINLINE2 poly p_Add_q(poly p, poly q, const ring r) |
---|
| 252 | { |
---|
| 253 | int shorter; |
---|
| 254 | return r->p_Procs->p_Add_q(p, q, shorter, r); |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | PINLINE2 poly p_Add_q(poly p, poly q, int &lp, int lq, const ring r) |
---|
| 258 | { |
---|
| 259 | int shorter; |
---|
| 260 | poly res = r->p_Procs->p_Add_q(p, q, shorter, r); |
---|
| 261 | lp = (lp + lq) - shorter; |
---|
| 262 | return res; |
---|
| 263 | } |
---|
| 264 | |
---|
| 265 | // returns p*n, destroys p |
---|
| 266 | PINLINE2 poly p_Mult_nn(poly p, number n, const ring r) |
---|
| 267 | { |
---|
| 268 | return r->p_Procs->p_Mult_nn(p, n, r); |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | // returns p*n, does not destroy p |
---|
| 272 | PINLINE2 poly pp_Mult_nn(poly p, number n, const ring r) |
---|
| 273 | { |
---|
| 274 | return r->p_Procs->pp_Mult_nn(p, n, r); |
---|
| 275 | } |
---|
| 276 | |
---|
| 277 | // returns Copy(p)*m, does neither destroy p nor m |
---|
| 278 | PINLINE2 poly pp_Mult_mm(poly p, poly m, const ring r) |
---|
| 279 | { |
---|
| 280 | return r->p_Procs->pp_Mult_mm(p, m, NULL, r); |
---|
| 281 | } |
---|
| 282 | |
---|
| 283 | // returns p*m, destroys p, const: m |
---|
| 284 | PINLINE2 poly p_Mult_mm(poly p, poly m, const ring r) |
---|
| 285 | { |
---|
| 286 | return r->p_Procs->p_Mult_mm(p, m, r); |
---|
| 287 | } |
---|
| 288 | |
---|
| 289 | // return p - m*Copy(q), destroys p; const: p,m |
---|
| 290 | PINLINE2 poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, const ring r) |
---|
| 291 | { |
---|
| 292 | int shorter; |
---|
| 293 | return r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r); |
---|
| 294 | } |
---|
[7150eb] | 295 | PINLINE2 poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, |
---|
[a6a239] | 296 | poly spNoether, const ring r) |
---|
| 297 | { |
---|
| 298 | int shorter; |
---|
| 299 | poly res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, spNoether, r); |
---|
| 300 | lp = (lp + lq) - shorter; |
---|
| 301 | return res; |
---|
| 302 | } |
---|
[7150eb] | 303 | |
---|
[a6a239] | 304 | // returns -p, destroys p |
---|
| 305 | PINLINE2 poly p_Neg(poly p, const ring r) |
---|
| 306 | { |
---|
| 307 | return r->p_Procs->p_Neg(p, r); |
---|
| 308 | } |
---|
| 309 | |
---|
| 310 | extern poly _p_Mult_q(poly p, poly q, const int copy, const ring r); |
---|
| 311 | // returns p*q, destroys p and q |
---|
| 312 | PINLINE2 poly p_Mult_q(poly p, poly q, const ring r) |
---|
| 313 | { |
---|
[7150eb] | 314 | if (p == NULL) |
---|
[a6a239] | 315 | { |
---|
| 316 | r->p_Procs->p_Delete(&q, r); |
---|
| 317 | return NULL; |
---|
| 318 | } |
---|
| 319 | if (q == NULL) |
---|
| 320 | { |
---|
| 321 | r->p_Procs->p_Delete(&p, r); |
---|
| 322 | return NULL; |
---|
| 323 | } |
---|
| 324 | |
---|
| 325 | if (pNext(p) == NULL) |
---|
| 326 | { |
---|
[7150eb] | 327 | |
---|
[a6a239] | 328 | q = r->p_Procs->p_Mult_mm(q, p, r); |
---|
| 329 | r->p_Procs->p_Delete(&p, r); |
---|
| 330 | return q; |
---|
| 331 | } |
---|
[7150eb] | 332 | |
---|
[a6a239] | 333 | if (pNext(q) == NULL) |
---|
| 334 | { |
---|
| 335 | p = r->p_Procs->p_Mult_mm(p, q, r); |
---|
| 336 | r->p_Procs->p_Delete(&q, r); |
---|
| 337 | return p; |
---|
| 338 | } |
---|
[7150eb] | 339 | |
---|
[a6a239] | 340 | return _p_Mult_q(p, q, 0, r); |
---|
| 341 | } |
---|
| 342 | |
---|
| 343 | // returns p*q, does neither destroy p nor q |
---|
| 344 | PINLINE2 poly pp_Mult_qq(poly p, poly q, const ring r) |
---|
| 345 | { |
---|
| 346 | if (p == NULL || q == NULL) return NULL; |
---|
| 347 | |
---|
| 348 | if (pNext(p) == NULL) |
---|
| 349 | return r->p_Procs->pp_Mult_mm(q, p, NULL, r); |
---|
[7150eb] | 350 | |
---|
[a6a239] | 351 | if (pNext(q) == NULL) |
---|
| 352 | return r->p_Procs->pp_Mult_mm(p, q, NULL, r); |
---|
| 353 | |
---|
| 354 | poly qq = q; |
---|
| 355 | if (p == q) |
---|
| 356 | qq = p_Copy(q, r); |
---|
[7150eb] | 357 | |
---|
[a6a239] | 358 | poly res = _p_Mult_q(p, qq, 1, r); |
---|
| 359 | if (qq != q) |
---|
| 360 | p_Delete(&qq, r); |
---|
| 361 | return res; |
---|
| 362 | } |
---|
| 363 | |
---|
| 364 | // returns p + m*q destroys p, const: q, m |
---|
| 365 | // this should be implemented more efficiently |
---|
| 366 | PINLINE2 poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, const ring r) |
---|
| 367 | { |
---|
| 368 | poly res; |
---|
| 369 | int shorter; |
---|
| 370 | number n_old = pGetCoeff(m); |
---|
| 371 | number n_neg = p_nCopy(n_old, r); |
---|
| 372 | n_neg = p_nNeg(n_neg, r); |
---|
| 373 | pSetCoeff0(m, n_neg); |
---|
[7150eb] | 374 | |
---|
[a6a239] | 375 | res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r); |
---|
| 376 | pSetCoeff0(m, n_old); |
---|
| 377 | p_nDelete(&n_neg, r); |
---|
| 378 | return res; |
---|
| 379 | } |
---|
| 380 | |
---|
| 381 | |
---|
| 382 | #endif // !defined(NO_PINLINE2) || defined(POLYS_IMPL_CC) |
---|
| 383 | #endif // PINLINE2_H |
---|
| 384 | |
---|