[5a66d0] | 1 | #include <stdio.h> |
---|
| 2 | #include <stdlib.h> |
---|
| 3 | #include <string.h> |
---|
| 4 | #include <time.h> |
---|
| 5 | |
---|
[599326] | 6 | #include <Singular/mod2.h> |
---|
[5a66d0] | 7 | #include <omalloc.h> |
---|
[599326] | 8 | #include <kernel/polys.h> |
---|
| 9 | #include <kernel/numbers.h> |
---|
| 10 | #include <kernel/ring.h> |
---|
| 11 | #include <kernel/ideals.h> |
---|
| 12 | #include <Singular/subexpr.h> |
---|
| 13 | #include <kernel/kbuckets.h> |
---|
| 14 | #include <kernel/longrat.h> |
---|
[5a66d0] | 15 | |
---|
| 16 | #if (defined(__CYGWIN__)) |
---|
| 17 | #include <ctype.h> |
---|
| 18 | #endif |
---|
| 19 | #include <stdarg.h> |
---|
| 20 | |
---|
[599326] | 21 | #include <kernel/febase.h> |
---|
| 22 | #include <Singular/janet.h> |
---|
| 23 | #include <kernel/kutil.h> |
---|
[5a66d0] | 24 | |
---|
| 25 | //------GLOBALS------- |
---|
| 26 | static int m_s,v_s,vectorized,VarN1,offset; |
---|
| 27 | static jList *T,*Q; |
---|
| 28 | static TreeM *G; |
---|
| 29 | static Poly *phD; |
---|
| 30 | static NodeM *FreeNodes; |
---|
| 31 | static int degree_compatible; |
---|
| 32 | static int (*ListGreatMove)(jList *,jList *,poly); |
---|
| 33 | static int Mask[8]={0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1}; |
---|
| 34 | |
---|
| 35 | //#define DebugPrint |
---|
| 36 | |
---|
| 37 | //#define pow_(x) pTotaldegree((x)) |
---|
| 38 | //#define pow_(x) pDeg((x)) |
---|
| 39 | pFDegProc jDeg; |
---|
[08db0a] | 40 | #define pow_(x) jDeg((x),currRing) |
---|
[5a66d0] | 41 | |
---|
| 42 | void Debug() |
---|
| 43 | { |
---|
| 44 | LCI it=T->root; |
---|
| 45 | |
---|
[ca4d0e6] | 46 | PrintS("T==================================\n"); |
---|
[5a66d0] | 47 | while (it) |
---|
| 48 | { |
---|
| 49 | pWrite(it->info->root); |
---|
| 50 | it=it->next; |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | it=Q->root; |
---|
| 54 | |
---|
[ca4d0e6] | 55 | PrintS("Q==================================\n"); |
---|
[5a66d0] | 56 | while (it) |
---|
| 57 | { |
---|
| 58 | if (it->info->root) pWrite(it->info->root); |
---|
| 59 | else |
---|
| 60 | { |
---|
| 61 | Print("%d.........",it->info->prolonged); |
---|
| 62 | pWrite(it->info->history); |
---|
| 63 | } |
---|
| 64 | it=it->next; |
---|
| 65 | } |
---|
[ca4d0e6] | 66 | PrintS("===================================\n"); |
---|
[5a66d0] | 67 | } |
---|
| 68 | |
---|
| 69 | int ReducePolyLead(Poly *x,Poly *y) |
---|
| 70 | { |
---|
| 71 | if (!x->root || !y->root) |
---|
| 72 | return 0; |
---|
| 73 | |
---|
| 74 | /* poly b1=pDivide(x->root,y->root); |
---|
| 75 | |
---|
| 76 | number gcd=nGcd(pGetCoeff(x->root),pGetCoeff(y->root),currRing); |
---|
| 77 | |
---|
| 78 | number a1=nDiv(pGetCoeff(y->root),gcd); |
---|
| 79 | pGetCoeff(b1)=nDiv(pGetCoeff(x->root),gcd); |
---|
| 80 | |
---|
| 81 | x->root=pMult_nn(x->root,a1); |
---|
| 82 | nDelete(&a1); |
---|
| 83 | |
---|
| 84 | x->root=pMinus_mm_Mult_qq(x->root,b1,y->root); |
---|
| 85 | |
---|
| 86 | pDelete(&b1); |
---|
| 87 | */ |
---|
| 88 | #if 1 |
---|
| 89 | if (x->root_b==NULL) |
---|
| 90 | { |
---|
| 91 | if (x->root_l<=0) x->root_l=pLength(x->root); |
---|
| 92 | x->root_b=kBucketCreate(currRing); |
---|
| 93 | kBucketInit(x->root_b,x->root,x->root_l); |
---|
| 94 | } |
---|
| 95 | number coef; |
---|
| 96 | if (y->root_l<=0) y->root_l=pLength(y->root); |
---|
| 97 | coef=kBucketPolyRed(x->root_b,y->root,y->root_l,NULL); |
---|
| 98 | nDelete(&coef); |
---|
| 99 | x->root=kBucketGetLm(x->root_b); |
---|
| 100 | if (x->root==NULL) |
---|
| 101 | { |
---|
| 102 | kBucketDestroy(&x->root_b); |
---|
| 103 | x->root_b=NULL; |
---|
| 104 | x->root_l=0; |
---|
| 105 | } |
---|
| 106 | #else |
---|
| 107 | x->root=ksOldSpolyRed(y->root,x->root,NULL); |
---|
| 108 | #endif |
---|
[6e0750] | 109 | // if (x->root) p_Content(x->root,currRing); |
---|
[5a66d0] | 110 | // if (x->root) pSimpleContent(x->root,5); |
---|
| 111 | |
---|
| 112 | return 1; |
---|
| 113 | } |
---|
| 114 | |
---|
| 115 | int ReducePoly(Poly *x,poly from,Poly *y) |
---|
| 116 | { |
---|
| 117 | if (!x->root || !y->root) |
---|
| 118 | return 0; |
---|
| 119 | |
---|
| 120 | /* poly b1=pDivide(from,y->root); |
---|
| 121 | |
---|
| 122 | number gcd=nGcd(pGetCoeff(from),pGetCoeff(y->root),currRing); |
---|
| 123 | |
---|
| 124 | number a1=nDiv(pGetCoeff(y->root),gcd); |
---|
| 125 | pGetCoeff(b1)=nDiv(pGetCoeff(from),gcd); |
---|
| 126 | |
---|
| 127 | x->root=pMult_nn(x->root,a1); |
---|
| 128 | nDelete(&a1);*/ |
---|
| 129 | |
---|
| 130 | // x->root=pMinus_mm_Mult_qq(x->root,b1,y->root); |
---|
| 131 | // pDelete(&b1); |
---|
| 132 | |
---|
| 133 | ksOldSpolyTail(y->root,x->root,from,NULL,currRing); |
---|
| 134 | y->root_l=0; |
---|
| 135 | |
---|
| 136 | return 1; |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | void PNF(Poly *p, TreeM *F) |
---|
| 140 | { |
---|
| 141 | if (p->root==NULL) return; |
---|
| 142 | |
---|
| 143 | Poly *f; |
---|
| 144 | BOOLEAN done=FALSE; |
---|
| 145 | poly temp=p->root; |
---|
| 146 | |
---|
| 147 | // if (TEST_OPT_PROT) { PrintS("r"); mflush(); } |
---|
| 148 | int count=0; |
---|
| 149 | poly pp=p->root; |
---|
| 150 | int old_size=nSize(pGetCoeff(pp)); |
---|
| 151 | p->root_l=0; |
---|
| 152 | while(temp->next) |
---|
| 153 | { |
---|
| 154 | f=is_div_(F,temp->next); |
---|
| 155 | if (f) |
---|
| 156 | { |
---|
| 157 | if (ReducePoly(p,temp,f)) //temp->next |
---|
| 158 | { |
---|
| 159 | count++; |
---|
| 160 | //if (TEST_OPT_PROT) { PrintS("-"); mflush(); } |
---|
| 161 | if ((f!=NULL) |
---|
| 162 | && (count>20) |
---|
| 163 | && (nSize(pGetCoeff(pp))>old_size) |
---|
| 164 | ) |
---|
| 165 | { |
---|
| 166 | //pSimpleContent(pp,2); |
---|
[6e0750] | 167 | p_Content(pp,currRing); |
---|
[5a66d0] | 168 | count=0; |
---|
| 169 | // old_size=nSize(pGetCoeff(pp)); |
---|
| 170 | } |
---|
| 171 | } |
---|
| 172 | done=TRUE; |
---|
| 173 | } |
---|
| 174 | else |
---|
| 175 | temp=temp->next; |
---|
| 176 | } |
---|
| 177 | |
---|
[6e0750] | 178 | if (done) p_Content(p->root,currRing); |
---|
[5a66d0] | 179 | //if (done) pSimpleContent(p->root,-1); |
---|
| 180 | pTest(p->root); |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | void NFL(Poly *p, TreeM *F) |
---|
| 184 | { |
---|
| 185 | Poly *f; |
---|
| 186 | int g1,f1,gg; |
---|
| 187 | |
---|
| 188 | if ((f=is_div_(F,p->lead))==NULL) return; |
---|
| 189 | |
---|
| 190 | int pX=pow_(p->lead); |
---|
| 191 | int phX=pow_(p->history); |
---|
| 192 | |
---|
| 193 | if (pX!=phX) |
---|
| 194 | { |
---|
| 195 | int phF=pow_(f->history); |
---|
| 196 | if (pX >= (phX+phF)) |
---|
| 197 | { |
---|
| 198 | pDelete(&p->root); |
---|
| 199 | //p->root=NULL; |
---|
| 200 | return; |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | /* poly p2=pInit(); |
---|
| 204 | pLcm(p->history,f->history,p2); |
---|
| 205 | pSetm(p2); |
---|
| 206 | |
---|
| 207 | if (pLmCmp(p->root,p2) > 0) |
---|
| 208 | { |
---|
| 209 | pLmDelete(&p2); |
---|
| 210 | pDelete(&p->root); |
---|
| 211 | //p->root=NULL; |
---|
| 212 | return; |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | pLmDelete(&p2); |
---|
| 216 | */ |
---|
| 217 | /* for(int i=0, gg=0 ; i<currRing->N;i++) |
---|
| 218 | if ((g1=pGetExp(p->history,i+1)) > (f1=pGetExp(f->history,i+1))) |
---|
| 219 | gg+=g1; |
---|
| 220 | else gg+=f1; |
---|
| 221 | |
---|
| 222 | if (pX > gg) |
---|
| 223 | { |
---|
| 224 | pDelete(&p->root); |
---|
| 225 | //x->root=NULL; |
---|
| 226 | return; |
---|
| 227 | } |
---|
| 228 | */ |
---|
| 229 | int pF=pow_(f->lead); |
---|
| 230 | |
---|
| 231 | if ((pX == pF) && (pF == phF)) |
---|
| 232 | { |
---|
| 233 | pLmDelete(&f->history); |
---|
| 234 | f->history=pCopy(p->history); |
---|
| 235 | } |
---|
| 236 | } |
---|
| 237 | |
---|
| 238 | //if (TEST_OPT_PROT) { PrintS("R"); mflush(); } |
---|
| 239 | int old_size, count; |
---|
| 240 | count=0; |
---|
| 241 | while(f && p->root) |
---|
| 242 | { |
---|
[ca4d0e6] | 243 | // PrintS("R"); |
---|
[5a66d0] | 244 | // if (TEST_OPT_PROT) { PrintS("R"); mflush(); } |
---|
| 245 | #if 0 |
---|
| 246 | old_size=nSize(pGetCoeff(p->root)); |
---|
| 247 | #endif |
---|
| 248 | if (ReducePolyLead(p,f) == 0) break; |
---|
| 249 | if (p->root!=NULL) |
---|
| 250 | { |
---|
| 251 | count++; |
---|
| 252 | #if 0 |
---|
| 253 | if ((count>4) && (3<nSize(pGetCoeff(p->root))) |
---|
| 254 | && (nSize(pGetCoeff(p->root))>old_size)) |
---|
| 255 | { |
---|
| 256 | pSimpleContent(p->root,old_size); |
---|
| 257 | count=0; |
---|
| 258 | } |
---|
| 259 | #else |
---|
| 260 | if (count>500) |
---|
| 261 | { |
---|
| 262 | kBucketClear(p->root_b,&p->root,&p->root_l); |
---|
| 263 | pSimpleContent(p->root,2); |
---|
| 264 | kBucketInit(p->root_b,p->root,p->root_l); |
---|
| 265 | count=0; |
---|
[ca4d0e6] | 266 | //PrintS("."); |
---|
[5a66d0] | 267 | } |
---|
| 268 | #endif |
---|
| 269 | f=is_div_(F,p->root); |
---|
| 270 | } |
---|
| 271 | } |
---|
| 272 | #if 1 |
---|
| 273 | if (p->root_b!=NULL) |
---|
| 274 | { |
---|
| 275 | kBucketClear(p->root_b,&p->root,&p->root_l); |
---|
| 276 | kBucketDestroy(&p->root_b); |
---|
| 277 | p->root_b=NULL; |
---|
| 278 | } |
---|
| 279 | #endif |
---|
| 280 | |
---|
| 281 | if (!p->root) |
---|
| 282 | return; |
---|
| 283 | |
---|
| 284 | InitHistory(p); |
---|
| 285 | InitProl(p); |
---|
| 286 | InitLead(p); |
---|
| 287 | p->changed=1; |
---|
| 288 | |
---|
[6e0750] | 289 | p_Content(p->root,currRing); |
---|
[5a66d0] | 290 | //pSimpleContent(p->root,-1); |
---|
| 291 | pTest(p->root); |
---|
| 292 | } |
---|
| 293 | |
---|
| 294 | int ValidatePoly(Poly *x, TreeM *F) |
---|
| 295 | { |
---|
| 296 | Poly *f,*g; |
---|
| 297 | int g1,f1; |
---|
| 298 | |
---|
| 299 | if (x->root) return 1; |
---|
| 300 | |
---|
| 301 | g=is_present(T,x->history); //it's a prolongation - do we have a parent ? |
---|
| 302 | |
---|
| 303 | if (!g) return 0; //if not - kill him ! |
---|
| 304 | |
---|
| 305 | poly lmX=pDivide(x->lead,g->root); |
---|
| 306 | pGetCoeff(lmX)=nInit(1); |
---|
| 307 | |
---|
| 308 | /* if ((f=is_div_(F,lmX)) != NULL) |
---|
| 309 | { |
---|
| 310 | int pX=pow_(lmX); |
---|
| 311 | int phX=pow_(x->history); |
---|
| 312 | |
---|
| 313 | if (pX!=phX) |
---|
| 314 | { |
---|
| 315 | int phF=pow_(f->history); |
---|
| 316 | if (pX >= (phX+phF)) |
---|
| 317 | { |
---|
| 318 | pLmDelete(&lmX); |
---|
| 319 | //x->root=NULL; |
---|
| 320 | return 0; |
---|
| 321 | } |
---|
| 322 | |
---|
| 323 | for(int i=0, gg=0 ; i<currRing->N;i++) |
---|
| 324 | if ((g1=pGetExp(x->history,i+1)) > (f1=pGetExp(f->history,i+1))) |
---|
| 325 | gg+=g1; |
---|
| 326 | else |
---|
| 327 | gg+=f1; |
---|
| 328 | |
---|
| 329 | if (pX > gg) |
---|
| 330 | { |
---|
| 331 | pLmDelete(&lmX); |
---|
| 332 | return 0; |
---|
| 333 | } |
---|
| 334 | int pF=pow_(f->root); |
---|
| 335 | |
---|
| 336 | if ((pX == pF) && (pF == phF)) |
---|
| 337 | f->history=x->history; |
---|
| 338 | } |
---|
| 339 | } |
---|
| 340 | |
---|
| 341 | pLmDelete(&lmX); |
---|
| 342 | |
---|
| 343 | */ |
---|
| 344 | x->root=pCopy(g->root); |
---|
| 345 | x->root_l=g->root_l; |
---|
| 346 | |
---|
| 347 | x->root=pMult(x->root,lmX); |
---|
| 348 | |
---|
| 349 | pTest(x->root); |
---|
| 350 | |
---|
| 351 | x->prolonged=-1; |
---|
| 352 | |
---|
| 353 | return 1; |
---|
| 354 | } |
---|
| 355 | |
---|
| 356 | Poly *NewPoly(poly p) |
---|
| 357 | { |
---|
| 358 | Poly *beg=(Poly *)GCM(sizeof(Poly)); |
---|
| 359 | |
---|
| 360 | beg->root=p;//(p == NULL ? pInit() : p); |
---|
| 361 | beg->root_b=NULL; |
---|
| 362 | beg->root_l=0; |
---|
| 363 | beg->history=NULL;//pInit(); |
---|
| 364 | beg->lead=NULL; |
---|
| 365 | beg->mult=(char *)GCMA(sizeof(char)*2*offset); |
---|
| 366 | |
---|
| 367 | for (int i=0; i < currRing->N; i++) |
---|
| 368 | { |
---|
| 369 | ClearMult(beg,i); |
---|
| 370 | ClearProl(beg,i); |
---|
| 371 | }; |
---|
| 372 | |
---|
| 373 | beg->prolonged=-1; |
---|
| 374 | |
---|
| 375 | return beg; |
---|
| 376 | } |
---|
| 377 | |
---|
| 378 | void DestroyPoly(Poly *x) |
---|
| 379 | { |
---|
| 380 | pDelete(&x->root); |
---|
| 381 | pDelete(&x->history); |
---|
| 382 | if (x->lead) pDelete(&x->lead); |
---|
| 383 | GCF(x->mult); |
---|
| 384 | GCF(x); |
---|
| 385 | } |
---|
| 386 | |
---|
| 387 | void ControlProlong(Poly *x) |
---|
| 388 | { |
---|
| 389 | for (int i = 0; i< offset; i++) |
---|
| 390 | { |
---|
| 391 | (x->mult+offset)[i]&=~((x->mult)[i]); |
---|
| 392 | // if (!GetMult(x,i) && !GetProl(x,i)) |
---|
| 393 | // ProlVar(x,i); |
---|
| 394 | } |
---|
| 395 | } |
---|
| 396 | |
---|
| 397 | void InitHistory(Poly *p) |
---|
| 398 | { |
---|
| 399 | if (p->history) pLmDelete(&p->history); |
---|
| 400 | p->history=pLmInit(p->root); |
---|
| 401 | p->changed=0; |
---|
| 402 | } |
---|
| 403 | |
---|
| 404 | void InitLead(Poly *p) |
---|
| 405 | { |
---|
| 406 | if (p->lead) pLmDelete(&p->lead); |
---|
| 407 | p->lead=pLmInit(p->root); |
---|
| 408 | p->prolonged=-1; |
---|
| 409 | } |
---|
| 410 | |
---|
| 411 | void InitProl(Poly *p) |
---|
| 412 | { |
---|
| 413 | memset(p->mult+offset,0,sizeof(char)*offset); |
---|
| 414 | } |
---|
| 415 | |
---|
| 416 | int GetMult(Poly *x,int i) |
---|
| 417 | { |
---|
| 418 | return x->mult[i/8] & Mask[i%8]; |
---|
| 419 | } |
---|
| 420 | |
---|
| 421 | void SetMult(Poly *x,int i) |
---|
| 422 | { |
---|
| 423 | x->mult[i/8] |= Mask[i%8]; |
---|
| 424 | } |
---|
| 425 | |
---|
| 426 | void ClearMult(Poly *x,int i) |
---|
| 427 | { |
---|
| 428 | x->mult[i/8] &= ~Mask[i%8]; |
---|
| 429 | } |
---|
| 430 | |
---|
| 431 | int GetProl(Poly *x, int i) |
---|
| 432 | { |
---|
| 433 | return (x->mult+offset)[i/8] & Mask[i%8]; |
---|
| 434 | } |
---|
| 435 | |
---|
| 436 | void SetProl(Poly *x, int i) |
---|
| 437 | { |
---|
| 438 | (x->mult+offset)[i/8] |= Mask[i%8]; |
---|
| 439 | } |
---|
| 440 | |
---|
| 441 | void ClearProl(Poly *x, int i) |
---|
| 442 | { |
---|
| 443 | (x->mult+offset)[i/8] &= ~Mask[i%8]; |
---|
| 444 | } |
---|
| 445 | |
---|
| 446 | int LengthCompare(poly p1,poly p2) |
---|
| 447 | { |
---|
| 448 | do |
---|
| 449 | { |
---|
| 450 | if (p1 == NULL) return 1; |
---|
| 451 | if (p2 == NULL) return 0; |
---|
| 452 | pIter(p1); |
---|
| 453 | pIter(p2); |
---|
| 454 | }while(p1 && p2); |
---|
| 455 | return 1; |
---|
| 456 | } |
---|
| 457 | |
---|
| 458 | int ProlCompare(Poly *item1, Poly *item2) |
---|
| 459 | { |
---|
| 460 | switch(pLmCmp(item1->lead,item2->lead)) |
---|
| 461 | { |
---|
| 462 | case -1: |
---|
| 463 | return 1; |
---|
| 464 | |
---|
| 465 | case 1: |
---|
| 466 | return 0; |
---|
| 467 | |
---|
| 468 | default: |
---|
| 469 | if ((item1->root_l<=0)||(item2->root_l<=0)) |
---|
| 470 | return LengthCompare(item1->root,item2->root); |
---|
| 471 | return item1->root_l<=item2->root_l; |
---|
| 472 | } |
---|
| 473 | } |
---|
| 474 | |
---|
| 475 | void ProlVar(Poly *temp,int i) |
---|
| 476 | { |
---|
| 477 | Poly *Pr; |
---|
| 478 | |
---|
| 479 | if (!GetProl(temp,i) && !GetMult(temp,i)) |
---|
| 480 | { |
---|
| 481 | Pr=NewPoly(); |
---|
| 482 | SetProl(temp,i); |
---|
| 483 | |
---|
| 484 | Pr->prolonged=i; |
---|
| 485 | Pr->history=pLmInit(temp->history); |
---|
| 486 | Pr->lead=pLmInit(temp->lead); |
---|
| 487 | pIncrExp(Pr->lead,i+1); |
---|
| 488 | pSetm(Pr->lead); |
---|
| 489 | InitProl(temp); |
---|
| 490 | |
---|
| 491 | Pr->changed=0; |
---|
| 492 | // pTest(Pr->root); |
---|
| 493 | InsertInCount(Q,Pr); |
---|
| 494 | } |
---|
| 495 | } |
---|
| 496 | |
---|
| 497 | void DestroyListNode(ListNode *x) |
---|
| 498 | { |
---|
| 499 | DestroyPoly(x->info); |
---|
| 500 | GCF(x); |
---|
| 501 | } |
---|
| 502 | |
---|
| 503 | ListNode* CreateListNode(Poly *x) |
---|
| 504 | { |
---|
| 505 | ListNode* ret=(ListNode *)GCM(sizeof(ListNode)); |
---|
| 506 | ret->info=x; |
---|
| 507 | ret->next=NULL; |
---|
| 508 | return ret; |
---|
| 509 | } |
---|
| 510 | |
---|
| 511 | |
---|
| 512 | Poly *FindMinList(jList *L) |
---|
| 513 | { |
---|
| 514 | LI min=&(L->root); |
---|
| 515 | LI l; |
---|
| 516 | LCI xl; |
---|
| 517 | Poly *x; |
---|
| 518 | |
---|
| 519 | if (degree_compatible) |
---|
| 520 | { |
---|
| 521 | while ((*min) && ((*min)->info->root == NULL)) |
---|
| 522 | min=&((*min)->next); |
---|
| 523 | } |
---|
| 524 | |
---|
| 525 | if (!(*min)) return NULL; |
---|
| 526 | |
---|
| 527 | l=&((*min)->next); |
---|
| 528 | |
---|
| 529 | while (*l) |
---|
| 530 | { |
---|
| 531 | if ((*l)->info->root != NULL) |
---|
| 532 | { |
---|
| 533 | if (ProlCompare((*l)->info,(*min)->info)) |
---|
| 534 | min=l; |
---|
| 535 | } |
---|
| 536 | |
---|
| 537 | l=&((*l)->next); |
---|
| 538 | } |
---|
| 539 | x=(*min)->info; |
---|
| 540 | xl=*min; |
---|
| 541 | *min=(*min)->next; |
---|
| 542 | GCF(xl); |
---|
| 543 | |
---|
| 544 | return x; |
---|
| 545 | } |
---|
| 546 | |
---|
| 547 | void InsertInList(jList *x,Poly *y) |
---|
| 548 | { |
---|
| 549 | ListNode *ins; |
---|
| 550 | LI ix=&(x->root); |
---|
| 551 | |
---|
| 552 | while (*ix) |
---|
| 553 | { |
---|
| 554 | if (pLmCmp(y->lead,(*ix)->info->lead) == -1) |
---|
| 555 | ix=(ListNode **)&((*ix)->next); |
---|
| 556 | else |
---|
| 557 | break; |
---|
| 558 | } |
---|
| 559 | |
---|
| 560 | ins=CreateListNode(y); |
---|
| 561 | ins->next=(ListNode *)(*ix); |
---|
| 562 | *ix=ins; |
---|
| 563 | return; |
---|
| 564 | } |
---|
| 565 | |
---|
| 566 | void InsertInCount(jList *x,Poly *y) |
---|
| 567 | { |
---|
| 568 | ListNode *ins; |
---|
| 569 | LI ix=&(x->root); |
---|
| 570 | |
---|
| 571 | ins=CreateListNode(y); |
---|
| 572 | ins->next=(ListNode *)(*ix); |
---|
| 573 | *ix=ins; |
---|
| 574 | return; |
---|
| 575 | } |
---|
| 576 | |
---|
| 577 | int ListGreatMoveOrder(jList *A,jList *B,poly x) |
---|
| 578 | { |
---|
| 579 | LCI y=A->root; |
---|
| 580 | |
---|
| 581 | if (!y || pLmCmp(y->info->lead,x) < 0) return 0; |
---|
| 582 | |
---|
| 583 | while(y && pLmCmp(y->info->lead,x) >= 0) |
---|
| 584 | { |
---|
| 585 | InsertInCount(B,y->info); |
---|
| 586 | A->root=y->next; |
---|
| 587 | GCF(y); |
---|
| 588 | y=A->root; |
---|
| 589 | } |
---|
| 590 | |
---|
| 591 | return 1; |
---|
| 592 | } |
---|
| 593 | |
---|
| 594 | int ListGreatMoveDegree(jList *A,jList *B,poly x) |
---|
| 595 | { |
---|
| 596 | LCI y=A->root; |
---|
| 597 | int pow_x=pow_(x); |
---|
| 598 | |
---|
| 599 | if (!y || pow_(y->info->lead) <= pow_x) return 0; |
---|
| 600 | |
---|
| 601 | while(y && pow_(y->info->lead) > pow_x) |
---|
| 602 | { |
---|
| 603 | InsertInCount(B,y->info); |
---|
| 604 | A->root=y->next; |
---|
| 605 | GCF(y); |
---|
| 606 | y=A->root; |
---|
| 607 | } |
---|
| 608 | |
---|
| 609 | return 1; |
---|
| 610 | } |
---|
| 611 | |
---|
| 612 | int CountList(jList *Q) |
---|
| 613 | { |
---|
| 614 | int i=0; |
---|
| 615 | LCI y=Q->root; |
---|
| 616 | |
---|
| 617 | while(y) |
---|
| 618 | { |
---|
| 619 | i++; |
---|
| 620 | y=y->next; |
---|
| 621 | } |
---|
| 622 | |
---|
| 623 | return i; |
---|
| 624 | } |
---|
| 625 | |
---|
| 626 | void NFListQ() |
---|
| 627 | { |
---|
| 628 | LCI ll; |
---|
| 629 | int p,p1; |
---|
| 630 | LI l; |
---|
| 631 | |
---|
| 632 | do |
---|
| 633 | { |
---|
| 634 | if (!Q->root) break; |
---|
| 635 | |
---|
| 636 | ll=Q->root; |
---|
| 637 | |
---|
| 638 | p=pow_(Q->root->info->lead); |
---|
| 639 | |
---|
| 640 | while (ll) |
---|
| 641 | { |
---|
| 642 | int ploc=pow_(ll->info->lead); |
---|
| 643 | if (ploc < p) p=ploc; |
---|
| 644 | ll=ll->next; |
---|
| 645 | } |
---|
| 646 | |
---|
| 647 | p1=1; |
---|
| 648 | |
---|
| 649 | l=&(Q->root); |
---|
| 650 | |
---|
| 651 | while (*l) |
---|
| 652 | { |
---|
[ca4d0e6] | 653 | // PrintS("*"); |
---|
[5a66d0] | 654 | int ploc=pow_((*l)->info->lead); |
---|
| 655 | |
---|
| 656 | if (ploc == p) |
---|
| 657 | { |
---|
| 658 | if (!ValidatePoly((*l)->info,G)) |
---|
| 659 | { |
---|
| 660 | ll=(*l); |
---|
| 661 | *l=(*l)->next; |
---|
| 662 | DestroyListNode(ll); |
---|
| 663 | continue; |
---|
| 664 | }; |
---|
| 665 | |
---|
| 666 | (*l)->info->changed=0; |
---|
[ca4d0e6] | 667 | // PrintS("!"); |
---|
[5a66d0] | 668 | NFL((*l)->info,G); |
---|
[ca4d0e6] | 669 | // PrintS("$"); |
---|
[5a66d0] | 670 | if (!(*l)->info->root) |
---|
| 671 | { |
---|
| 672 | ll=(*l); |
---|
| 673 | *l=(*l)->next; |
---|
| 674 | DestroyListNode(ll); |
---|
| 675 | continue; |
---|
| 676 | }; |
---|
| 677 | p1=0; |
---|
| 678 | } |
---|
| 679 | |
---|
| 680 | l=&((*l)->next); |
---|
| 681 | } |
---|
| 682 | }while(p1); |
---|
[ca4d0e6] | 683 | // PrintLn(); |
---|
[5a66d0] | 684 | } |
---|
| 685 | |
---|
| 686 | |
---|
| 687 | void ForEachPNF(jList *x,int i) |
---|
| 688 | { |
---|
| 689 | LCI y=x->root; |
---|
| 690 | |
---|
| 691 | while(y) |
---|
| 692 | { |
---|
| 693 | if (pow_(y->info->root) == i) PNF(y->info,G); |
---|
| 694 | y=y->next; |
---|
| 695 | } |
---|
| 696 | } |
---|
| 697 | |
---|
| 698 | void ForEachControlProlong(jList *x) |
---|
| 699 | { |
---|
| 700 | LCI y=x->root; |
---|
| 701 | |
---|
| 702 | while(y) |
---|
| 703 | { |
---|
| 704 | ControlProlong(y->info); |
---|
| 705 | y=y->next; |
---|
| 706 | } |
---|
| 707 | } |
---|
| 708 | |
---|
| 709 | void DestroyList(jList *x) |
---|
| 710 | { |
---|
| 711 | LCI y=x->root,z; |
---|
| 712 | |
---|
| 713 | while(y) |
---|
| 714 | { |
---|
| 715 | z=y->next; |
---|
| 716 | DestroyPoly(y->info); |
---|
| 717 | GCF(y); |
---|
| 718 | y=z; |
---|
| 719 | } |
---|
| 720 | |
---|
| 721 | GCF(x); |
---|
| 722 | } |
---|
| 723 | |
---|
| 724 | Poly* is_present(jList *F,poly x) |
---|
| 725 | { |
---|
| 726 | LCI iF=F->root; |
---|
| 727 | while(iF) |
---|
| 728 | if (pLmCmp(iF->info->root,x) == 0) |
---|
| 729 | return iF->info; |
---|
| 730 | else iF=iF->next; |
---|
| 731 | |
---|
| 732 | return NULL; |
---|
| 733 | } |
---|
| 734 | |
---|
| 735 | int GB_length() |
---|
| 736 | { |
---|
| 737 | LCI iT=T->root; |
---|
| 738 | int l=0; |
---|
| 739 | |
---|
| 740 | while(iT) |
---|
| 741 | { |
---|
| 742 | if (pow_(iT->info->lead) == pow_(iT->info->history)) |
---|
| 743 | ++l; |
---|
| 744 | iT=iT->next; |
---|
| 745 | } |
---|
| 746 | |
---|
| 747 | return l; |
---|
| 748 | } |
---|
| 749 | |
---|
| 750 | static Poly *temp_l; |
---|
| 751 | |
---|
| 752 | NodeM* create() |
---|
| 753 | { |
---|
| 754 | NodeM *y; |
---|
| 755 | |
---|
| 756 | if (FreeNodes == NULL) |
---|
| 757 | { |
---|
| 758 | y=(NodeM *)GCM(sizeof(NodeM)); |
---|
| 759 | } |
---|
| 760 | else |
---|
| 761 | { |
---|
| 762 | y=FreeNodes; |
---|
| 763 | FreeNodes=FreeNodes->left; |
---|
| 764 | } |
---|
| 765 | |
---|
| 766 | y->left=y->right=NULL; |
---|
| 767 | y->ended=NULL; |
---|
| 768 | return y; |
---|
| 769 | } |
---|
| 770 | |
---|
| 771 | void DestroyFreeNodes() |
---|
| 772 | { |
---|
| 773 | NodeM *y; |
---|
| 774 | |
---|
| 775 | while((y=FreeNodes)!=NULL) |
---|
| 776 | { |
---|
| 777 | FreeNodes=FreeNodes->left; |
---|
| 778 | GCF(y); |
---|
| 779 | } |
---|
| 780 | } |
---|
| 781 | |
---|
| 782 | static void go_right(NodeM *current,poly_function disp) |
---|
| 783 | { |
---|
| 784 | if (current) |
---|
| 785 | { |
---|
| 786 | go_right(current->left,disp); |
---|
| 787 | if (current->ended) disp(current->ended); |
---|
| 788 | go_right(current->right,disp); |
---|
| 789 | } |
---|
| 790 | } |
---|
| 791 | |
---|
| 792 | void ForEach(TreeM *t,poly_function disp) |
---|
| 793 | { |
---|
| 794 | go_right(t->root,disp); |
---|
| 795 | } |
---|
| 796 | |
---|
| 797 | void DestroyTree(NodeM *G) |
---|
| 798 | { |
---|
| 799 | if (G) |
---|
| 800 | { |
---|
| 801 | DestroyTree(G->left); |
---|
| 802 | DestroyTree(G->right); |
---|
| 803 | G->left=FreeNodes; |
---|
| 804 | FreeNodes=G; |
---|
| 805 | } |
---|
| 806 | } |
---|
| 807 | |
---|
| 808 | void Define(TreeM **G) |
---|
| 809 | { |
---|
| 810 | *G=(TreeM *)GCM(sizeof(TreeM)); |
---|
| 811 | (*G)->root=create(); |
---|
| 812 | } |
---|
| 813 | |
---|
| 814 | int sp_div(poly m1,poly m2,int from) |
---|
| 815 | { |
---|
| 816 | |
---|
| 817 | if (pow_(m2) == 0 && pow_(m1)) return 0; |
---|
| 818 | |
---|
| 819 | for(int k=from; k < currRing->N; k++) |
---|
| 820 | if (pGetExp(m1,k+1) < pGetExp(m2,k+1)) return 0; |
---|
| 821 | |
---|
| 822 | return 1; |
---|
| 823 | } |
---|
| 824 | |
---|
| 825 | void div_l(poly item, NodeM *x,int from) |
---|
| 826 | { |
---|
| 827 | if (x && !temp_l) |
---|
| 828 | { |
---|
| 829 | div_l(item,x->left,from); |
---|
| 830 | if ((x->ended) && sp_div(item,x->ended->root,from)) |
---|
| 831 | { |
---|
| 832 | temp_l=x->ended; |
---|
| 833 | return; |
---|
| 834 | }; |
---|
| 835 | div_l(item,x->right,from); |
---|
| 836 | } |
---|
| 837 | } |
---|
| 838 | |
---|
| 839 | Poly* is_div_upper(poly item, NodeM *x,int from) |
---|
| 840 | { |
---|
| 841 | temp_l=NULL; |
---|
| 842 | div_l(item,x,from); |
---|
| 843 | return temp_l; |
---|
| 844 | } |
---|
| 845 | |
---|
| 846 | Poly* is_div_(TreeM *tree, poly item) |
---|
| 847 | { |
---|
| 848 | int power_tmp,i,i_con=currRing->N-1; |
---|
| 849 | NodeM *curr=tree->root; |
---|
| 850 | |
---|
| 851 | if (!curr) return NULL; |
---|
| 852 | if (pow_(item) == 0) return NULL; |
---|
| 853 | |
---|
| 854 | for ( ; i_con>=0 && !pGetExp(item,i_con+1) ; i_con--) |
---|
| 855 | ; |
---|
| 856 | |
---|
| 857 | for (i=0; i <= i_con ; i++) |
---|
| 858 | { |
---|
| 859 | power_tmp=pGetExp(item,i+1); |
---|
| 860 | |
---|
| 861 | while (power_tmp) |
---|
| 862 | { |
---|
| 863 | if (curr->ended) return curr->ended; |
---|
| 864 | |
---|
| 865 | if (!curr->left) |
---|
| 866 | { |
---|
| 867 | if (curr->right) |
---|
| 868 | return is_div_upper(item,curr->right,i); //?????? |
---|
| 869 | return NULL; |
---|
| 870 | } |
---|
| 871 | |
---|
| 872 | curr=curr->left; |
---|
| 873 | power_tmp--; |
---|
| 874 | } |
---|
| 875 | |
---|
| 876 | if (curr->ended) return curr->ended; |
---|
| 877 | |
---|
| 878 | if (!curr->right) return NULL; |
---|
| 879 | |
---|
| 880 | curr=curr->right; |
---|
| 881 | } |
---|
| 882 | |
---|
| 883 | if (curr->ended) return curr->ended; |
---|
| 884 | else return NULL; |
---|
| 885 | } |
---|
| 886 | |
---|
| 887 | static void ClearMultiplicative(NodeM *xx,int i) |
---|
| 888 | { |
---|
| 889 | if (!xx) return; |
---|
| 890 | |
---|
| 891 | while (xx->left) |
---|
| 892 | { |
---|
| 893 | ClearMultiplicative(xx->right, i); |
---|
| 894 | xx = xx->left; |
---|
| 895 | } |
---|
| 896 | if ((xx->ended) && (GetMult(xx->ended,i))) |
---|
| 897 | { |
---|
| 898 | ClearMult(xx->ended,i); |
---|
| 899 | ProlVar(xx->ended,i); |
---|
| 900 | } |
---|
| 901 | else |
---|
| 902 | ClearMultiplicative(xx->right,i); |
---|
| 903 | } |
---|
| 904 | //====================================================== |
---|
| 905 | void insert_(TreeM **tree, Poly *item) |
---|
| 906 | { |
---|
| 907 | int power_tmp,i,i_con=currRing->N-1; |
---|
| 908 | NodeM *curr=(*tree)->root; |
---|
| 909 | |
---|
| 910 | for ( ; (i_con>=0) && !pGetExp(item->root,i_con+1) ; i_con--) |
---|
| 911 | SetMult(item,i_con); |
---|
| 912 | |
---|
| 913 | for (i = 0; i<= i_con; i++) |
---|
| 914 | //<= |
---|
| 915 | { |
---|
| 916 | power_tmp=pGetExp(item->root,i+1); |
---|
| 917 | |
---|
| 918 | ClearMult(item,i); |
---|
| 919 | |
---|
| 920 | while (power_tmp) |
---|
| 921 | { |
---|
| 922 | if (!curr->left) |
---|
| 923 | { |
---|
| 924 | SetMult(item,i); |
---|
| 925 | ClearMultiplicative(curr->right,i); |
---|
| 926 | curr->left=create(); |
---|
| 927 | }; |
---|
| 928 | curr=curr->left; |
---|
| 929 | power_tmp--; |
---|
| 930 | }; |
---|
| 931 | |
---|
| 932 | if (i<i_con) |
---|
| 933 | { |
---|
| 934 | if (!curr->left) SetMult(item,i); |
---|
| 935 | if (!curr->right) curr->right=create(); |
---|
| 936 | curr=curr->right; |
---|
| 937 | |
---|
| 938 | ProlVar(item,i); |
---|
| 939 | } |
---|
| 940 | } |
---|
| 941 | |
---|
| 942 | curr->ended=item; |
---|
| 943 | } |
---|
| 944 | |
---|
| 945 | void Initialization(char *Ord) |
---|
| 946 | { |
---|
| 947 | offset=(currRing->N % 8 == 0) ? (currRing->N/8)*8 : (currRing->N/8+1)*8; |
---|
| 948 | if (strstr(Ord,"dp\0") || strstr(Ord,"Dp\0")) |
---|
| 949 | { |
---|
| 950 | degree_compatible=1; |
---|
| 951 | jDeg=pDeg; |
---|
| 952 | ListGreatMove=ListGreatMoveDegree; |
---|
| 953 | } |
---|
| 954 | else |
---|
| 955 | { |
---|
| 956 | degree_compatible=0; |
---|
| 957 | jDeg=pTotaldegree; |
---|
| 958 | ListGreatMove=ListGreatMoveOrder; |
---|
| 959 | } |
---|
| 960 | |
---|
| 961 | Define(&G); |
---|
| 962 | }; |
---|
| 963 | |
---|
| 964 | static Poly *h,*f; |
---|
| 965 | |
---|
| 966 | void insert_in_G(Poly *x) |
---|
| 967 | { |
---|
| 968 | insert_(&G,x); |
---|
| 969 | } |
---|
| 970 | |
---|
| 971 | void T2G(); |
---|
| 972 | |
---|
| 973 | void Q2TG() |
---|
| 974 | { |
---|
| 975 | LCI t; |
---|
| 976 | Poly *x; |
---|
| 977 | |
---|
| 978 | while (Q->root) |
---|
| 979 | { |
---|
| 980 | t=Q->root; |
---|
| 981 | x=t->info; |
---|
| 982 | insert_(&G,x); |
---|
| 983 | InsertInList(T,x); |
---|
| 984 | Q->root=t->next; |
---|
| 985 | GCF(t); |
---|
| 986 | } |
---|
| 987 | } |
---|
| 988 | |
---|
| 989 | int ComputeBasis(jList *_T,jList *_Q) |
---|
| 990 | { |
---|
| 991 | int gb_l,i,ret_value=1; |
---|
| 992 | |
---|
| 993 | T=_T; Q=_Q; |
---|
| 994 | |
---|
| 995 | // Debug(); |
---|
| 996 | |
---|
| 997 | while((h=FindMinList(Q))!=NULL) |
---|
| 998 | { |
---|
[ca4d0e6] | 999 | // PrintS("New element\n"); |
---|
[5a66d0] | 1000 | // Debug(); |
---|
| 1001 | |
---|
| 1002 | if (!degree_compatible) |
---|
| 1003 | { |
---|
| 1004 | if (!ValidatePoly(h,G)) |
---|
| 1005 | { |
---|
| 1006 | DestroyPoly(h); |
---|
| 1007 | continue; |
---|
| 1008 | } |
---|
| 1009 | |
---|
| 1010 | h->changed=0; |
---|
| 1011 | |
---|
| 1012 | NFL(h,G); |
---|
| 1013 | |
---|
| 1014 | if (!h->root) |
---|
| 1015 | { |
---|
| 1016 | DestroyPoly(h); |
---|
| 1017 | continue; |
---|
| 1018 | } |
---|
| 1019 | } |
---|
| 1020 | |
---|
| 1021 | if (h->root) |
---|
| 1022 | { |
---|
| 1023 | if (pIsConstant(h->root)) |
---|
| 1024 | { |
---|
| 1025 | WarnS("Constant in basis\n"); |
---|
| 1026 | return 0; |
---|
| 1027 | } |
---|
| 1028 | |
---|
| 1029 | if (h->changed && ListGreatMove(T,Q,h->root)) |
---|
| 1030 | { |
---|
[ca4d0e6] | 1031 | // PrintS("<-\n"); |
---|
[5a66d0] | 1032 | DestroyTree(G->root); |
---|
| 1033 | G->root=create(); |
---|
| 1034 | T2G(); |
---|
| 1035 | } |
---|
| 1036 | } |
---|
| 1037 | |
---|
[ca4d0e6] | 1038 | // PrintS("PNF\n"); |
---|
[5a66d0] | 1039 | PNF(h,G); |
---|
| 1040 | // Print("{%d}\n",pow_(h->root)); |
---|
| 1041 | insert_(&G,h); |
---|
| 1042 | InsertInList(T,h); |
---|
| 1043 | |
---|
[ca4d0e6] | 1044 | // PrintS("For each PNF\n"); |
---|
[5a66d0] | 1045 | if (degree_compatible) |
---|
| 1046 | ForEachPNF(T,pow_(h->root)); |
---|
| 1047 | |
---|
[ca4d0e6] | 1048 | // PrintS("Control of prolongations\n"); |
---|
[5a66d0] | 1049 | if (h->changed) |
---|
| 1050 | ForEachControlProlong(T); |
---|
| 1051 | else |
---|
| 1052 | ControlProlong(h); |
---|
| 1053 | |
---|
| 1054 | // Debug(); |
---|
| 1055 | |
---|
[ca4d0e6] | 1056 | // PrintS("NFListQ\n"); |
---|
[5a66d0] | 1057 | if (degree_compatible) |
---|
| 1058 | NFListQ(); |
---|
| 1059 | //Debug(); |
---|
| 1060 | } |
---|
| 1061 | |
---|
| 1062 | // gb_l=GB_length(); |
---|
| 1063 | |
---|
| 1064 | Print("Length of Janet basis: %d\n",CountList(T)); |
---|
| 1065 | // Print("Length of Groebner basis: %d\n",gb_l); |
---|
| 1066 | |
---|
| 1067 | DestroyTree(G->root); |
---|
| 1068 | GCF(G); |
---|
| 1069 | DestroyFreeNodes(); |
---|
| 1070 | |
---|
| 1071 | return 1; |
---|
| 1072 | } |
---|
| 1073 | |
---|
| 1074 | void T2G() |
---|
| 1075 | { |
---|
| 1076 | LCI i=T->root; |
---|
| 1077 | while (i) |
---|
| 1078 | { |
---|
| 1079 | insert_(&G,i->info); |
---|
| 1080 | i=i->next; |
---|
| 1081 | } |
---|
| 1082 | } |
---|