Changeset db83bf in git
- Timestamp:
- May 27, 2011, 4:27:42 PM (12 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
- Children:
- 5b274570b3977c8b95131bdda194e0b179f17b8b
- Parents:
- 410ea0fb1e22ebcb52e33b6789cf294a2d1f663b
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/tgb.cc
r410ea0f rdb83bf 40 40 static omBin lm_bin = NULL; 41 41 42 static void 43 simplify_poly (poly p, ring r) 42 static void simplify_poly (poly p, ring r) 44 43 { 45 44 assume (r == currRing); 46 if 45 if(!rField_is_Zp (r)) 47 46 { 48 47 p_Cleardenom (p, r); … … 55 54 //static const BOOLEAN up_to_radical=TRUE; 56 55 57 int 58 slim_nsize (number n, ring r) 59 { 60 if (rField_is_Zp (r)) 56 int slim_nsize (number n, ring r) 57 { 58 if(rField_is_Zp (r)) 61 59 { 62 60 return 1; 63 61 } 64 if 62 if(rField_is_Q (r)) 65 63 { 66 64 return QlogSize (n); … … 72 70 } 73 71 74 static BOOLEAN 75 monomial_root (poly m, ring r) 72 static BOOLEAN monomial_root (poly m, ring r) 76 73 { 77 74 BOOLEAN changed = FALSE; 78 75 int i; 79 for 76 for(i = 1; i <= rVar (r); i++) 80 77 { 81 78 int e = p_GetExp (m, i, r); 82 if 79 if(e > 1) 83 80 { 84 81 p_SetExp (m, i, 1, r); … … 86 83 } 87 84 } 88 if 85 if(changed) 89 86 { 90 87 p_Setm (m, r); … … 93 90 } 94 91 95 static BOOLEAN 96 polynomial_root (poly h, ring r) 92 static BOOLEAN polynomial_root (poly h, ring r) 97 93 { 98 94 poly got = gcd_of_terms (h, r); 99 95 BOOLEAN changed = FALSE; 100 if 96 if((got != NULL) && (TEST_V_UPTORADICAL)) 101 97 { 102 98 poly copy = p_Copy (got, r); 103 99 //p_wrp(got,c->r); 104 100 changed = monomial_root (got, r); 105 if 101 if(changed) 106 102 { 107 103 poly div_by = pDivide (copy, got); 108 104 poly iter = h; 109 while 110 { 111 112 105 while(iter) 106 { 107 pExpVectorSub (iter, div_by); 108 pIter (iter); 113 109 } 114 110 p_Delete (&div_by, r); 115 if 116 111 if(TEST_OPT_PROT) 112 PrintS ("U"); 117 113 } 118 114 p_Delete (©, r); … … 122 118 } 123 119 124 static inline poly 125 p_Init_Special (const ring r) 120 static inline poly p_Init_Special (const ring r) 126 121 { 127 122 return p_Init (r, lm_bin); 128 123 } 129 124 130 static inline poly 131 pOne_Special (const ring r = currRing) 125 static inline poly pOne_Special (const ring r = currRing) 132 126 { 133 127 poly rc = p_Init_Special (r); … … 147 141 #ifdef LEN_VAR1 148 142 // erste Variante: Laenge: Anzahl der Monome 149 static inline int 150 pSLength (poly p, int l) 143 static inline int pSLength (poly p, int l) 151 144 { 152 145 return l; 153 146 } 154 147 155 static inline int 156 kSBucketLength (kBucket * bucket, poly lm) 148 static inline int kSBucketLength (kBucket * bucket, poly lm) 157 149 { 158 150 return bucket_guess (bucket); … … 162 154 #ifdef LEN_VAR2 163 155 // 2. Variante: Laenge: Platz fuer die Koeff. 164 int 165 pSLength (poly p, int l) 156 int pSLength (poly p, int l) 166 157 { 167 158 int s = 0; 168 while 159 while(p != NULL) 169 160 { 170 161 s += nSize (pGetCoeff (p)); … … 174 165 } 175 166 176 int 177 kSBucketLength (kBucket * b, poly lm) 167 int kSBucketLength (kBucket * b, poly lm) 178 168 { 179 169 int s = 0; 180 170 int i; 181 for 171 for(i = MAX_BUCKET; i >= 0; i--) 182 172 { 183 173 s += pSLength (b->buckets[i], 0); … … 187 177 #endif 188 178 189 int 190 QlogSize (number n) 191 { 192 if (SR_HDL (n) & SR_INT) 179 int QlogSize (number n) 180 { 181 if(SR_HDL (n) & SR_INT) 193 182 { 194 183 long i = SR_TO_INT (n); 195 if 184 if(i == 0) 196 185 return 0; 197 186 … … 200 189 int r = 0; 201 190 202 while 191 while(v >>= 1) 203 192 { 204 193 r++; … … 211 200 212 201 #ifdef LEN_VAR3 213 static inline wlen_type 214 pSLength (poly p, int l) 202 static inline wlen_type pSLength (poly p, int l) 215 203 { 216 204 wlen_type c; 217 205 number coef = pGetCoeff (p); 218 if 206 if(rField_is_Q (currRing)) 219 207 { 220 208 c = QlogSize (coef); … … 222 210 else 223 211 c = nSize (coef); 224 if (!(TEST_V_COEFSTRAT)) 212 if(!(TEST_V_COEFSTRAT)) 213 { 225 214 return (wlen_type) c *(wlen_type) l /*pLength(p) */ ; 215 } 226 216 else 227 217 { … … 234 224 235 225 //! TODO CoefBuckets bercksichtigen 236 wlen_type 237 kSBucketLength (kBucket * b, poly lm = NULL) 226 wlen_type kSBucketLength (kBucket * b, poly lm = NULL) 238 227 { 239 228 int s = 0; 240 229 wlen_type c; 241 230 number coef; 242 if 231 if(lm == NULL) 243 232 coef = pGetCoeff (kBucketGetLm (b)); 244 233 //c=nSize(pGetCoeff(kBucketGetLm(b))); … … 246 235 coef = pGetCoeff (lm); 247 236 //c=nSize(pGetCoeff(lm)); 248 if 237 if(rField_is_Q (currRing)) 249 238 { 250 239 c = QlogSize (coef); … … 254 243 255 244 int i; 256 for 245 for(i = b->buckets_used; i >= 0; i--) 257 246 { 258 247 assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL)); … … 261 250 #ifdef HAVE_COEF_BUCKETS 262 251 assume (b->buckets[0] == kBucketGetLm (b)); 263 if 264 { 265 if 252 if(b->coef[0] != NULL) 253 { 254 if(rField_is_Q (currRing)) 266 255 { 267 256 int modifier = QlogSize (pGetCoeff (b->coef[0])); … … 275 264 } 276 265 #endif 277 if 266 if(!(TEST_V_COEFSTRAT)) 278 267 { 279 268 return s * c; … … 289 278 #endif 290 279 #ifdef LEN_VAR5 291 static inline wlen_type 292 pSLength (poly p, int l) 280 static inline wlen_type pSLength (poly p, int l) 293 281 { 294 282 int c; 295 283 number coef = pGetCoeff (p); 296 if 284 if(rField_is_Q (currRing)) 297 285 { 298 286 c = QlogSize (coef); … … 309 297 310 298 //! TODO CoefBuckets bercksichtigen 311 wlen_type 312 kSBucketLength (kBucket * b, poly lm = NULL) 299 wlen_type kSBucketLength (kBucket * b, poly lm = NULL) 313 300 { 314 301 wlen_type s = 0; 315 302 int c; 316 303 number coef; 317 if 304 if(lm == NULL) 318 305 coef = pGetCoeff (kBucketGetLm (b)); 319 306 //c=nSize(pGetCoeff(kBucketGetLm(b))); … … 321 308 coef = pGetCoeff (lm); 322 309 //c=nSize(pGetCoeff(lm)); 323 if 310 if(rField_is_Q (currRing)) 324 311 { 325 312 c = QlogSize (coef); … … 329 316 330 317 int i; 331 for 318 for(i = b->buckets_used; i >= 0; i--) 332 319 { 333 320 assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL)); … … 336 323 #ifdef HAVE_COEF_BUCKETS 337 324 assume (b->buckets[0] == kBucketGetLm (b)); 338 if 339 { 340 if 325 if(b->coef[0] != NULL) 326 { 327 if(rField_is_Q (currRing)) 341 328 { 342 329 int modifier = QlogSize (pGetCoeff (b->coef[0])); … … 359 346 #ifdef LEN_VAR4 360 347 // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.) 361 int 362 pSLength (poly p, int l) 348 int pSLength (poly p, int l) 363 349 { 364 350 int s = 1; 365 351 int c = nSize (pGetCoeff (p)); 366 352 pIter (p); 367 while 353 while(p != NULL) 368 354 { 369 355 s += nSize (pGetCoeff (p)); … … 373 359 } 374 360 375 int 376 kSBucketLength (kBucket * b) 361 int kSBucketLength (kBucket * b) 377 362 { 378 363 int s = 1; 379 364 int c = nSize (pGetCoeff (kBucketGetLm (b))); 380 365 int i; 381 for 382 { 383 if 366 for(i = MAX_BUCKET; i > 0; i--) 367 { 368 if(b->buckets[i] == NULL) 384 369 continue; 385 370 s += pSLength (b->buckets[i], 0); … … 389 374 #endif 390 375 //BUG/TODO this stuff will fail on internal Schreyer orderings 391 static BOOLEAN 392 elength_is_normal_length (poly p, slimgb_alg * c) 376 static BOOLEAN elength_is_normal_length (poly p, slimgb_alg * c) 393 377 { 394 378 ring r = c->r; 395 if 379 if(p_GetComp (p, r) != 0) 396 380 return FALSE; 397 if 381 if(c->lastDpBlockStart <= pVariables) 398 382 { 399 383 int i; 400 for 401 { 402 if 403 { 404 405 } 406 } 407 if 384 for(i = 1; i < c->lastDpBlockStart; i++) 385 { 386 if(p_GetExp (p, i, r) != 0) 387 { 388 break; 389 } 390 } 391 if(i >= c->lastDpBlockStart) 408 392 { 409 393 //wrp(p); … … 418 402 } 419 403 420 static BOOLEAN 421 lies_in_last_dp_block (poly p, slimgb_alg * c) 404 static BOOLEAN lies_in_last_dp_block (poly p, slimgb_alg * c) 422 405 { 423 406 ring r = c->r; 424 if 407 if(p_GetComp (p, r) != 0) 425 408 return FALSE; 426 if 409 if(c->lastDpBlockStart <= pVariables) 427 410 { 428 411 int i; 429 for 430 { 431 if 432 { 433 434 } 435 } 436 if 412 for(i = 1; i < c->lastDpBlockStart; i++) 413 { 414 if(p_GetExp (p, i, r) != 0) 415 { 416 break; 417 } 418 } 419 if(i >= c->lastDpBlockStart) 437 420 { 438 421 //wrp(p); … … 447 430 } 448 431 449 static int 450 get_last_dp_block_start (ring r) 432 static int get_last_dp_block_start (ring r) 451 433 { 452 434 //ring r=c->r; 453 435 int last_block; 454 436 455 if 437 if(rRing_has_CompLastBlock (r)) 456 438 { 457 439 last_block = rBlocks (r) - 3; … … 462 444 } 463 445 assume (last_block >= 0); 464 if 446 if(r->order[last_block] == ringorder_dp) 465 447 return r->block0[last_block]; 466 448 return pVariables + 1; 467 449 } 468 450 469 static wlen_type 470 do_pELength (poly p, slimgb_alg * c, int dlm = -1) 471 { 472 if (p == NULL) 451 static wlen_type do_pELength (poly p, slimgb_alg * c, int dlm = -1) 452 { 453 if(p == NULL) 473 454 return 0; 474 455 wlen_type s = 0; 475 456 poly pi = p; 476 if 457 if(dlm < 0) 477 458 { 478 459 dlm = c->pTotaldegree (p); … … 481 462 } 482 463 483 while 464 while(pi) 484 465 { 485 466 int d = c->pTotaldegree (pi); 486 if 467 if(d > dlm) 487 468 s += 1 + d - dlm; 488 469 else … … 493 474 } 494 475 495 wlen_type 496 pELength (poly p, slimgb_alg * c, ring r) 497 { 498 if (p == NULL) 476 wlen_type pELength (poly p, slimgb_alg * c, ring r) 477 { 478 if(p == NULL) 499 479 return 0; 500 480 wlen_type s = 0; … … 505 485 pi = p->next; 506 486 507 while 487 while(pi) 508 488 { 509 489 int d = c->pTotaldegree (pi); 510 if 490 if(d > dlm) 511 491 s += 1 + d - dlm; 512 492 else … … 517 497 } 518 498 519 wlen_type 520 kEBucketLength (kBucket * b, poly lm, int sugar, slimgb_alg * ca) 499 wlen_type kEBucketLength (kBucket * b, poly lm, int sugar, slimgb_alg * ca) 521 500 { 522 501 wlen_type s = 0; 523 if 502 if(lm == NULL) 524 503 { 525 504 lm = kBucketGetLm (b); 526 505 } 527 if 506 if(lm == NULL) 528 507 return 0; 529 if 508 if(elength_is_normal_length (lm, ca)) 530 509 { 531 510 return bucket_guess (b); … … 540 519 //int d=pTotaldegree(lm,ca->r); 541 520 int i; 542 for 543 { 544 if 521 for(i = b->buckets_used; i >= 0; i--) 522 { 523 if(b->buckets[i] == NULL) 545 524 continue; 546 525 547 if 548 526 if((ca->pTotaldegree (b->buckets[i]) <= d) 527 && (elength_is_normal_length (b->buckets[i], ca))) 549 528 { 550 529 s += b->buckets_length[i]; … … 559 538 } 560 539 561 static inline int 562 pELength (poly p, slimgb_alg * c, int l) 563 { 564 if (p == NULL) 540 static inline int pELength (poly p, slimgb_alg * c, int l) 541 { 542 if(p == NULL) 565 543 return 0; 566 if 544 if((l > 0) && (elength_is_normal_length (p, c))) 567 545 return l; 568 546 return do_pELength (p, c); 569 547 } 570 548 571 static inline wlen_type 572 pQuality (poly p, slimgb_alg * c, int l = -1) 573 { 574 if (l < 0) 549 static inline wlen_type pQuality (poly p, slimgb_alg * c, int l = -1) 550 { 551 if(l < 0) 575 552 l = pLength (p); 576 if 577 { 578 if 553 if(c->isDifficultField) 554 { 555 if(c->eliminationProblem) 579 556 { 580 557 wlen_type cs; 581 558 number coef = pGetCoeff (p); 582 if 583 { 584 559 if(rField_is_Q (currRing)) 560 { 561 cs = QlogSize (coef); 585 562 } 586 563 else 587 564 cs = nSize (coef); 588 565 wlen_type erg = cs; 589 if 590 566 if(TEST_V_COEFSTRAT) 567 erg *= cs; 591 568 //erg*=cs;//for quadratic 592 569 erg *= pELength (p, c, l); … … 600 577 return r; 601 578 } 602 if 579 if(c->eliminationProblem) 603 580 return pELength (p, c, l); 604 581 return l; 605 582 } 606 583 607 static inline int 608 pTotaldegree_full (poly p) 584 static inline int pTotaldegree_full (poly p) 609 585 { 610 586 int r = 0; 611 while 587 while(p) 612 588 { 613 589 int d = pTotaldegree (p); … … 618 594 } 619 595 620 wlen_type 621 red_object::guess_quality (slimgb_alg * c) 596 wlen_type red_object::guess_quality (slimgb_alg * c) 622 597 { 623 598 //works at the moment only for lenvar 1, because in different 624 599 //case, you have to look on coefs 625 600 wlen_type s = 0; 626 if 601 if(c->isDifficultField) 627 602 { 628 603 //s=kSBucketLength(bucket,this->p); 629 if 604 if(c->eliminationProblem) 630 605 { 631 606 wlen_type cs; … … 636 611 637 612 //c=nSize(pGetCoeff(lm)); 638 if 639 { 640 613 if(rField_is_Q (currRing)) 614 { 615 cs = QlogSize (coef); 641 616 } 642 617 else 643 618 cs = nSize (coef); 644 619 #ifdef HAVE_COEF_BUCKETS 645 if 646 { 647 if(rField_is_Q (currRing))648 649 650 651 652 653 654 655 656 620 if(bucket->coef[0] != NULL) 621 { 622 if(rField_is_Q (currRing)) 623 { 624 int modifier = QlogSize (pGetCoeff (bucket->coef[0])); 625 cs += modifier; 626 } 627 else 628 { 629 int modifier = nSize (pGetCoeff (bucket->coef[0])); 630 cs *= modifier; 631 } 657 632 } 658 633 #endif … … 661 636 //erg*=cs;//for quadratic 662 637 erg *= cs; 663 if 664 638 if(TEST_V_COEFSTRAT) 639 erg *= cs; 665 640 //return cs*kEBucketLength(this->bucket,this->p,c); 666 641 return erg; … … 670 645 else 671 646 { 672 if 647 if(c->eliminationProblem) 673 648 //if (false) 674 649 s = kEBucketLength (this->bucket, this->p, this->sugar, c); … … 679 654 } 680 655 681 #if 0 //currently unused 682 static void 683 finalize_reduction_step (reduction_step * r) 656 #if 0 //currently unused 657 static void finalize_reduction_step (reduction_step * r) 684 658 { 685 659 delete r; 686 660 } 687 661 #endif 688 #if 0 //currently unused 689 static int 690 LObject_better_gen (const void *ap, const void *bp) 662 #if 0 //currently unused 663 static int LObject_better_gen (const void *ap, const void *bp) 691 664 { 692 665 LObject *a = *(LObject **) ap; … … 695 668 } 696 669 #endif 697 static int 698 red_object_better_gen (const void *ap, const void *bp) 670 static int red_object_better_gen (const void *ap, const void *bp) 699 671 { 700 672 return (pLmCmp (((red_object *) ap)->p, ((red_object *) bp)->p)); 701 673 } 702 674 703 #if 0 //currently unused 704 static int 705 pLmCmp_func_inverted (const void *ap1, const void *ap2) 675 #if 0 //currently unused 676 static int pLmCmp_func_inverted (const void *ap1, const void *ap2) 706 677 { 707 678 poly p1, p2; … … 712 683 #endif 713 684 714 int 715 tgb_pair_better_gen2 (const void *ap, const void *bp) 685 int tgb_pair_better_gen2 (const void *ap, const void *bp) 716 686 { 717 687 return (-tgb_pair_better_gen (ap, bp)); 718 688 } 719 689 720 int 721 kFindDivisibleByInS_easy (kStrategy strat, const red_object & obj) 690 int kFindDivisibleByInS_easy (kStrategy strat, const red_object & obj) 722 691 { 723 692 int i; 724 693 long not_sev = ~obj.sev; 725 694 poly p = obj.p; 726 for 727 { 728 if 695 for(i = 0; i <= strat->sl; i++) 696 { 697 if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev)) 729 698 return i; 730 699 } … … 732 701 } 733 702 734 int 735 kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev) 703 int kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev) 736 704 { 737 705 int i; 738 706 long not_sev = ~sev; 739 for 740 { 741 if 707 for(i = 0; i <= strat->sl; i++) 708 { 709 if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev)) 742 710 return i; 743 711 } … … 747 715 static int 748 716 posInPairs (sorted_pair_node ** p, int pn, sorted_pair_node * qe, 749 750 { 751 if 717 slimgb_alg * c, int an = 0) 718 { 719 if(pn == 0) 752 720 return 0; 753 721 … … 757 725 int en = length; 758 726 759 if 727 if(pair_better (qe, p[en], c)) 760 728 return length + 1; 761 729 762 while 730 while(1) 763 731 { 764 732 //if (an >= en-1) 765 if 766 { 767 if 768 733 if(en - 1 <= an) 734 { 735 if(pair_better (p[an], qe, c)) 736 return an; 769 737 return en; 770 738 } 771 739 i = (an + en) / 2; 772 if 740 if(pair_better (p[i], qe, c)) 773 741 en = i; 774 742 else … … 777 745 } 778 746 779 static BOOLEAN 780 ascending (int *i, int top) 781 { 782 if (top < 1) 747 static BOOLEAN ascending (int *i, int top) 748 { 749 if(top < 1) 783 750 return TRUE; 784 if 751 if(i[top] < i[top - 1]) 785 752 return FALSE; 786 753 return ascending (i, top - 1); 787 754 } 788 755 789 sorted_pair_node ** 790 spn_merge (sorted_pair_node ** p, int pn, sorted_pair_node ** q, int qn, 791 slimgb_alg * c) 756 sorted_pair_node **spn_merge (sorted_pair_node ** p, int pn, 757 sorted_pair_node ** q, int qn, slimgb_alg * c) 792 758 { 793 759 int i; … … 807 773 // } 808 774 int lastpos = 0; 809 for 775 for(i = 0; i < qn; i++) 810 776 { 811 777 lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos - 1, 0)); … … 813 779 a[i] = lastpos; 814 780 } 815 if 781 if((pn + qn) > c->max_pairs) 816 782 { 817 783 p = 818 784 (sorted_pair_node **) omrealloc (p, 819 820 821 785 2 * (pn + 786 qn) * 787 sizeof (sorted_pair_node *)); 822 788 c->max_pairs = 2 * (pn + qn); 823 789 } 824 for 790 for(i = qn - 1; i >= 0; i--) 825 791 { 826 792 size_t size; 827 if 793 if(qn - 1 > i) 828 794 size = (a[i + 1] - a[i]) * sizeof (sorted_pair_node *); 829 795 else 830 size = (pn - a[i]) * sizeof (sorted_pair_node *); 796 size = (pn - a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0 831 797 memmove (p + a[i] + (1 + i), p + a[i], size); 832 798 p[a[i] + i] = q[i]; … … 842 808 poly p2 = c->S->m[pos2]; 843 809 844 if 810 if(pGetComp (p1) > 0 || pGetComp (p2) > 0) 845 811 return FALSE; 846 812 int i = 1; … … 849 815 poly gcd2 = c->gcd_of_terms[pos2]; 850 816 851 if 852 { 853 gcd1->next = gcd2; 817 if((gcd1 != NULL) && (gcd2 != NULL)) 818 { 819 gcd1->next = gcd2; //may ordered incorrect 854 820 m = gcd_of_terms (gcd1, c->r); 855 821 gcd1->next = NULL; 856 822 } 857 if 823 if(m == NULL) 858 824 { 859 825 loop 860 826 { 861 if 862 863 if 864 { 865 866 827 if(pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i)) 828 return FALSE; 829 if(i == pVariables) 830 { 831 //PrintS("trivial"); 832 return TRUE; 867 833 } 868 834 i++; … … 873 839 loop 874 840 { 875 if 876 877 { 878 879 880 } 881 if 882 { 883 884 885 841 if(pGetExp (p1, i) - pGetExp (m, i) + pGetExp (p2, i) > 842 pGetExp (bound, i)) 843 { 844 pDelete (&m); 845 return FALSE; 846 } 847 if(i == pVariables) 848 { 849 pDelete (&m); 850 //PrintS("trivial"); 851 return TRUE; 886 852 } 887 853 i++; … … 891 857 892 858 //! returns position sets w as weight 893 int 894 find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c) 859 int find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c) 895 860 { 896 861 int best = l; 897 862 int i; 898 863 w = r[l].guess_quality (c); 899 for 864 for(i = l + 1; i <= u; i++) 900 865 { 901 866 wlen_type w2 = r[i].guess_quality (c); 902 if 867 if(w2 < w) 903 868 { 904 869 w = w2; … … 909 874 } 910 875 911 void 912 red_object::canonicalize () 876 void red_object::canonicalize () 913 877 { 914 878 kBucketCanonicalize (bucket); 915 879 } 916 880 917 BOOLEAN 918 good_has_t_rep (int i, int j, slimgb_alg * c) 881 BOOLEAN good_has_t_rep (int i, int j, slimgb_alg * c) 919 882 { 920 883 assume (i >= 0); 921 884 assume (j >= 0); 922 if 885 if(has_t_rep (i, j, c)) 923 886 return TRUE; 924 887 //poly lm=pOne(); … … 933 896 //p_Delete(&lm,c->r); 934 897 935 for 936 { 937 if 898 for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++) 899 { 900 if(i_con[n] == j) 938 901 { 939 902 now_t_rep (i, j, c); … … 947 910 } 948 911 949 BOOLEAN 950 lenS_correct (kStrategy strat) 912 BOOLEAN lenS_correct (kStrategy strat) 951 913 { 952 914 int i; 953 for 954 { 955 if 915 for(i = 0; i <= strat->sl; i++) 916 { 917 if(strat->lenS[i] != pLength (strat->S[i])) 956 918 return FALSE; 957 919 } … … 960 922 961 923 962 static void 963 cleanS (kStrategy strat, slimgb_alg * c) 924 static void cleanS (kStrategy strat, slimgb_alg * c) 964 925 { 965 926 int i = 0; 966 927 LObject P; 967 while 928 while(i <= strat->sl) 968 929 { 969 930 P.p = strat->S[i]; … … 971 932 //int dummy=strat->sl; 972 933 //if(kFindDivisibleByInS(strat,&dummy,&P)!=i) 973 if 934 if(kFindDivisibleByInS_easy (strat, P.p, P.sev) != i) 974 935 { 975 936 deleteInS (i, strat); … … 977 938 BOOLEAN found = FALSE; 978 939 int j; 979 for 980 { 981 if(c->S->m[j] == P.p)982 983 984 985 986 } 987 if 988 940 for(j = 0; j < c->n; j++) 941 { 942 if(c->S->m[j] == P.p) 943 { 944 found = TRUE; 945 break; 946 } 947 } 948 if(!found) 949 pDelete (&P.p); 989 950 //remember additional reductors 990 951 } … … 994 955 } 995 956 996 static int 997 bucket_guess (kBucket * bucket) 957 static int bucket_guess (kBucket * bucket) 998 958 { 999 959 int sum = 0; 1000 960 int i; 1001 for 1002 { 1003 if 961 for(i = bucket->buckets_used; i >= 0; i--) 962 { 963 if(bucket->buckets[i]) 1004 964 sum += bucket->buckets_length[i]; 1005 965 } … … 1009 969 static int 1010 970 add_to_reductors (slimgb_alg * c, poly h, int len, int ecart, 1011 971 BOOLEAN simplified) 1012 972 { 1013 973 //inDebug(h); … … 1023 983 memset (&P, 0, sizeof (P)); 1024 984 P.tailRing = c->r; 1025 P.p = h; 985 P.p = h; /*p_Copy(h,c->r); */ 1026 986 P.ecart = ecart; 1027 987 P.FDeg = pFDeg (P.p, c->r); 1028 if 1029 { 1030 if 988 if(!(simplified)) 989 { 990 if(!rField_is_Zp (c->r)) 1031 991 { 1032 992 p_Cleardenom (P.p, c->r); … … 1044 1004 c->strat->lenS[i] = len; 1045 1005 assume (pLength (c->strat->S[i]) == c->strat->lenS[i]); 1046 if 1006 if(c->strat->lenSw != NULL) 1047 1007 c->strat->lenSw[i] = pq; 1048 1008 … … 1050 1010 } 1051 1011 1052 static void 1053 length_one_crit (slimgb_alg * c, int pos, int len) 1054 { 1055 if (c->nc) 1012 static void length_one_crit (slimgb_alg * c, int pos, int len) 1013 { 1014 if(c->nc) 1056 1015 return; 1057 if 1016 if(len == 1) 1058 1017 { 1059 1018 int i; 1060 for 1061 { 1062 if 1063 1064 } 1065 for 1066 { 1067 if 1068 1069 } 1070 if 1019 for(i = 0; i < pos; i++) 1020 { 1021 if(c->lengths[i] == 1) 1022 c->states[pos][i] = HASTREP; 1023 } 1024 for(i = pos + 1; i < c->n; i++) 1025 { 1026 if(c->lengths[i] == 1) 1027 c->states[i][pos] = HASTREP; 1028 } 1029 if(!c->nc) 1071 1030 shorten_tails (c, c->S->m[pos]); 1072 1031 } 1073 1032 } 1074 1033 1075 static void 1076 move_forward_in_S (int old_pos, int new_pos, kStrategy strat) 1034 static void move_forward_in_S (int old_pos, int new_pos, kStrategy strat) 1077 1035 { 1078 1036 assume (old_pos >= new_pos); … … 1084 1042 assume (length == pLength (strat->S[old_pos])); 1085 1043 wlen_type length_w; 1086 if 1044 if(strat->lenSw != NULL) 1087 1045 length_w = strat->lenSw[old_pos]; 1088 1046 int i; 1089 for 1047 for(i = old_pos; i > new_pos; i--) 1090 1048 { 1091 1049 strat->S[i] = strat->S[i - 1]; … … 1094 1052 strat->S_2_R[i] = strat->S_2_R[i - 1]; 1095 1053 } 1096 if 1097 for 1054 if(strat->lenS != NULL) 1055 for(i = old_pos; i > new_pos; i--) 1098 1056 strat->lenS[i] = strat->lenS[i - 1]; 1099 if 1100 for 1057 if(strat->lenSw != NULL) 1058 for(i = old_pos; i > new_pos; i--) 1101 1059 strat->lenSw[i] = strat->lenSw[i - 1]; 1102 1060 … … 1106 1064 strat->S_2_R[new_pos] = s_2_r; 1107 1065 strat->lenS[new_pos] = length; 1108 if 1066 if(strat->lenSw != NULL) 1109 1067 strat->lenSw[new_pos] = length_w; 1110 1068 //assume(lenS_correct(strat)); 1111 1069 } 1112 1070 1113 static void 1114 move_backward_in_S (int old_pos, int new_pos, kStrategy strat) 1071 static void move_backward_in_S (int old_pos, int new_pos, kStrategy strat) 1115 1072 { 1116 1073 assume (old_pos <= new_pos); … … 1122 1079 assume (length == pLength (strat->S[old_pos])); 1123 1080 wlen_type length_w; 1124 if 1081 if(strat->lenSw != NULL) 1125 1082 length_w = strat->lenSw[old_pos]; 1126 1083 int i; 1127 for 1084 for(i = old_pos; i < new_pos; i++) 1128 1085 { 1129 1086 strat->S[i] = strat->S[i + 1]; … … 1132 1089 strat->S_2_R[i] = strat->S_2_R[i + 1]; 1133 1090 } 1134 if 1135 for 1091 if(strat->lenS != NULL) 1092 for(i = old_pos; i < new_pos; i++) 1136 1093 strat->lenS[i] = strat->lenS[i + 1]; 1137 if 1138 for 1094 if(strat->lenSw != NULL) 1095 for(i = old_pos; i < new_pos; i++) 1139 1096 strat->lenSw[i] = strat->lenSw[i + 1]; 1140 1097 … … 1144 1101 strat->S_2_R[new_pos] = s_2_r; 1145 1102 strat->lenS[new_pos] = length; 1146 if 1103 if(strat->lenSw != NULL) 1147 1104 strat->lenSw[new_pos] = length_w; 1148 1105 //assume(lenS_correct(strat)); 1149 1106 } 1150 1107 1151 static int * 1152 make_connections (int from, int to, poly bound, slimgb_alg * c) 1108 static int *make_connections (int from, int to, poly bound, slimgb_alg * c) 1153 1109 { 1154 1110 ideal I = c->S; … … 1166 1122 int pos; 1167 1123 1168 while 1169 { 1170 if 1124 while(TRUE) 1125 { 1126 if((con_checked < connected_length) && (not_yet_found > 0)) 1171 1127 { 1172 1128 pos = connected[con_checked]; 1173 for 1174 { 1175 if(cans[i] < 0)1176 1177 1178 if((has_t_rep (pos, cans[i], c))1179 1180 1181 1182 1183 1184 1185 1186 1187 if(connected[connected_length - 1] == to)1188 1189 if(connected_length < c->n)1190 1191 1192 1193 1194 1195 1196 1129 for(int i = 0; i < cans_length; i++) 1130 { 1131 if(cans[i] < 0) 1132 continue; 1133 //FIXME: triv. syz. does not hold on noncommutative, check it for modules 1134 if((has_t_rep (pos, cans[i], c)) 1135 || ((!rIsPluralRing (c->r)) 1136 && (trivial_syzygie (pos, cans[i], bound, c)))) 1137 { 1138 connected[connected_length] = cans[i]; 1139 connected_length++; 1140 cans[i] = -1; 1141 --not_yet_found; 1142 1143 if(connected[connected_length - 1] == to) 1144 { 1145 if(connected_length < c->n) 1146 { 1147 connected[connected_length] = -1; 1148 } 1149 omfree (cans); 1150 return connected; 1151 } 1152 } 1197 1153 } 1198 1154 con_checked++; … … 1200 1156 else 1201 1157 { 1202 for 1203 { 1204 if(last_cans_pos == c->n)1205 1206 if(connected_length < c->n)1207 1208 1209 1210 1211 1212 1213 if((last_cans_pos == from) || (last_cans_pos == to))1214 1215 if(p_LmShortDivisibleBy1216 1217 1218 1219 1220 1221 1222 1158 for(last_cans_pos++; last_cans_pos <= c->n; last_cans_pos++) 1159 { 1160 if(last_cans_pos == c->n) 1161 { 1162 if(connected_length < c->n) 1163 { 1164 connected[connected_length] = -1; 1165 } 1166 omfree (cans); 1167 return connected; 1168 } 1169 if((last_cans_pos == from) || (last_cans_pos == to)) 1170 continue; 1171 if(p_LmShortDivisibleBy 1172 (I->m[last_cans_pos], c->short_Exps[last_cans_pos], bound, 1173 neg_bounds_short, c->r)) 1174 { 1175 cans[cans_length] = last_cans_pos; 1176 cans_length++; 1177 break; 1178 } 1223 1179 } 1224 1180 not_yet_found++; 1225 for 1226 { 1227 if(has_t_rep (connected[i], last_cans_pos, c))1228 1229 1230 1231 1232 1233 if(connected[connected_length - 1] == to)1234 1235 if(connected_length < c->n)1236 1237 1238 1239 1240 1241 1242 1243 1244 } 1245 } 1246 } 1247 if 1181 for(int i = 0; i < con_checked; i++) 1182 { 1183 if(has_t_rep (connected[i], last_cans_pos, c)) 1184 { 1185 connected[connected_length] = last_cans_pos; 1186 connected_length++; 1187 cans[cans_length - 1] = -1; 1188 --not_yet_found; 1189 if(connected[connected_length - 1] == to) 1190 { 1191 if(connected_length < c->n) 1192 { 1193 connected[connected_length] = -1; 1194 } 1195 omfree (cans); 1196 return connected; 1197 } 1198 break; 1199 } 1200 } 1201 } 1202 } 1203 if(connected_length < c->n) 1248 1204 { 1249 1205 connected[connected_length] = -1; … … 1254 1210 1255 1211 #ifdef HEAD_BIN 1256 static inline poly 1257 p_MoveHead (poly p, omBin b) 1212 static inline poly p_MoveHead (poly p, omBin b) 1258 1213 { 1259 1214 poly np; … … 1265 1220 #endif 1266 1221 1267 static void 1268 replace_pair (int &i, int &j, slimgb_alg * c) 1269 { 1270 if (i < 0) 1222 static void replace_pair (int &i, int &j, slimgb_alg * c) 1223 { 1224 if(i < 0) 1271 1225 return; 1272 1226 c->soon_free = NULL; … … 1279 1233 int *i_con = make_connections (i, j, lm, c); 1280 1234 1281 for 1282 { 1283 if 1235 for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++) 1236 { 1237 if(i_con[n] == j) 1284 1238 { 1285 1239 now_t_rep (i, j, c); … … 1306 1260 1307 1261 p_Delete (&lm, c->r); 1308 if (c->T_deg_full)//Sugar1262 if(c->T_deg_full) //Sugar 1309 1263 { 1310 1264 int t_i = c->T_deg_full[i] - c->T_deg[i]; … … 1314 1268 } 1315 1269 1316 for 1317 { 1318 if 1270 for(int m = 0; ((m < c->n) && (i_con[m] >= 0)); m++) 1271 { 1272 if(c->T_deg_full != NULL) 1319 1273 { 1320 1274 int s1 = c->T_deg_full[i_con[m]] + syz_deg - c->T_deg[i_con[m]]; 1321 if 1322 1323 } 1324 if 1275 if(s1 > sugar) 1276 continue; 1277 } 1278 if(c->weighted_lengths[i_con[m]] < c->weighted_lengths[i]) 1325 1279 i = i_con[m]; 1326 1280 } 1327 for 1328 { 1329 if 1281 for(int m = 0; ((m < c->n) && (j_con[m] >= 0)); m++) 1282 { 1283 if(c->T_deg_full != NULL) 1330 1284 { 1331 1285 int s1 = c->T_deg_full[j_con[m]] + syz_deg - c->T_deg[j_con[m]]; 1332 if 1333 1334 } 1335 if 1286 if(s1 > sugar) 1287 continue; 1288 } 1289 if(c->weighted_lengths[j_con[m]] < c->weighted_lengths[j]) 1336 1290 j = j_con[m]; 1337 1291 } … … 1343 1297 } 1344 1298 1345 static void 1346 add_later (poly p, const char *prot, slimgb_alg * c) 1299 static void add_later (poly p, const char *prot, slimgb_alg * c) 1347 1300 { 1348 1301 int i = 0; 1349 1302 //check, if it is already in the queue 1350 1303 1351 while 1352 { 1353 if 1304 while(c->add_later->m[i] != NULL) 1305 { 1306 if(p_LmEqual (c->add_later->m[i], p, c->r)) 1354 1307 return; 1355 1308 i++; 1356 1309 } 1357 if 1310 if(TEST_OPT_PROT) 1358 1311 PrintS (prot); 1359 1312 c->add_later->m[i] = p; 1360 1313 } 1361 1314 1362 static int 1363 simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen) 1364 { 1365 if (strat->sl == -1) 1315 static int simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen) 1316 { 1317 if(strat->sl == -1) 1366 1318 return 0; 1367 if 1319 if(strat->lenSw) 1368 1320 return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat->lenSw, 1369 1321 strat->S); 1370 1322 return pos_helper (strat, p, len, strat->lenS, strat->S); 1371 1323 } … … 1379 1331 { 1380 1332 assume (p_sev == pGetShortExpVector (p)); 1381 if 1333 if(!pLmShortDivisibleBy (p, p_sev, strat->S[*at], ~strat->sevS[*at])) 1382 1334 return; 1383 if 1335 if(l >= strat->lenS[*at]) 1384 1336 return; 1385 if 1337 if(TEST_OPT_PROT) 1386 1338 PrintS ("!"); 1387 1339 mflush (); … … 1393 1345 } 1394 1346 1395 static int 1396 iq_crit (const void *ap, const void *bp) 1347 static int iq_crit (const void *ap, const void *bp) 1397 1348 { 1398 1349 sorted_pair_node *a = *((sorted_pair_node **) ap); … … 1401 1352 assume (b->i > b->j); 1402 1353 1403 if 1354 if(a->deg < b->deg) 1404 1355 return -1; 1405 if 1356 if(a->deg > b->deg) 1406 1357 return 1; 1407 1358 int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm); 1408 if 1359 if(comp != 0) 1409 1360 return comp; 1410 if 1361 if(a->expected_length < b->expected_length) 1411 1362 return -1; 1412 if 1363 if(a->expected_length > b->expected_length) 1413 1364 return 1; 1414 if 1365 if(a->j > b->j) 1415 1366 return 1; 1416 if 1367 if(a->j < b->j) 1417 1368 return -1; 1418 1369 return 0; 1419 1370 } 1420 1371 1421 static wlen_type 1422 coeff_mult_size_estimate (int s1, int s2, ring r) 1423 { 1424 if (rField_is_Q (r)) 1372 static wlen_type coeff_mult_size_estimate (int s1, int s2, ring r) 1373 { 1374 if(rField_is_Q (r)) 1425 1375 return s1 + s2; 1426 1376 else … … 1428 1378 } 1429 1379 1430 static wlen_type 1431 pair_weighted_length (int i, int j, slimgb_alg * c) 1432 { 1433 if ((c->isDifficultField) && (c->eliminationProblem)) 1380 static wlen_type pair_weighted_length (int i, int j, slimgb_alg * c) 1381 { 1382 if((c->isDifficultField) && (c->eliminationProblem)) 1434 1383 { 1435 1384 int c1 = slim_nsize (p_GetCoeff (c->S->m[i], c->r), c->r); … … 1448 1397 1449 1398 } 1450 if 1399 if(c->isDifficultField) 1451 1400 { 1452 1401 //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+ 1453 1402 // slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r); 1454 if 1403 if(!(TEST_V_COEFSTRAT)) 1455 1404 { 1456 1405 wlen_type cs = 1457 1458 1459 1460 1406 coeff_mult_size_estimate (slim_nsize 1407 (p_GetCoeff (c->S->m[i], c->r), c->r), 1408 slim_nsize (p_GetCoeff (c->S->m[j], c->r), 1409 c->r), c->r); 1461 1410 return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs; 1462 1411 } … … 1465 1414 1466 1415 wlen_type cs = 1467 1468 1469 1470 1416 coeff_mult_size_estimate (slim_nsize 1417 (p_GetCoeff (c->S->m[i], c->r), c->r), 1418 slim_nsize (p_GetCoeff (c->S->m[j], c->r), 1419 c->r), c->r); 1471 1420 cs *= cs; 1472 1421 return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs; 1473 1422 } 1474 1423 } 1475 if 1424 if(c->eliminationProblem) 1476 1425 { 1477 1426 … … 1482 1431 } 1483 1432 1484 sorted_pair_node ** 1485 add_to_basis_ideal_quotient (poly h, slimgb_alg * c,int *ip)1433 sorted_pair_node **add_to_basis_ideal_quotient (poly h, slimgb_alg * c, 1434 int *ip) 1486 1435 { 1487 1436 p_Test (h, c->r); 1488 1437 assume (h != NULL); 1489 1438 poly got = gcd_of_terms (h, c->r); 1490 if 1439 if((got != NULL) && (TEST_V_UPTORADICAL)) 1491 1440 { 1492 1441 poly copy = p_Copy (got, c->r); 1493 1442 //p_wrp(got,c->r); 1494 1443 BOOLEAN changed = monomial_root (got, c->r); 1495 if 1444 if(changed) 1496 1445 { 1497 1446 poly div_by = pDivide (copy, got); 1498 1447 poly iter = h; 1499 while 1500 { 1501 1502 1448 while(iter) 1449 { 1450 pExpVectorSub (iter, div_by); 1451 pIter (iter); 1503 1452 } 1504 1453 p_Delete (&div_by, c->r); … … 1519 1468 (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i); 1520 1469 int spc = 0; 1521 if 1470 if(c->n > c->array_lengths) 1522 1471 { 1523 1472 c->array_lengths = c->array_lengths * 2; … … 1542 1491 } 1543 1492 pEnlargeSet (&c->S->m, c->n - 1, 1); 1544 if 1493 if(c->T_deg_full) 1545 1494 ENLARGE (c->T_deg_full, int); 1546 1495 sugar = c->T_deg[i] = c->pTotaldegree (h); 1547 if 1496 if(c->T_deg_full) 1548 1497 { 1549 1498 sugar = c->T_deg_full[i] = c->pTotaldegree_full (h); … … 1559 1508 //necessary for correct weighted length 1560 1509 1561 if 1510 if(!rField_is_Zp (c->r)) 1562 1511 { 1563 1512 p_Cleardenom (h, c->r); … … 1579 1528 1580 1529 #else 1581 if 1530 if(i > 0) 1582 1531 c->states[i] = (char *) omalloc (i * sizeof (char)); 1583 1532 else … … 1590 1539 1591 1540 #undef ENLARGE 1592 if 1593 { 1594 for 1541 if(p_GetComp (h, currRing) <= c->syz_comp) 1542 { 1543 for(j = 0; j < i; j++) 1595 1544 { 1596 1545 … … 1600 1549 #endif 1601 1550 assume (p_LmDivisibleBy (c->S->m[i], c->S->m[j], c->r) == 1602 1603 1604 1605 if 1606 { 1607 1608 1609 1610 } 1611 else if 1612 { 1613 1614 } 1615 else if 1616 1551 p_LmShortDivisibleBy (c->S->m[i], c->short_Exps[i], c->S->m[j], 1552 ~(c->short_Exps[j]), c->r)); 1553 1554 if(_p_GetComp (c->S->m[i], c->r) != _p_GetComp (c->S->m[j], c->r)) 1555 { 1556 //c->states[i][j]=UNCALCULATED; 1557 //WARNUNG: be careful 1558 continue; 1559 } 1560 else if((!c->nc) && (c->lengths[i] == 1) && (c->lengths[j] == 1)) 1561 { 1562 c->states[i][j] = HASTREP; 1563 } 1564 else if(((!c->nc) || (c->is_homog && rIsSCA (c->r))) 1565 && (pHasNotCF (c->S->m[i], c->S->m[j]))) 1617 1566 // else if ((!(c->nc)) && (pHasNotCF(c->S->m[i],c->S->m[j]))) 1618 1567 { 1619 1620 1621 1568 c->easy_product_crit++; 1569 c->states[i][j] = HASTREP; 1570 continue; 1622 1571 } 1623 1572 else 1624 if(extended_product_criterion1625 1626 1627 { 1628 1629 1630 1573 if(extended_product_criterion 1574 (c->S->m[i], c->gcd_of_terms[i], c->S->m[j], c->gcd_of_terms[j], 1575 c)) 1576 { 1577 c->states[i][j] = HASTREP; 1578 c->extended_product_crit++; 1579 //PrintS("E"); 1631 1580 } 1632 1581 // if (c->states[i][j]==UNCALCULATED) 1633 1582 // { 1634 1583 1635 if 1636 { 1637 1638 1639 1584 if((TEST_V_FINDMONOM) && (!c->nc)) 1585 { 1586 //PrintS("COMMU"); 1587 // if (c->lengths[i]==c->lengths[j]) 1588 // { 1640 1589 // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); 1641 1590 // if (short_s==NULL) … … 1648 1597 // } 1649 1598 // } 1650 if(c->lengths[i] + c->lengths[j] == 3)1651 1652 1653 1654 1655 if(short_s == NULL)1656 1657 1658 1659 1660 1661 1662 if(TEST_V_UPTORADICAL)1663 1664 int iS = 1665 kFindDivisibleByInS_easy (c->strat,short_s,1666 p_GetShortExpVector (short_s,c->r));1667 if(iS < 0)1668 1669 1670 if(TRUE)1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 if(c->strat->lenS[iS] > 1)1681 1682 1683 if(TRUE)1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1599 if(c->lengths[i] + c->lengths[j] == 3) 1600 { 1601 1602 1603 poly short_s = ksCreateShortSpoly (c->S->m[i], c->S->m[j], c->r); 1604 if(short_s == NULL) 1605 { 1606 c->states[i][j] = HASTREP; 1607 } 1608 else 1609 { 1610 assume (pLength (short_s) == 1); 1611 if(TEST_V_UPTORADICAL) 1612 monomial_root (short_s, c->r); 1613 int iS = kFindDivisibleByInS_easy (c->strat, short_s, 1614 p_GetShortExpVector (short_s, 1615 c->r)); 1616 if(iS < 0) 1617 { 1618 //PrintS("N"); 1619 if(TRUE) 1620 { 1621 c->states[i][j] = HASTREP; 1622 add_later (short_s, "N", c); 1623 } 1624 else 1625 p_Delete (&short_s, currRing); 1626 } 1627 else 1628 { 1629 if(c->strat->lenS[iS] > 1) 1630 { 1631 //PrintS("O"); 1632 if(TRUE) 1633 { 1634 c->states[i][j] = HASTREP; 1635 add_later (short_s, "O", c); 1636 } 1637 else 1638 p_Delete (&short_s, currRing); 1639 } 1640 else 1641 p_Delete (&short_s, currRing); 1642 c->states[i][j] = HASTREP; 1643 } 1644 1645 1646 } 1647 } 1699 1648 } 1700 1649 // if (short_s) 1701 1650 // { 1702 1651 assume (spc <= j); 1703 sorted_pair_node *s = c->tmp_spn[spc]; 1652 sorted_pair_node *s = c->tmp_spn[spc]; //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1704 1653 s->i = si_max (i, j); 1705 1654 s->j = si_min (i, j); 1706 1655 assume (s->j == j); 1707 s->expected_length = pair_weighted_length (i, j, c); 1708 1709 poly lm = c->tmp_pair_lm[spc]; 1656 s->expected_length = pair_weighted_length (i, j, c); //c->lengths[i]+c->lengths[j]-2; 1657 1658 poly lm = c->tmp_pair_lm[spc]; //=pOne_Special(); 1710 1659 1711 1660 pLcm (c->S->m[i], c->S->m[j], lm); … … 1714 1663 s->deg = c->pTotaldegree (lm); 1715 1664 1716 if (c->T_deg_full)//Sugar1717 { 1718 1719 1720 1721 1665 if(c->T_deg_full) //Sugar 1666 { 1667 int t_i = c->T_deg_full[s->i] - c->T_deg[s->i]; 1668 int t_j = c->T_deg_full[s->j] - c->T_deg[s->j]; 1669 s->deg += si_max (t_i, t_j); 1670 //Print("\n max: %d\n",max(t_i,t_j)); 1722 1671 } 1723 1672 p_Test (lm, c->r); … … 1734 1683 //} 1735 1684 } 1736 } 1685 } //if syz_comp end 1737 1686 1738 1687 assume (spc <= i); … … 1744 1693 int spc_final = 0; 1745 1694 j = 0; 1746 while 1695 while(j < spc) 1747 1696 { 1748 1697 int lower = j; 1749 1698 int upper; 1750 1699 BOOLEAN has = FALSE; 1751 for 1752 { 1753 if 1754 { 1755 1756 } 1757 if 1758 1700 for(upper = lower + 1; upper < spc; upper++) 1701 { 1702 if(!pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm)) 1703 { 1704 break; 1705 } 1706 if(has_t_rep (nodes[upper]->i, nodes[upper]->j, c)) 1707 has = TRUE; 1759 1708 } 1760 1709 upper = upper - 1; 1761 1710 int z; 1762 1711 assume (spc_final <= j); 1763 for 1764 { 1765 if 1766 1767 { 1768 1769 1770 } 1771 } 1772 1773 if 1774 { 1775 for 1776 { 1777 1778 1779 1712 for(z = 0; z < spc_final; z++) 1713 { 1714 if(p_LmDivisibleBy 1715 (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->r)) 1716 { 1717 has = TRUE; 1718 break; 1719 } 1720 } 1721 1722 if(has) 1723 { 1724 for(; lower <= upper; lower++) 1725 { 1726 //free_sorted_pair_node(nodes[lower],c->r); 1727 //omfree(nodes[lower]); 1728 nodes[lower] = NULL; 1780 1729 } 1781 1730 j = upper + 1; … … 1787 1736 nodes[lower]->lcm_of_lm = pCopy (nodes[lower]->lcm_of_lm); 1788 1737 assume (_p_GetComp (c->S->m[nodes[lower]->i], c->r) == 1789 1738 _p_GetComp (c->S->m[nodes[lower]->j], c->r)); 1790 1739 nodes_final[spc_final] = 1791 1740 (sorted_pair_node *) omalloc (sizeof (sorted_pair_node)); 1792 1741 1793 1742 *(nodes_final[spc_final++]) = *(nodes[lower]); 1794 1743 //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1795 1744 nodes[lower] = NULL; 1796 for 1797 { 1798 1799 1800 1745 for(lower = lower + 1; lower <= upper; lower++) 1746 { 1747 // free_sorted_pair_node(nodes[lower],c->r); 1748 //omfree(nodes[lower]); 1749 nodes[lower] = NULL; 1801 1750 } 1802 1751 j = upper + 1; … … 1813 1762 add_to_reductors (c, h, c->lengths[c->n - 1], ecart, TRUE); 1814 1763 //i=posInS(c->strat,c->strat->sl,h,0 ecart); 1815 if 1816 { 1817 if 1764 if(!(c->nc)) 1765 { 1766 if(c->lengths[c->n - 1] == 1) 1818 1767 shorten_tails (c, c->S->m[c->n - 1]); 1819 1768 } … … 1822 1771 //for(i=c->strat->sl; i>0;i--) 1823 1772 // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i); 1824 if 1773 if(c->Rcounter > 50) 1825 1774 { 1826 1775 c->Rcounter = 0; … … 1831 1780 // for SCA: 1832 1781 // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg-1] 1833 if 1782 if(rIsSCA (c->r)) 1834 1783 { 1835 1784 const poly pNext = pNext (h); 1836 1785 1837 if 1786 if(pNext != NULL) 1838 1787 { 1839 1788 // for additional polynomials … … 1841 1790 const unsigned int m_iLastAltVar = scaLastAltVar (c->r); 1842 1791 1843 int N = 1844 m_iLastAltVar - m_iFirstAltVar + 1;// should be enough1792 int N = // c->r->N; 1793 m_iLastAltVar - m_iFirstAltVar + 1; // should be enough 1845 1794 // TODO: but we may also use got = gcd({m}_{m\in f}))! 1846 1795 1847 poly *array_arg = (poly *) omalloc (N * sizeof (poly)); 1796 poly *array_arg = (poly *) omalloc (N * sizeof (poly)); // ! 1848 1797 int j = 0; 1849 1798 1850 1799 1851 for 1852 1853 if (p_GetExp (h, v, c->r))// TODO: use 'got' here!1854 1855 1856 1857 poly p = sca_pp_Mult_xi_pp (v, pNext, c->r);// x_v * h;1858 1859 if (p != NULL)// if (x_v * h != 0)1860 1861 }// for all x_v | Ann(lm(h))1800 for(unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++) 1801 // for all x_v | Ann(lm(h)) 1802 if(p_GetExp (h, v, c->r)) // TODO: use 'got' here! 1803 { 1804 assume (p_GetExp (h, v, c->r) == 1); 1805 1806 poly p = sca_pp_Mult_xi_pp (v, pNext, c->r); // x_v * h; 1807 1808 if(p != NULL) // if (x_v * h != 0) 1809 array_arg[j++] = p; 1810 } // for all x_v | Ann(lm(h)) 1862 1811 1863 1812 c->introduceDelayedPairs (array_arg, j); 1864 1813 1865 omfree (array_arg); 1814 omfree (array_arg); // !!! 1866 1815 } 1867 1816 // PrintS("Saturation - done!!!\n"); … … 1870 1819 1871 1820 1872 if 1821 if(!ip) 1873 1822 { 1874 1823 qsort (nodes_final, spc_final, sizeof (sorted_pair_node *), 1875 1824 tgb_pair_better_gen2); 1876 1825 1877 1826 … … 1889 1838 } 1890 1839 1891 static poly 1892 redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n) 1840 static poly redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n) 1893 1841 { 1894 1842 m = nInit (1); 1895 if 1843 if(h == NULL) 1896 1844 return NULL; 1897 1845 1898 1846 assume (len == pLength (h)); 1899 1847 kStrategy strat = c->strat; 1900 if 1848 if(0 > strat->sl) 1901 1849 { 1902 1850 return h; … … 1920 1868 j = kFindDivisibleByInS_easy (strat, P.p, P.sev); 1921 1869 //j=kFindDivisibleByInS(strat,&dummy,&P); 1922 if 1923 1924 1870 if((j >= 0) && ((!n) || 1871 ((strat->lenS[j] <= n) && 1872 ((strat->lenSw == NULL) || (strat->lenSw[j] <= n))))) 1925 1873 { 1926 1874 nNormalize (pGetCoeff (P.p)); 1927 1875 #ifdef KDEBUG 1928 if 1929 { 1930 1931 1932 1933 1876 if(TEST_OPT_DEBUG) 1877 { 1878 PrintS ("red:"); 1879 wrp (h); 1880 PrintS (" with "); 1881 wrp (strat->S[j]); 1934 1882 } 1935 1883 #endif 1936 1884 1937 1885 number coef = kBucketPolyRed (P.bucket, strat->S[j], 1938 1939 1886 strat->lenS[j] /*pLength(strat->S[j]) */ , 1887 strat->kNoether); 1940 1888 number m2 = nMult (m, coef); 1941 1889 nDelete (&m); … … 1944 1892 h = kBucketGetLm (P.bucket); 1945 1893 1946 if 1947 { 1948 1949 1950 1894 if(h == NULL) 1895 { 1896 len = 0; 1897 kBucketDestroy (&P.bucket); 1898 return NULL; 1951 1899 } 1952 1900 P.p = h; … … 1954 1902 P.SetShortExpVector (); 1955 1903 #ifdef KDEBUG 1956 if 1957 { 1958 1959 1960 1904 if(TEST_OPT_DEBUG) 1905 { 1906 PrintS ("\nto:"); 1907 wrp (h); 1908 PrintLn (); 1961 1909 } 1962 1910 #endif … … 1973 1921 } 1974 1922 1975 static poly 1976 redTailShort (poly h, kStrategy strat) 1977 { 1978 if (h == NULL) 1979 return NULL; //n_Init(1,currRing); 1980 if (TEST_V_MODPSOLVSB) 1923 static poly redTailShort (poly h, kStrategy strat) 1924 { 1925 if(h == NULL) 1926 return NULL; //n_Init(1,currRing); 1927 if(TEST_V_MODPSOLVSB) 1981 1928 { 1982 1929 bit_reduce (pNext (h), strat->tailRing); … … 1984 1931 int i; 1985 1932 int len = pLength (h); 1986 for 1987 { 1988 if 1989 1933 for(i = 0; i <= strat->sl; i++) 1934 { 1935 if((strat->lenS[i] > 2) 1936 || ((strat->lenSw != NULL) && (strat->lenSw[i] > 2))) 1990 1937 break; 1991 1938 } … … 1993 1940 } 1994 1941 1995 static void 1996 line_of_extended_prod (int fixpos, slimgb_alg * c) 1997 { 1998 if (c->gcd_of_terms[fixpos] == NULL) 1942 static void line_of_extended_prod (int fixpos, slimgb_alg * c) 1943 { 1944 if(c->gcd_of_terms[fixpos] == NULL) 1999 1945 { 2000 1946 c->gcd_of_terms[fixpos] = gcd_of_terms (c->S->m[fixpos], c->r); 2001 if 1947 if(c->gcd_of_terms[fixpos]) 2002 1948 { 2003 1949 int i; 2004 for (i = 0; i < fixpos; i++) 2005 if ((c->states[fixpos][i] != HASTREP) 2006 && 2007 (extended_product_criterion 2008 (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i], 2009 c->gcd_of_terms[i], c))) 2010 { 2011 c->states[fixpos][i] = HASTREP; 2012 c->extended_product_crit++; 2013 } 2014 for (i = fixpos + 1; i < c->n; i++) 2015 if ((c->states[i][fixpos] != HASTREP) 2016 && 2017 (extended_product_criterion 2018 (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i], 2019 c->gcd_of_terms[i], c))) 2020 { 2021 c->states[i][fixpos] = HASTREP; 2022 c->extended_product_crit++; 2023 } 2024 } 2025 } 2026 } 2027 2028 static void 2029 c_S_element_changed_hook (int pos, slimgb_alg * c) 1950 for(i = 0; i < fixpos; i++) 1951 if((c->states[fixpos][i] != HASTREP) 1952 && 1953 (extended_product_criterion 1954 (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i], 1955 c->gcd_of_terms[i], c))) 1956 { 1957 c->states[fixpos][i] = HASTREP; 1958 c->extended_product_crit++; 1959 } 1960 for(i = fixpos + 1; i < c->n; i++) 1961 if((c->states[i][fixpos] != HASTREP) 1962 && 1963 (extended_product_criterion 1964 (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i], 1965 c->gcd_of_terms[i], c))) 1966 { 1967 c->states[i][fixpos] = HASTREP; 1968 c->extended_product_crit++; 1969 } 1970 } 1971 } 1972 } 1973 1974 static void c_S_element_changed_hook (int pos, slimgb_alg * c) 2030 1975 { 2031 1976 length_one_crit (c, pos, c->lengths[pos]); 2032 if 1977 if(!c->nc) 2033 1978 line_of_extended_prod (pos, c); 2034 1979 } … … 2041 1986 poly_tree_node *r; 2042 1987 int n; 2043 1988 poly_tree_node (int sn):l (NULL), r (NULL), n (sn) 2044 1989 { 2045 1990 } … … 2051 1996 int n; 2052 1997 int get_n (poly p); 2053 1998 exp_number_builder ():top_level (0), n (0) 2054 1999 { 2055 2000 } 2056 2001 }; 2057 int 2058 exp_number_builder::get_n (poly p) 2002 int exp_number_builder::get_n (poly p) 2059 2003 { 2060 2004 poly_tree_node **node = &top_level; 2061 while 2005 while(*node != NULL) 2062 2006 { 2063 2007 int c = pLmCmp (p, (*node)->p); 2064 if 2008 if(c == 0) 2065 2009 return (*node)->n; 2066 if 2010 if(c == -1) 2067 2011 node = &((*node)->r); 2068 2012 else … … 2087 2031 2088 2032 //! obsolete 2089 void 2090 t2ippa_rec (poly * ip, int *ia, poly_tree_node * k, int &offset) 2091 { 2092 if (!k) 2033 void t2ippa_rec (poly * ip, int *ia, poly_tree_node * k, int &offset) 2034 { 2035 if(!k) 2093 2036 return; 2094 2037 t2ippa_rec (ip, ia, k->l, offset); … … 2102 2045 2103 2046 //! obsolete 2104 void 2105 t2ippa (poly * ip, int *ia, exp_number_builder & e) 2047 void t2ippa (poly * ip, int *ia, exp_number_builder & e) 2106 2048 { 2107 2049 … … 2110 2052 } 2111 2053 2112 int 2113 anti_poly_order (const void *a, const void *b) 2054 int anti_poly_order (const void *a, const void *b) 2114 2055 { 2115 2056 return -pLmCmp (((int_poly_pair *) a)->p, ((int_poly_pair *) b)->p); 2116 2057 } 2117 2058 2118 BOOLEAN 2119 is_valid_ro (red_object & ro) 2059 BOOLEAN is_valid_ro (red_object & ro) 2120 2060 { 2121 2061 red_object r2 = ro; 2122 2062 ro.validate (); 2123 if 2063 if((r2.p != ro.p) || (r2.sev != ro.sev)) 2124 2064 return FALSE; 2125 2065 return TRUE; 2126 2066 } 2127 2067 2128 int 2129 terms_sort_crit (const void *a, const void *b) 2068 int terms_sort_crit (const void *a, const void *b) 2130 2069 { 2131 2070 return -pLmCmp (*((poly *) a), *((poly *) b)); 2132 2071 } 2133 2072 2134 #if 0 // currently unused 2135 static void 2136 unify_terms (poly * terms, int &sum) 2137 { 2138 if (sum == 0) 2073 #if 0 // currently unused 2074 static void unify_terms (poly * terms, int &sum) 2075 { 2076 if(sum == 0) 2139 2077 return; 2140 2078 int last = 0; 2141 2079 int curr = 1; 2142 while 2143 { 2144 if 2080 while(curr < sum) 2081 { 2082 if(!(pLmEqual (terms[curr], terms[last]))) 2145 2083 { 2146 2084 terms[++last] = terms[curr]; … … 2151 2089 } 2152 2090 #endif 2153 #if 0 2091 #if 0 // currently unused 2154 2092 static void 2155 2093 export_mat (number * number_array, int pn, int tn, const char *format_str, 2156 2094 int mat_nr) 2157 2095 { 2158 2096 char matname[20]; … … 2161 2099 int i, j; 2162 2100 fprintf (out, "mat=[\n"); 2163 for 2101 for(i = 0; i < pn; i++) 2164 2102 { 2165 2103 fprintf (out, "[\n"); 2166 for 2167 { 2168 if 2169 { 2170 2104 for(j = 0; j < tn; j++) 2105 { 2106 if(j > 0) 2107 { 2108 fprintf (out, ", "); 2171 2109 } 2172 2110 fprintf (out, "%i", npInt (number_array[i * tn + j], currRing)); 2173 2111 } 2174 if 2112 if(i < pn - 1) 2175 2113 fprintf (out, "],\n"); 2176 2114 else … … 2188 2126 static void 2189 2127 linalg_step_modp (poly * p, poly * p_out, int &pn, poly * terms, int tn, 2190 2128 slimgb_alg * c) 2191 2129 { 2192 2130 static int export_n = 0; … … 2194 2132 assume (rField_is_Zp (c->r)); 2195 2133 //I don't do deletes, copies of number_types ... 2196 const number_type zero = 0; 2134 const number_type zero = 0; //npInit(0); 2197 2135 int array_size = pn * tn; 2198 2136 number_type *number_array = 2199 2137 (number_type *) omalloc (pn * tn * sizeof (number_type)); 2200 2138 int i; 2201 for 2139 for(i = 0; i < array_size; i++) 2202 2140 { 2203 2141 number_array[i] = zero; 2204 2142 } 2205 for 2143 for(i = 0; i < pn; i++) 2206 2144 { 2207 2145 poly h = p[i]; … … 2218 2156 int act_row = 0; 2219 2157 int p_pos = 0; 2220 for 2158 for(i = 0; i < pn; i++) 2221 2159 { 2222 2160 poly h = NULL; … … 2226 2164 h = row_to_poly (row, terms, tn, c->r); 2227 2165 2228 if 2166 if(h != NULL) 2229 2167 { 2230 2168 p_out[p_pos++] = h; … … 2233 2171 pn = p_pos; 2234 2172 //assert(p_pos==rank) 2235 while 2173 while(p_pos < pn) 2236 2174 { 2237 2175 p_out[p_pos++] = NULL; … … 2243 2181 #endif 2244 2182 #endif 2245 static void 2246 mass_add (poly * p, int pn, slimgb_alg * c) 2183 static void mass_add (poly * p, int pn, slimgb_alg * c) 2247 2184 { 2248 2185 int j; … … 2250 2187 sorted_pair_node ***sbuf = 2251 2188 (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **)); 2252 for 2189 for(j = 0; j < pn; j++) 2253 2190 { 2254 2191 p_Test (p[j], c->r); … … 2256 2193 } 2257 2194 int sum = 0; 2258 for 2195 for(j = 0; j < pn; j++) 2259 2196 { 2260 2197 sum += ibuf[j]; … … 2263 2200 (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *)); 2264 2201 int partsum = 0; 2265 for 2202 for(j = 0; j < pn; j++) 2266 2203 { 2267 2204 memmove (big_sbuf + partsum, sbuf[j], 2268 2205 ibuf[j] * sizeof (sorted_pair_node *)); 2269 2206 omfree (sbuf[j]); 2270 2207 partsum += ibuf[j]; … … 2281 2218 #ifdef TGB_DEBUG 2282 2219 int z; 2283 for 2220 for(z = 1; z <= c->pair_top; z++) 2284 2221 { 2285 2222 assume (pair_better (c->apairs[z], c->apairs[z - 1], c)); … … 2291 2228 #ifdef NORO_CACHE 2292 2229 #ifndef NORO_NON_POLY 2293 void 2294 NoroCache::evaluateRows () 2230 void NoroCache::evaluateRows () 2295 2231 { 2296 2232 //after that can evaluate placeholders 2297 2233 int i; 2298 2234 buffer = (number *) omalloc (nIrreducibleMonomials * sizeof (number)); 2299 for 2235 for(i = 0; i < root.branches_len; i++) 2300 2236 { 2301 2237 evaluateRows (1, root.branches[i]); … … 2305 2241 } 2306 2242 2307 void 2308 NoroCache::evaluateRows (int level, NoroCacheNode * node) 2243 void NoroCache::evaluateRows (int level, NoroCacheNode * node) 2309 2244 { 2310 2245 assume (level >= 0); 2311 if 2246 if(node == NULL) 2312 2247 return; 2313 if 2248 if(level < pVariables) 2314 2249 { 2315 2250 int i, sum; 2316 for 2251 for(i = 0; i < node->branches_len; i++) 2317 2252 { 2318 2253 evaluateRows (level + 1, node->branches[i]); … … 2322 2257 { 2323 2258 DataNoroCacheNode *dn = (DataNoroCacheNode *) node; 2324 if 2259 if(dn->value_len != backLinkCode) 2325 2260 { 2326 2261 poly p = dn->value_poly; … … 2330 2265 memset (buffer, 0, sizeof (number) * nIrreducibleMonomials); 2331 2266 2332 if 2333 { 2334 2335 2336 2337 2267 if(p == NULL) 2268 { 2269 row->array = NULL; 2270 row->begin = 0; 2271 row->end = 0; 2272 return; 2338 2273 } 2339 2274 int i = 0; 2340 2275 int idx; 2341 2276 number *a = buffer; 2342 while 2343 { 2344 2345 2346 2347 2348 2349 if(i == 0)2350 2351 2352 2277 while(p) 2278 { 2279 DataNoroCacheNode *ref = getCacheReference (p); 2280 2281 idx = ref->term_index; 2282 assume (idx >= 0); 2283 a[idx] = p_GetCoeff (p, currRing); 2284 if(i == 0) 2285 row->begin = idx; 2286 i++; 2287 pIter (p); 2353 2288 } 2354 2289 row->end = idx + 1; … … 2362 2297 SparseRow *row = dn->row; 2363 2298 int i = 0; 2364 while 2365 { 2366 2367 2368 2369 2370 2371 2372 2373 2374 } 2375 if 2376 { 2377 2299 while(p) 2300 { 2301 DataNoroCacheNode *ref = getCacheReference (p); 2302 2303 int idx = ref->term_index; 2304 assume (idx >= 0); 2305 row->idx_array[i] = idx; 2306 row->coef_array[i] = p_GetCoeff (p, currRing); 2307 i++; 2308 pIter (p); 2309 } 2310 if(i != dn->value_len) 2311 { 2312 PrintS ("F4 calc wrong, as poly len was wrong\n"); 2378 2313 } 2379 2314 assume (i == dn->value_len); … … 2384 2319 2385 2320 void 2386 NoroCache::evaluatePlaceHolder (number * row,2387 2388 2321 NoroCache::evaluatePlaceHolder (number * row, 2322 std::vector < NoroPlaceHolder > 2323 &place_holders) 2389 2324 { 2390 2325 int i; 2391 2326 int s = place_holders.size (); 2392 for 2327 for(i = 0; i < s; i++) 2393 2328 { 2394 2329 DataNoroCacheNode *ref = place_holders[i].ref; 2395 2330 number coef = place_holders[i].coef; 2396 if 2331 if(ref->value_len == backLinkCode) 2397 2332 { 2398 2333 row[ref->term_index] = npAddM (row[ref->term_index], coef); … … 2402 2337 #ifndef NORO_SPARSE_ROWS_PRE 2403 2338 DenseRow *ref_row = ref->row; 2404 if 2405 2339 if(ref_row == NULL) 2340 continue; 2406 2341 number *ref_begin = ref_row->array; 2407 2342 number *ref_end = ref_row->array + (ref_row->end - ref_row->begin); 2408 2343 number *my_pos = row + ref_row->begin; 2409 2344 //TODO npisOne distinction 2410 if 2411 { 2412 while(ref_begin != ref_end)2413 2414 2415 2416 2417 2418 2345 if(!(npIsOne (coef))) 2346 { 2347 while(ref_begin != ref_end) 2348 { 2349 2350 *my_pos = npAddM (*my_pos, npMult (coef, *ref_begin)); 2351 ++ref_begin; 2352 ++my_pos; 2353 } 2419 2354 } 2420 2355 else 2421 2356 { 2422 while(ref_begin != ref_end)2423 2424 2425 2426 2427 2428 2357 while(ref_begin != ref_end) 2358 { 2359 2360 *my_pos = npAddM (*my_pos, *ref_begin); 2361 ++ref_begin; 2362 ++my_pos; 2363 } 2429 2364 } 2430 2365 2431 2366 #else 2432 2367 SparseRow *ref_row = ref->row; 2433 if 2434 2368 if(ref_row == NULL) 2369 continue; 2435 2370 int n = ref_row->len; 2436 2371 int j; 2437 2372 int *idx_array = ref_row->idx_array; 2438 2373 number *coef_array = ref_row->coef_array; 2439 for 2440 { 2441 2442 2443 2374 for(j = 0; j < n; j++) 2375 { 2376 int idx = idx_array[j]; 2377 number ref_coef = coef_array[j]; 2378 row[idx] = npAddM (row[idx], npMult (coef, ref_coef)); 2444 2379 } 2445 2380 #endif … … 2459 2394 //wrp(t); 2460 2395 res_holder.changed = TRUE; 2461 if 2396 if(force_unique) 2462 2397 { 2463 2398 DataNoroCacheNode *ref = cache->getCacheReference (t); 2464 if 2399 if(ref != NULL) 2465 2400 { 2466 2401 res_holder.len = ref->value_len; 2467 if 2468 { 2469 2402 if(res_holder.len == NoroCache::backLinkCode) 2403 { 2404 res_holder.len = 1; 2470 2405 } 2471 2406 res_holder.coef = p_GetCoeff (t, c->r); … … 2481 2416 { 2482 2417 BOOLEAN succ; 2483 poly cache_lookup = cache->lookup (t, succ, res_holder.len); 2484 if 2485 { 2486 if 2487 { 2488 2489 2490 2491 2492 2493 2494 2495 2496 2418 poly cache_lookup = cache->lookup (t, succ, res_holder.len); //don't own this yet 2419 if(succ) 2420 { 2421 if(cache_lookup == t) 2422 { 2423 //know they are equal 2424 //res_holder.len=1; 2425 2426 res_holder.changed = FALSE; 2427 res_holder.p = t; 2428 res_holder.coef = npInit (1); 2429 2430 res_holder.onlyBorrowed = FALSE; 2431 return res_holder; 2497 2432 } 2498 2433 … … 2510 2445 unsigned long sev = p_GetShortExpVector (t, currRing); 2511 2446 int i = kFindDivisibleByInS_easy (c->strat, t, sev); 2512 if 2447 if(i >= 0) 2513 2448 { 2514 2449 number coef_bak = p_GetCoeff (t, c->r); … … 2549 2484 p_SetCoeff (t, one, c->r); 2550 2485 res_holder.len = 1; 2551 if 2486 if(!(force_unique)) 2552 2487 { 2553 2488 res_holder.ref = cache->insert (t, t, res_holder.len); … … 2579 2514 #ifndef NORO_NON_POLY 2580 2515 //len input and out: Idea: reverse addition 2581 poly 2582 noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c) 2516 poly noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c) 2583 2517 { 2584 2518 assume (len == pLength (p)); 2585 2519 poly orig_p = p; 2586 if 2520 if(p == NULL) 2587 2521 { 2588 2522 len = 0; … … 2595 2529 int unchanged_size = 0; 2596 2530 2597 while 2531 while(p) 2598 2532 { 2599 2533 poly t = p; … … 2604 2538 #endif 2605 2539 MonRedRes red = noro_red_mon (t, FALSE, cache, c); 2606 if 2540 if((!(red.changed)) && (!(red.onlyBorrowed))) 2607 2541 { 2608 2542 unchanged_size++; 2609 2543 assume (npIsOne (red.coef)); 2610 2544 assume (p_GetCoeff (red.p, currRing) == coef_debug); 2611 if 2612 { 2613 2614 2545 if(unchanged_head) 2546 { 2547 pNext (unchanged_tail) = red.p; 2548 pIter (unchanged_tail); 2615 2549 } 2616 2550 else 2617 2551 { 2618 2619 2552 unchanged_tail = red.p; 2553 unchanged_head = red.p; 2620 2554 } 2621 2555 } … … 2623 2557 { 2624 2558 assume (red.len == pLength (red.p)); 2625 if 2626 { 2627 if(npIsOne (red.coef))2628 2629 2630 2631 2632 2559 if(red.onlyBorrowed) 2560 { 2561 if(npIsOne (red.coef)) 2562 { 2563 t = p_Copy (red.p, currRing); 2564 } 2565 else 2566 t = pp_Mult_nn (red.p, red.coef, currRing); 2633 2567 } 2634 2568 else 2635 2569 { 2636 if(npIsOne (red.coef))2637 2638 2639 2570 if(npIsOne (red.coef)) 2571 t = red.p; 2572 else 2573 t = p_Mult_nn (red.p, red.coef, currRing); 2640 2574 } 2641 2575 kBucket_Add_q (bucket, t, &red.len); … … 2675 2609 #ifndef NORO_NON_POLY 2676 2610 std::vector < NoroPlaceHolder > noro_red (poly p, int &len, NoroCache * cache, 2677 2611 slimgb_alg * c) 2678 2612 { 2679 2613 std::vector < NoroPlaceHolder > res; 2680 while 2614 while(p) 2681 2615 { 2682 2616 poly t = p; … … 2692 2626 h.coef = red.coef; 2693 2627 assume (!((h.ref->value_poly == NULL) && (h.ref->value_len != 0))); 2694 if 2628 if(h.ref->value_poly) 2695 2629 res.push_back (h); 2696 2630 } … … 2702 2636 #ifdef USE_NORO 2703 2637 #ifndef NORO_CACHE 2704 void 2705 noro_step (poly * p, int &pn, slimgb_alg * c) 2638 void noro_step (poly * p, int &pn, slimgb_alg * c) 2706 2639 { 2707 2640 poly *reduced = (poly *) omalloc (pn * sizeof (poly)); … … 2714 2647 NoroCache cache; 2715 2648 #endif 2716 for 2649 for(j = 0; j < pn; j++) 2717 2650 { 2718 2651 … … 2727 2660 assume (pLength (h) == h_len); 2728 2661 #endif 2729 if 2662 if(h != NULL) 2730 2663 { 2731 2664 #ifndef NORO_CACHE … … 2737 2670 reduced_len[reduced_c] = h_len; 2738 2671 reduced_c++; 2739 if 2740 2672 if(TEST_OPT_PROT) 2673 Print ("%d ", h_len); 2741 2674 } 2742 2675 } 2743 2676 int reduced_sum = 0; 2744 for 2677 for(j = 0; j < reduced_c; j++) 2745 2678 { 2746 2679 reduced_sum += reduced_len[j]; … … 2748 2681 poly *terms = (poly *) omalloc (reduced_sum * sizeof (poly)); 2749 2682 int tc = 0; 2750 for 2683 for(j = 0; j < reduced_c; j++) 2751 2684 { 2752 2685 poly h = reduced[j]; 2753 2686 2754 while 2687 while(h != NULL) 2755 2688 { 2756 2689 terms[tc++] = h; … … 2774 2707 omfree (reduced); 2775 2708 2776 if 2709 if(TEST_OPT_PROT) 2777 2710 PrintS ("\n"); 2778 2711 } … … 2781 2714 #endif 2782 2715 #endif 2783 static void 2784 go_on (slimgb_alg * c) 2716 static void go_on (slimgb_alg * c) 2785 2717 { 2786 2718 //set limit of 1000 for multireductions, at the moment for … … 2794 2726 int i = 0; 2795 2727 c->average_length = 0; 2796 for 2728 for(i = 0; i < c->n; i++) 2797 2729 { 2798 2730 c->average_length += c->lengths[i]; … … 2803 2735 2804 2736 #ifdef USE_NORO 2805 if 2737 if((use_noro) || (c->use_noro_last_block)) 2806 2738 max_pairs = bundle_size_noro; 2807 2739 #endif 2808 poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); 2740 poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); //nullterminated 2809 2741 2810 2742 int curr_deg = -1; 2811 while 2812 { 2813 sorted_pair_node *s = top_pair (c); 2814 2815 if 2743 while(i < max_pairs) 2744 { 2745 sorted_pair_node *s = top_pair (c); //here is actually chain criterium done 2746 2747 if(!s) 2816 2748 break; 2817 2749 2818 if 2819 { 2820 if 2821 2750 if(curr_deg >= 0) 2751 { 2752 if(s->deg > curr_deg) 2753 break; 2822 2754 } 2823 2755 … … 2825 2757 curr_deg = s->deg; 2826 2758 quick_pop_pair (c); 2827 if 2759 if(s->i >= 0) 2828 2760 { 2829 2761 //be careful replace_pair use createShortSpoly which is not noncommutative … … 2831 2763 replace_pair (s->i, s->j, c); 2832 2764 2833 if 2834 { 2835 2836 2765 if(s->i == s->j) 2766 { 2767 free_sorted_pair_node (s, c->r); 2768 continue; 2837 2769 } 2838 2770 now_t_rep (s->i, s->j, c); 2839 2771 } 2840 2772 poly h; 2841 if 2773 if(s->i >= 0) 2842 2774 { 2843 2775 #ifdef HAVE_PLURAL 2844 if 2845 { 2846 2847 2848 if(h != NULL)2849 2776 if(c->nc) 2777 { 2778 h = nc_CreateSpoly (c->S->m[s->i], c->S->m[s->j] /*, NULL */ , c->r); 2779 2780 if(h != NULL) 2781 p_Cleardenom (h, c->r); 2850 2782 } 2851 2783 else 2852 2784 #endif 2853 2785 h = ksOldCreateSpoly (c->S->m[s->i], c->S->m[s->j], NULL, c->r); 2854 2786 p_Test (h, c->r); 2855 2787 } … … 2864 2796 int mlen = pLength (h); 2865 2797 p_Test (h, c->r); 2866 if 2798 if((!c->nc) & (!(use_noro))) 2867 2799 { 2868 2800 h = redNF2 (h, c, mlen, coef, 2); … … 2872 2804 p_Test (h, c->r); 2873 2805 free_sorted_pair_node (s, c->r); 2874 if 2806 if(!h) 2875 2807 continue; 2876 2808 p[i] = h; … … 2879 2811 p[i] = NULL; 2880 2812 // pre_comp(p,i,c); 2881 if 2813 if(i == 0) 2882 2814 { 2883 2815 omfree (p); … … 2894 2826 //if ((!(c->nc))&&(rField_is_Zp(c->r))) 2895 2827 //{ 2896 if 2828 if(use_noro) 2897 2829 { 2898 2830 int pn = i; 2899 if 2831 if(pn == 0) 2900 2832 { 2901 2833 omfree (p); … … 2903 2835 } 2904 2836 { 2905 if 2906 { 2907 2837 if(npPrimeM < 255) 2838 { 2839 noro_step < tgb_uint8 > (p, pn, c); 2908 2840 } 2909 2841 else 2910 2842 { 2911 if(npPrimeM < 65000)2912 2913 2914 2915 2916 2917 2918 2843 if(npPrimeM < 65000) 2844 { 2845 noro_step < tgb_uint16 > (p, pn, c); 2846 } 2847 else 2848 { 2849 noro_step < tgb_uint32 > (p, pn, c); 2850 } 2919 2851 } 2920 2852 } … … 2935 2867 #endif 2936 2868 red_object *buf = (red_object *) omalloc (i * sizeof (red_object)); 2937 for 2869 for(j = 0; j < i; j++) 2938 2870 { 2939 2871 p_Test (p[j], c->r); … … 2942 2874 buf[j].bucket = kBucketCreate (currRing); 2943 2875 p_Test (p[j], c->r); 2944 if 2876 if(c->eliminationProblem) 2945 2877 { 2946 2878 buf[j].sugar = c->pTotaldegree_full (p[j]); … … 2954 2886 qsort (buf, i, sizeof (red_object), red_object_better_gen); 2955 2887 // Print("\ncurr_deg:%i\n",curr_deg); 2956 if 2888 if(TEST_OPT_PROT) 2957 2889 { 2958 2890 Print ("%dM[%d,", curr_deg, i); … … 2961 2893 multi_reduction (buf, i, c); 2962 2894 #ifdef TGB_RESORT_PAIRS 2963 if 2964 { 2965 if 2895 if(c->used_b) 2896 { 2897 if(TEST_OPT_PROT) 2966 2898 PrintS ("B"); 2967 2899 int e; 2968 for 2969 { 2970 if 2971 2900 for(e = 0; e <= c->pair_top; e++) 2901 { 2902 if(c->apairs[e]->i < 0) 2903 continue; 2972 2904 assume (c->apairs[e]->j >= 0); 2973 if 2974 { 2975 2976 2905 if((c->replaced[c->apairs[e]->i]) || (c->replaced[c->apairs[e]->j])) 2906 { 2907 sorted_pair_node *s = c->apairs[e]; 2908 s->expected_length = pair_weighted_length (s->i, s->j, c); 2977 2909 } 2978 2910 } 2979 2911 qsort (c->apairs, c->pair_top + 1, sizeof (sorted_pair_node *), 2980 2912 tgb_pair_better_gen2); 2981 2913 } 2982 2914 #endif … … 2984 2916 { 2985 2917 int k; 2986 for 2918 for(k = 0; k < i; k++) 2987 2919 { 2988 2920 assume (kFindDivisibleByInS_easy (c->strat, buf[k]) < 0); 2989 2921 int k2; 2990 for 2991 { 2992 if(k == k2)2993 2994 2995 2996 2922 for(k2 = 0; k2 < i; k2++) 2923 { 2924 if(k == k2) 2925 continue; 2926 assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c->r))) 2927 || (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2), 2928 wrp (buf[k2].p), FALSE)); 2997 2929 } 2998 2930 } … … 3001 2933 //resort S 3002 2934 3003 if 2935 if(TEST_OPT_PROT) 3004 2936 Print ("%i]", i); 3005 2937 3006 2938 poly *add_those = (poly *) omalloc (i * sizeof (poly)); 3007 for 2939 for(j = 0; j < i; j++) 3008 2940 { 3009 2941 int len; … … 3014 2946 p_Test (p, c->r); 3015 2947 //if (!c->nc) { 3016 if 2948 if((c->tailReductions) || (lies_in_last_dp_block (p, c))) 3017 2949 { 3018 2950 p = redNFTail (p, c->strat->sl, c->strat, 0); … … 3032 2964 omfree (buf); 3033 2965 3034 if 2966 if(TEST_OPT_PROT) 3035 2967 Print ("(%d)", c->pair_top + 1); 3036 2968 //TODO: implement that while(!(idIs0(c->add_later))) … … 3045 2977 #ifdef REDTAIL_S 3046 2978 3047 static poly 3048 redNFTail (poly h, const int sl, kStrategy strat, int len) 2979 static poly redNFTail (poly h, const int sl, kStrategy strat, int len) 3049 2980 { 3050 2981 BOOLEAN nc = rIsPluralRing (currRing); 3051 if 2982 if(h == NULL) 3052 2983 return NULL; 3053 2984 pTest (h); 3054 if 2985 if(0 > sl) 3055 2986 return h; 3056 if 2987 if(pNext (h) == NULL) 3057 2988 return h; 3058 2989 … … 3065 2996 len--; 3066 2997 h = P.p; 3067 if 2998 if(len <= 0) 3068 2999 len = pLength (h); 3069 3000 kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ ); … … 3077 3008 { 3078 3009 //int dummy=strat->sl; 3079 j = kFindDivisibleByInS_easy (strat, P.p, P.sev); 3080 if 3010 j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P); 3011 if(j >= 0) 3081 3012 { 3082 3013 #ifdef REDTAIL_PROT 3083 3084 #endif 3085 3014 PrintS ("r"); 3015 #endif 3016 nNormalize (pGetCoeff (P.p)); 3086 3017 #ifdef KDEBUG 3087 if(TEST_OPT_DEBUG)3088 3089 3090 3091 3092 3093 3094 #endif 3095 3096 3018 if(TEST_OPT_DEBUG) 3019 { 3020 PrintS ("red tail:"); 3021 wrp (h); 3022 PrintS (" with "); 3023 wrp (strat->S[j]); 3024 } 3025 #endif 3026 number coef; 3027 pTest (strat->S[j]); 3097 3028 #ifdef HAVE_PLURAL 3098 if(nc)3099 3100 3101 3102 3103 #endif 3104 3105 3106 3107 3108 3109 3110 3111 if(h == NULL)3112 3029 if(nc) 3030 { 3031 nc_BucketPolyRed_Z (P.bucket, strat->S[j], &coef); 3032 } 3033 else 3034 #endif 3035 coef = kBucketPolyRed (P.bucket, strat->S[j], 3036 strat->lenS[j] /*pLength(strat->S[j]) */ , 3037 strat->kNoether); 3038 pMult_nn (res, coef); 3039 nDelete (&coef); 3040 h = kBucketGetLm (P.bucket); 3041 pTest (h); 3042 if(h == NULL) 3043 { 3113 3044 #ifdef REDTAIL_PROT 3114 3115 #endif 3116 3117 3118 3119 3120 3121 3122 3045 PrintS (" "); 3046 #endif 3047 kBucketDestroy (&P.bucket); 3048 return res; 3049 } 3050 pTest (h); 3051 P.p = h; 3052 P.t_p = NULL; 3053 P.SetShortExpVector (); 3123 3054 #ifdef KDEBUG 3124 if(TEST_OPT_DEBUG)3125 3126 3127 3128 3129 3055 if(TEST_OPT_DEBUG) 3056 { 3057 PrintS ("\nto tail:"); 3058 wrp (h); 3059 PrintLn (); 3060 } 3130 3061 #endif 3131 3062 } … … 3133 3064 { 3134 3065 #ifdef REDTAIL_PROT 3135 3136 #endif 3137 3138 } 3139 } 3066 PrintS ("n"); 3067 #endif 3068 break; 3069 } 3070 } /* end loop current mon */ 3140 3071 // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); 3141 3072 //act->next=tmp;pIter(act); … … 3143 3074 pIter (act); 3144 3075 h = kBucketGetLm (P.bucket); 3145 if 3076 if(h == NULL) 3146 3077 { 3147 3078 #ifdef REDTAIL_PROT … … 3160 3091 3161 3092 //transfers ownership of m to mat 3162 void 3163 init_with_mac_poly (tgb_sparse_matrix * mat, int row, mac_poly m) 3093 void init_with_mac_poly (tgb_sparse_matrix * mat, int row, mac_poly m) 3164 3094 { 3165 3095 assume (mat->mp[row] == NULL); … … 3167 3097 #ifdef TGB_DEBUG 3168 3098 mac_poly r = m; 3169 while 3099 while(r) 3170 3100 { 3171 3101 assume (r->exp < mat->columns); … … 3177 3107 poly 3178 3108 free_row_to_poly (tgb_sparse_matrix * mat, int row, poly * monoms, 3179 3109 int monom_index) 3180 3110 { 3181 3111 poly p = NULL; … … 3183 3113 mac_poly r = mat->mp[row]; 3184 3114 mat->mp[row] = NULL; 3185 while 3115 while(r) 3186 3116 { 3187 3117 (*set_this) = pLmInit (monoms[monom_index - 1 - r->exp]); … … 3196 3126 } 3197 3127 3198 static int 3199 poly_crit (const void *ap1, const void *ap2) 3128 static int poly_crit (const void *ap1, const void *ap2) 3200 3129 { 3201 3130 poly p1, p2; … … 3204 3133 3205 3134 int c = pLmCmp (p1, p2); 3206 if 3135 if(c != 0) 3207 3136 return c; 3208 3137 int l1 = pLength (p1); 3209 3138 int l2 = pLength (p2); 3210 if 3139 if(l1 < l2) 3211 3140 return -1; 3212 if 3141 if(l1 > l2) 3213 3142 return 1; 3214 3143 return 0; 3215 3144 } 3216 3145 3217 void 3218 slimgb_alg::introduceDelayedPairs (poly * pa, int s) 3219 { 3220 if (s == 0) 3146 void slimgb_alg::introduceDelayedPairs (poly * pa, int s) 3147 { 3148 if(s == 0) 3221 3149 return; 3222 3150 sorted_pair_node **si_array = 3223 3151 (sorted_pair_node **) omalloc (s * sizeof (sorted_pair_node *)); 3224 3152 3225 for 3153 for(int i = 0; i < s; i++) 3226 3154 { 3227 3155 sorted_pair_node *si = … … 3265 3193 { 3266 3194 int hzz; 3267 for 3195 for(hzz = 0; hzz < IDELEMS (I); hzz++) 3268 3196 { 3269 3197 assume (I->m[hzz] != NULL); 3270 3198 int d = this->pTotaldegree (I->m[hzz]); 3271 3199 poly t = I->m[hzz]->next; 3272 while 3273 { 3274 if(d != this->pTotaldegree (t))3275 3276 3277 3278 3279 3280 } 3281 if 3282 3200 while(t) 3201 { 3202 if(d != this->pTotaldegree (t)) 3203 { 3204 is_homog = FALSE; 3205 break; 3206 } 3207 t = t->next; 3208 } 3209 if(!(is_homog)) 3210 break; 3283 3211 } 3284 3212 } … … 3291 3219 easy_product_crit = 0; 3292 3220 extended_product_crit = 0; 3293 if 3221 if(rField_is_Zp (r)) 3294 3222 isDifficultField = FALSE; 3295 3223 else … … 3327 3255 this->n = 0; 3328 3256 T_deg = (int *) omalloc (n * sizeof (int)); 3329 if 3257 if(eliminationProblem) 3330 3258 T_deg_full = (int *) omalloc (n * sizeof (int)); 3331 3259 else … … 3352 3280 3353 3281 short_Exps = (long *) omalloc (n * sizeof (long)); 3354 if 3282 if(F4_mode) 3355 3283 S = idInit (n, I->rank); 3356 3284 else 3357 3285 S = idInit (1, I->rank); 3358 3286 strat = new skStrategy; 3359 if 3287 if(eliminationProblem) 3360 3288 strat->honey = TRUE; 3361 3289 strat->syzComp = 0; … … 3367 3295 strat->sl = -1; 3368 3296 i = n; 3369 i = 1; 3297 i = 1; //some strange bug else 3370 3298 /* initS(c->S,NULL,c->strat); */ 3371 3299 /* intS start: */ 3372 3300 // i=((i+IDELEMS(c->S)+15)/16)*16; 3373 strat->ecartS = (intset) omAlloc (i * sizeof (int)); 3301 strat->ecartS = (intset) omAlloc (i * sizeof (int)); /*initec(i); */ 3374 3302 strat->sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long)); 3375 3303 /*initsevS(i); */ 3376 strat->S_2_R = (int *) omAlloc0 (i * sizeof (int)); 3304 strat->S_2_R = (int *) omAlloc0 (i * sizeof (int)); /*initS_2_R(i); */ 3377 3305 strat->fromQ = NULL; 3378 3306 strat->Shdl = idInit (1, 1); 3379 3307 strat->S = strat->Shdl->m; 3380 3308 strat->lenS = (int *) omAlloc0 (i * sizeof (int)); 3381 if 3309 if((isDifficultField) || (eliminationProblem)) 3382 3310 strat->lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type)); 3383 3311 else … … 3387 3315 3388 3316 assume (strat->sl == IDELEMS (strat->Shdl) - 1); 3389 if 3317 if(!(F4_mode)) 3390 3318 { 3391 3319 poly *array_arg = I->m; … … 3414 3342 else 3415 3343 { 3416 for (i = 1; i < n; i++)//the 1 is wanted, because first element is added to basis3344 for(i = 1; i < n; i++) //the 1 is wanted, because first element is added to basis 3417 3345 add_to_basis_ideal_quotient (I->m[i], this, NULL); 3418 3346 } 3419 for 3347 for(i = 0; i < IDELEMS (I); i++) 3420 3348 { 3421 3349 I->m[i] = NULL; … … 3425 3353 #ifdef USE_NORO 3426 3354 use_noro = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r)) 3427 3355 && (!(eliminationProblem)) && (npPrimeM <= 32003)); 3428 3356 use_noro_last_block = false; 3429 if 3357 if((!(use_noro)) && (lastDpBlockStart <= pVariables)) 3430 3358 { 3431 3359 use_noro_last_block = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r)) 3432 3360 && (npPrimeM <= 32003)); 3433 3361 } 3434 3362 #else … … 3443 3371 { 3444 3372 3445 if 3373 if(!(completed)) 3446 3374 { 3447 3375 poly *add = (poly *) omalloc ((pair_top + 2) * sizeof (poly)); 3448 3376 int piter; 3449 3377 int pos = 0; 3450 for 3378 for(piter = 0; piter <= pair_top; piter++) 3451 3379 { 3452 3380 sorted_pair_node *s = apairs[piter]; 3453 if 3454 { 3455 3456 if(s->lcm_of_lm != NULL)3457 3458 3459 3460 3381 if(s->i < 0) 3382 { 3383 //delayed element 3384 if(s->lcm_of_lm != NULL) 3385 { 3386 add[pos] = s->lcm_of_lm; 3387 pos++; 3388 } 3461 3389 } 3462 3390 free_sorted_pair_node (s, r); … … 3466 3394 add[pos] = NULL; 3467 3395 pos = 0; 3468 while 3396 while(add[pos] != NULL) 3469 3397 { 3470 3398 add_to_basis_ideal_quotient (add[pos], this, NULL); 3471 3399 pos++; 3472 3400 } 3473 for 3401 for(piter = 0; piter <= pair_top; piter++) 3474 3402 { 3475 3403 sorted_pair_node *s = apairs[piter]; … … 3483 3411 int i, j; 3484 3412 slimgb_alg *c = this; 3485 while 3413 while(c->to_destroy) 3486 3414 { 3487 3415 pDelete (&(c->to_destroy->p)); … … 3490 3418 omfree (old); 3491 3419 } 3492 while 3493 { 3494 for 3420 while(c->F) 3421 { 3422 for(i = 0; i < c->F->size; i++) 3495 3423 { 3496 3424 pDelete (&(c->F->mp[i].m)); … … 3502 3430 omfree (old); 3503 3431 } 3504 while 3505 { 3506 for 3432 while(c->F_minus) 3433 { 3434 for(i = 0; i < c->F_minus->size; i++) 3507 3435 { 3508 3436 pDelete (&(c->F_minus->p[i])); … … 3516 3444 #ifndef HAVE_BOOST 3517 3445 #ifndef USE_STDVECBOOL 3518 for 3446 for(int z = 1 /* zero length at 0 */ ; z < c->n; z++) 3519 3447 { 3520 3448 omfree (c->states[z]); … … 3526 3454 omfree (c->lengths); 3527 3455 omfree (c->weighted_lengths); 3528 for 3456 for(int z = 0; z < c->n; z++) 3529 3457 { 3530 3458 pDelete (&c->tmp_pair_lm[z]); … … 3535 3463 3536 3464 omfree (c->T_deg); 3537 if 3465 if(c->T_deg_full) 3538 3466 omfree (c->T_deg_full); 3539 3467 … … 3546 3474 omFree (c->strat->lenS); 3547 3475 3548 if 3476 if(c->strat->lenSw) 3549 3477 omFree (c->strat->lenSw); 3550 3478 3551 for 3552 { 3553 if 3479 for(i = 0; i < c->n; i++) 3480 { 3481 if(c->gcd_of_terms[i]) 3554 3482 pDelete (&(c->gcd_of_terms[i])); 3555 3483 } … … 3557 3485 3558 3486 omfree (c->apairs); 3559 if 3487 if(TEST_OPT_PROT) 3560 3488 { 3561 3489 //Print("calculated %d NFs\n",c->normal_forms); 3562 3490 Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n", 3563 3564 } 3565 3566 for 3567 { 3568 if 3491 c->normal_forms, c->easy_product_crit, c->extended_product_crit); 3492 } 3493 3494 for(i = 0; i <= c->strat->sl; i++) 3495 { 3496 if(!c->strat->S[i]) 3569 3497 continue; 3570 3498 BOOLEAN found = FALSE; 3571 for 3572 { 3573 if 3574 { 3575 3576 3577 } 3578 } 3579 if 3499 for(j = 0; j < c->n; j++) 3500 { 3501 if(c->S->m[j] == c->strat->S[i]) 3502 { 3503 found = TRUE; 3504 break; 3505 } 3506 } 3507 if(!found) 3580 3508 pDelete (&c->strat->S[i]); 3581 3509 } … … 3597 3525 // } 3598 3526 3599 if 3600 { 3601 for 3527 if(completed) 3528 { 3529 for(i = 0; i < c->n; i++) 3602 3530 { 3603 3531 assume (c->S->m[i] != NULL); 3604 if 3605 3606 for 3607 { 3608 if((c->S->m[j] == NULL) || (i == j))3609 3610 3611 3612 3613 3614 3615 if(p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],3616 3617 3618 3619 3620 3532 if(p_GetComp (c->S->m[i], currRing) > this->syz_comp) 3533 continue; 3534 for(j = 0; j < c->n; j++) 3535 { 3536 if((c->S->m[j] == NULL) || (i == j)) 3537 continue; 3538 assume (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j], 3539 c->S->m[i], ~c->short_Exps[i], 3540 c->r) == p_LmDivisibleBy (c->S->m[j], 3541 c->S->m[i], 3542 c->r)); 3543 if(p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j], 3544 c->S->m[i], ~c->short_Exps[i], c->r)) 3545 { 3546 pDelete (&c->S->m[i]); 3547 break; 3548 } 3621 3549 } 3622 3550 } … … 3627 3555 IDELEMS (I) = c->n; 3628 3556 idSkipZeroes (I); 3629 for 3557 for(i = 0; i <= c->strat->sl; i++) 3630 3558 c->strat->S[i] = NULL; 3631 3559 id_Delete (&c->strat->Shdl, c->r); … … 3635 3563 } 3636 3564 3637 ideal 3638 t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3565 ideal t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3639 3566 { 3640 3567 assume (r == currRing); … … 3643 3570 ring new_ring = rAssure_TDeg (orig_ring, 1, rVar (orig_ring), pos); 3644 3571 ideal s_h; 3645 if 3572 if(orig_ring != new_ring) 3646 3573 { 3647 3574 rChangeCurrRing (new_ring); … … 3666 3593 ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos); 3667 3594 ideal result; 3668 if 3595 if(orig_ring != new_ring) 3669 3596 { 3670 3597 idTest (s_result); … … 3688 3615 // Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(-2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(-2)),QlogSize(nlInit(5))); 3689 3616 3690 if 3691 if 3617 if(TEST_OPT_PROT) 3618 if(F4_mode) 3692 3619 PrintS ("F4 Modus \n"); 3693 3620 … … 3697 3624 ideal I = arg_I; 3698 3625 idCompactify (I); 3699 if 3626 if(idIs0 (I)) 3700 3627 return I; 3701 3628 int i; 3702 for 3629 for(i = 0; i < IDELEMS (I); i++) 3703 3630 { 3704 3631 assume (I->m[i] != NULL); … … 3712 3639 slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos); 3713 3640 3714 while 3715 3716 3641 while((c->pair_top >= 0) 3642 && ((!(TEST_OPT_DEGBOUND)) 3643 || (c->apairs[c->pair_top]->deg <= Kstd1_deg))) 3717 3644 { 3718 3645 #ifdef HAVE_F4 3719 if 3646 if(F4_mode) 3720 3647 go_on_F4 (c); 3721 3648 else … … 3723 3650 go_on (c); 3724 3651 } 3725 if 3652 if(c->pair_top < 0) 3726 3653 c->completed = TRUE; 3727 3654 I = c->S; 3728 3655 delete c; 3729 if 3656 if(TEST_OPT_REDSB) 3730 3657 { 3731 3658 ideal erg = kInterRed (I, NULL); … … 3739 3666 } 3740 3667 3741 void 3742 now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c) 3668 void now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c) 3743 3669 { 3744 3670 int i, j; 3745 if 3671 if(arg_i == arg_j) 3746 3672 { 3747 3673 return; 3748 3674 } 3749 if 3675 if(arg_i > arg_j) 3750 3676 { 3751 3677 i = arg_j; … … 3767 3693 assume (arg_i < state->n); 3768 3694 assume (arg_j < state->n); 3769 if 3695 if(arg_i == arg_j) 3770 3696 { 3771 3697 return (TRUE); 3772 3698 } 3773 if 3699 if(arg_i > arg_j) 3774 3700 { 3775 3701 return (state->states[arg_i][arg_j] == HASTREP); … … 3781 3707 } 3782 3708 3783 #if 0 // unused 3784 static int 3785 pLcmDeg (poly a, poly b) 3709 #if 0 // unused 3710 static int pLcmDeg (poly a, poly b) 3786 3711 { 3787 3712 int i; 3788 3713 int n = 0; 3789 for 3714 for(i = pVariables; i; i--) 3790 3715 { 3791 3716 n += si_max (pGetExp (a, i), pGetExp (b, i)); … … 3795 3720 #endif 3796 3721 3797 static void 3798 shorten_tails (slimgb_alg * c, poly monom) 3722 static void shorten_tails (slimgb_alg * c, poly monom) 3799 3723 { 3800 3724 return; 3801 3725 // BOOLEAN corr=lenS_correct(c->strat); 3802 for 3726 for(int i = 0; i < c->n; i++) 3803 3727 { 3804 3728 //enter tail 3805 3729 3806 if 3730 if(c->S->m[i] == NULL) 3807 3731 continue; 3808 3732 poly tail = c->S->m[i]->next; 3809 3733 poly prev = c->S->m[i]; 3810 3734 BOOLEAN did_something = FALSE; 3811 while 3812 { 3813 if 3814 { 3815 3816 3817 3818 3819 3820 3821 3735 while((tail != NULL) && (pLmCmp (tail, monom) >= 0)) 3736 { 3737 if(p_LmDivisibleBy (monom, tail, c->r)) 3738 { 3739 did_something = TRUE; 3740 prev->next = tail->next; 3741 tail->next = NULL; 3742 p_Delete (&tail, c->r); 3743 tail = prev; 3744 //PrintS("Shortened"); 3745 c->lengths[i]--; 3822 3746 } 3823 3747 prev = tail; 3824 3748 tail = tail->next; 3825 3749 } 3826 if 3750 if(did_something) 3827 3751 { 3828 3752 int new_pos; … … 3833 3757 int old_pos = -1; 3834 3758 //assume new_pos<old_pos 3835 for 3836 { 3837 if(c->strat->S[z] == c->S->m[i])3838 3839 3840 3841 3842 } 3843 if 3844 for(int z = new_pos - 1; z >= 0; z--)3845 3846 if(c->strat->S[z] == c->S->m[i])3847 3848 3849 3850 3851 3759 for(int z = 0; z <= c->strat->sl; z++) 3760 { 3761 if(c->strat->S[z] == c->S->m[i]) 3762 { 3763 old_pos = z; 3764 break; 3765 } 3766 } 3767 if(old_pos == -1) 3768 for(int z = new_pos - 1; z >= 0; z--) 3769 { 3770 if(c->strat->S[z] == c->S->m[i]) 3771 { 3772 old_pos = z; 3773 break; 3774 } 3775 } 3852 3776 assume (old_pos >= 0); 3853 3777 assume (new_pos <= old_pos); 3854 3778 assume (pLength (c->strat->S[old_pos]) == c->lengths[i]); 3855 3779 c->strat->lenS[old_pos] = c->lengths[i]; 3856 if 3857 3858 if 3859 3780 if(c->strat->lenSw) 3781 c->strat->lenSw[old_pos] = q; 3782 if(new_pos < old_pos) 3783 move_forward_in_S (old_pos, new_pos, c->strat); 3860 3784 length_one_crit (c, i, c->lengths[i]); 3861 3785 } … … 3863 3787 } 3864 3788 3865 #if 0 // currently unused 3866 static sorted_pair_node * 3867 pop_pair (slimgb_alg * c) 3789 #if 0 // currently unused 3790 static sorted_pair_node *pop_pair (slimgb_alg * c) 3868 3791 { 3869 3792 clean_top_of_pair_list (c); 3870 3793 3871 if 3794 if(c->pair_top < 0) 3872 3795 return NULL; 3873 3796 else … … 3876 3799 #endif 3877 3800 3878 void 3879 slimgb_alg::cleanDegs (int lower, int upper) 3801 void slimgb_alg::cleanDegs (int lower, int upper) 3880 3802 { 3881 3803 assume (is_homog); 3882 3804 int deg; 3883 if 3805 if(TEST_OPT_PROT) 3884 3806 { 3885 3807 PrintS ("C"); 3886 3808 } 3887 for 3809 for(deg = lower; deg <= upper; deg++) 3888 3810 { 3889 3811 int i; 3890 for 3891 { 3892 if 3893 { 3894 3895 3896 3897 if(!rField_is_Zp (r))3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 if(weighted_lengths)3911 3912 3913 3914 3915 for(j = 0; j <= strat->sl; j++)3916 3917 if(h == strat->S[j])3918 3919 3920 if(strat->lenS)3921 3922 3923 3924 if(strat->lenSw)3925 3926 3927 3928 if(new_pos < j)3929 3930 3931 3932 3933 3934 if(new_pos > j)3935 new_pos = new_pos - 1;//is identical with one element3936 if(new_pos > j)3937 3938 3939 3940 3941 3812 for(i = 0; i < n; i++) 3813 { 3814 if(T_deg[i] == deg) 3815 { 3816 poly h; 3817 h = S->m[i]; 3818 h = redNFTail (h, strat->sl, strat, lengths[i]); 3819 if(!rField_is_Zp (r)) 3820 { 3821 p_Cleardenom (h, r); 3822 //p_Content(h,r); 3823 } 3824 else 3825 pNorm (h); 3826 //TODO:GCD of TERMS 3827 poly got =::gcd_of_terms (h, r); 3828 p_Delete (&gcd_of_terms[i], r); 3829 gcd_of_terms[i] = got; 3830 int len = pLength (h); 3831 wlen_type wlen = pQuality (h, this, len); 3832 if(weighted_lengths) 3833 weighted_lengths[i] = wlen; 3834 lengths[i] = len; 3835 assume (h == S->m[i]); 3836 int j; 3837 for(j = 0; j <= strat->sl; j++) 3838 { 3839 if(h == strat->S[j]) 3840 { 3841 int new_pos = simple_posInS (strat, h, len, wlen); 3842 if(strat->lenS) 3843 { 3844 strat->lenS[j] = len; 3845 } 3846 if(strat->lenSw) 3847 { 3848 strat->lenSw[j] = wlen; 3849 } 3850 if(new_pos < j) 3851 { 3852 move_forward_in_S (j, new_pos, strat); 3853 } 3854 else 3855 { 3856 if(new_pos > j) 3857 new_pos = new_pos - 1; //is identical with one element 3858 if(new_pos > j) 3859 move_backward_in_S (j, new_pos, strat); 3860 } 3861 break; 3862 } 3863 } 3942 3864 } 3943 3865 } … … 3945 3867 { 3946 3868 int i, j; 3947 for 3948 { 3949 for 3950 { 3951 if(T_deg[i] + T_deg[j] <= upper)3952 3953 3954 3869 for(i = 0; i < this->n; i++) 3870 { 3871 for(j = 0; j < i; j++) 3872 { 3873 if(T_deg[i] + T_deg[j] <= upper) 3874 { 3875 now_t_rep (i, j, this); 3876 } 3955 3877 } 3956 3878 } … … 3960 3882 } 3961 3883 3962 sorted_pair_node * 3963 top_pair (slimgb_alg * c) 3964 { 3965 while (c->pair_top >= 0) 3966 { 3967 super_clean_top_of_pair_list (c); //yeah, I know, it's odd that I use a different proc here 3968 if ((c->is_homog) && (c->pair_top >= 0) 3969 && (c->apairs[c->pair_top]->deg >= c->lastCleanedDeg + 2)) 3884 sorted_pair_node *top_pair (slimgb_alg * c) 3885 { 3886 while(c->pair_top >= 0) 3887 { 3888 super_clean_top_of_pair_list (c); //yeah, I know, it's odd that I use a different proc here 3889 if((c->is_homog) && (c->pair_top >= 0) 3890 && (c->apairs[c->pair_top]->deg >= c->lastCleanedDeg + 2)) 3970 3891 { 3971 3892 int upper = c->apairs[c->pair_top]->deg - 1; … … 3979 3900 } 3980 3901 3981 if 3902 if(c->pair_top < 0) 3982 3903 return NULL; 3983 3904 else … … 3985 3906 } 3986 3907 3987 sorted_pair_node * 3988 quick_pop_pair (slimgb_alg * c) 3989 { 3990 if (c->pair_top < 0) 3908 sorted_pair_node *quick_pop_pair (slimgb_alg * c) 3909 { 3910 if(c->pair_top < 0) 3991 3911 return NULL; 3992 3912 else … … 3994 3914 } 3995 3915 3996 static void 3997 super_clean_top_of_pair_list (slimgb_alg * c) 3998 { 3999 while ((c->pair_top >= 0) 4000 && (c->apairs[c->pair_top]->i >= 0) 4001 && 4002 (good_has_t_rep 4003 (c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, c))) 3916 static void super_clean_top_of_pair_list (slimgb_alg * c) 3917 { 3918 while((c->pair_top >= 0) 3919 && (c->apairs[c->pair_top]->i >= 0) 3920 && 3921 (good_has_t_rep 3922 (c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, c))) 4004 3923 { 4005 3924 free_sorted_pair_node (c->apairs[c->pair_top], c->r); … … 4008 3927 } 4009 3928 4010 void 4011 clean_top_of_pair_list (slimgb_alg * c) 4012 { 4013 while ((c->pair_top >= 0) && (c->apairs[c->pair_top]->i >= 0) 4014 && 4015 (!state_is 4016 (UNCALCULATED, c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, 4017 c))) 3929 void clean_top_of_pair_list (slimgb_alg * c) 3930 { 3931 while((c->pair_top >= 0) && (c->apairs[c->pair_top]->i >= 0) 3932 && 3933 (!state_is 3934 (UNCALCULATED, c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, 3935 c))) 4018 3936 { 4019 3937 free_sorted_pair_node (c->apairs[c->pair_top], c->r); … … 4024 3942 static BOOLEAN 4025 3943 state_is (calc_state state, const int &arg_i, const int &arg_j, 4026 3944 slimgb_alg * c) 4027 3945 { 4028 3946 assume (0 <= arg_i); … … 4030 3948 assume (arg_i < c->n); 4031 3949 assume (arg_j < c->n); 4032 if 3950 if(arg_i == arg_j) 4033 3951 { 4034 3952 return (TRUE); 4035 3953 } 4036 if 3954 if(arg_i > arg_j) 4037 3955 { 4038 3956 return (c->states[arg_i][arg_j] == state); … … 4042 3960 } 4043 3961 4044 void 4045 free_sorted_pair_node (sorted_pair_node * s, ring r) 4046 { 4047 if (s->i >= 0) 3962 void free_sorted_pair_node (sorted_pair_node * s, ring r) 3963 { 3964 if(s->i >= 0) 4048 3965 p_Delete (&s->lcm_of_lm, r); 4049 3966 omfree (s); … … 4053 3970 pair_better (sorted_pair_node * a, sorted_pair_node * b, slimgb_alg * c) 4054 3971 { 4055 if 3972 if(a->deg < b->deg) 4056 3973 return TRUE; 4057 if 3974 if(a->deg > b->deg) 4058 3975 return FALSE; 4059 3976 4060 3977 int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm); 4061 if 3978 if(comp == 1) 4062 3979 return FALSE; 4063 if 3980 if(-1 == comp) 4064 3981 return TRUE; 4065 if 3982 if(a->expected_length < b->expected_length) 4066 3983 return TRUE; 4067 if 3984 if(a->expected_length > b->expected_length) 4068 3985 return FALSE; 4069 if 3986 if(a->i + a->j < b->i + b->j) 4070 3987 return TRUE; 4071 if 3988 if(a->i + a->j > b->i + b->j) 4072 3989 return FALSE; 4073 if 3990 if(a->i < b->i) 4074 3991 return TRUE; 4075 if 3992 if(a->i > b->i) 4076 3993 return FALSE; 4077 3994 return TRUE; 4078 3995 } 4079 3996 4080 static int 4081 tgb_pair_better_gen (const void *ap, const void *bp) 3997 static int tgb_pair_better_gen (const void *ap, const void *bp) 4082 3998 { 4083 3999 sorted_pair_node *a = *((sorted_pair_node **) ap); … … 4085 4001 assume ((a->i > a->j) || (a->i < 0)); 4086 4002 assume ((b->i > b->j) || (b->i < 0)); 4087 if 4003 if(a->deg < b->deg) 4088 4004 return -1; 4089 if 4005 if(a->deg > b->deg) 4090 4006 return 1; 4091 4007 4092 4008 int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm); 4093 4009 4094 if 4010 if(comp == 1) 4095 4011 return 1; 4096 if 4012 if(-1 == comp) 4097 4013 return -1; 4098 if 4014 if(a->expected_length < b->expected_length) 4099 4015 return -1; 4100 if 4016 if(a->expected_length > b->expected_length) 4101 4017 return 1; 4102 if 4018 if(a->i + a->j < b->i + b->j) 4103 4019 return -1; 4104 if 4020 if(a->i + a->j > b->i + b->j) 4105 4021 return 1; 4106 if 4022 if(a->i < b->i) 4107 4023 return -1; 4108 if 4024 if(a->i > b->i) 4109 4025 return 1; 4110 4026 return 0; 4111 4027 } 4112 4028 4113 static poly 4114 gcd_of_terms (poly p, ring r) 4029 static poly gcd_of_terms (poly p, ring r) 4115 4030 { 4116 4031 int max_g_0 = 0; … … 4119 4034 poly m = pOne (); 4120 4035 poly t; 4121 for 4036 for(i = pVariables; i; i--) 4122 4037 { 4123 4038 pSetExp (m, i, pGetExp (p, i)); 4124 if 4125 if 4126 4039 if(max_g_0 == 0) 4040 if(pGetExp (m, i) > 0) 4041 max_g_0 = i; 4127 4042 } 4128 4043 4129 4044 t = p->next; 4130 while 4131 { 4132 if 4045 while(t != NULL) 4046 { 4047 if(max_g_0 == 0) 4133 4048 break; 4134 for 4049 for(i = max_g_0; i; i--) 4135 4050 { 4136 4051 pSetExp (m, i, si_min (pGetExp (t, i), pGetExp (m, i))); 4137 if 4138 if(pGetExp (m, i) == 0)4139 4140 if 4141 { 4142 4052 if(max_g_0 == i) 4053 if(pGetExp (m, i) == 0) 4054 max_g_0 = 0; 4055 if((max_g_0 == 0) && (pGetExp (m, i) > 0)) 4056 { 4057 max_g_0 = i; 4143 4058 } 4144 4059 } … … 4146 4061 } 4147 4062 p_Setm (m, r); 4148 if 4063 if(max_g_0 > 0) 4149 4064 return m; 4150 4065 pDelete (&m); … … 4152 4067 } 4153 4068 4154 static inline BOOLEAN 4155 pHasNotCFExtended (poly p1, poly p2, poly m) 4156 { 4157 4158 if (pGetComp (p1) > 0 || pGetComp (p2) > 0) 4069 static inline BOOLEAN pHasNotCFExtended (poly p1, poly p2, poly m) 4070 { 4071 4072 if(pGetComp (p1) > 0 || pGetComp (p2) > 0) 4159 4073 return FALSE; 4160 4074 int i = 1; 4161 4075 loop 4162 4076 { 4163 if 4164 4077 if((pGetExp (p1, i) - pGetExp (m, i) > 0) 4078 && (pGetExp (p2, i) - pGetExp (m, i) > 0)) 4165 4079 return FALSE; 4166 if 4080 if(i == pVariables) 4167 4081 return TRUE; 4168 4082 i++; … … 4173 4087 static inline BOOLEAN 4174 4088 extended_product_criterion (poly p1, poly gcd1, poly p2, poly gcd2, 4175 4176 { 4177 if 4089 slimgb_alg * c) 4090 { 4091 if(c->nc) 4178 4092 return FALSE; 4179 if 4093 if(gcd1 == NULL) 4180 4094 return FALSE; 4181 if 4095 if(gcd2 == NULL) 4182 4096 return FALSE; 4183 gcd1->next = gcd2; 4097 gcd1->next = gcd2; //may ordered incorrect 4184 4098 poly m = gcd_of_terms (gcd1, c->r); 4185 4099 gcd1->next = NULL; 4186 if 4100 if(m == NULL) 4187 4101 return FALSE; 4188 4102 … … 4192 4106 } 4193 4107 4194 #if 0 //currently unused 4195 static poly 4196 kBucketGcd (kBucket * b, ring r) 4108 #if 0 //currently unused 4109 static poly kBucketGcd (kBucket * b, ring r) 4197 4110 { 4198 4111 int s = 0; … … 4200 4113 poly m, n; 4201 4114 BOOLEAN initialized = FALSE; 4202 for 4203 { 4204 if 4205 { 4206 if 4207 { 4208 4209 4210 if(m == NULL)4211 4115 for(i = MAX_BUCKET - 1; i >= 0; i--) 4116 { 4117 if(b->buckets[i] != NULL) 4118 { 4119 if(!initialized) 4120 { 4121 m = gcd_of_terms (b->buckets[i], r); 4122 initialized = TRUE; 4123 if(m == NULL) 4124 return NULL; 4212 4125 } 4213 4126 else 4214 4127 { 4215 4216 if(n == NULL)4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 if(m == NULL)4228 4128 n = gcd_of_terms (b->buckets[i], r); 4129 if(n == NULL) 4130 { 4131 pDelete (&m); 4132 return NULL; 4133 } 4134 n->next = m; 4135 poly t = gcd_of_terms (n, r); 4136 n->next = NULL; 4137 pDelete (&m); 4138 pDelete (&n); 4139 m = t; 4140 if(m == NULL) 4141 return NULL; 4229 4142 4230 4143 } … … 4235 4148 #endif 4236 4149 4237 static inline wlen_type 4238 quality_of_pos_in_strat_S (int pos, slimgb_alg * c) 4239 { 4240 if (c->strat->lenSw != NULL) 4150 static inline wlen_type quality_of_pos_in_strat_S (int pos, slimgb_alg * c) 4151 { 4152 if(c->strat->lenSw != NULL) 4241 4153 return c->strat->lenSw[pos]; 4242 4154 return c->strat->lenS[pos]; … … 4260 4172 static void 4261 4173 multi_reduction_lls_trick (red_object * los, int losl, slimgb_alg * c, 4262 4174 find_erg & erg) 4263 4175 { 4264 4176 erg.expand = NULL; 4265 BOOLEAN swap_roles; 4266 if 4267 { 4268 if 4177 BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS 4178 if(erg.fromS) 4179 { 4180 if(pLmEqual (c->strat->S[erg.reduce_by], los[erg.to_reduce_u].p)) 4269 4181 { 4270 4182 wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c); … … 4284 4196 wlen_type qc; 4285 4197 best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c); 4286 if 4287 { 4288 4289 4290 4291 4292 if(qc < quality_a)4293 4294 4295 4296 4297 4298 4299 4300 4198 if(qc < quality_a) 4199 { 4200 los[best].flatten (); 4201 int b_pos = kBucketCanonicalize (los[best].bucket); 4202 los[best].p = los[best].bucket->buckets[b_pos]; 4203 qc = pQuality (los[best].bucket->buckets[b_pos], c); 4204 if(qc < quality_a) 4205 { 4206 red_object h = los[erg.to_reduce_u]; 4207 los[erg.to_reduce_u] = los[best]; 4208 los[best] = h; 4209 swap_roles = TRUE; 4210 } 4211 else 4212 swap_roles = FALSE; 4301 4213 } 4302 4214 else 4303 4215 { 4304 4216 swap_roles = FALSE; 4305 4217 } 4306 4218 } 4307 4219 else 4308 4220 { 4309 if 4310 { 4311 4221 if(erg.to_reduce_u > erg.to_reduce_l) 4222 { 4223 wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c); 4312 4224 #ifdef HAVE_PLURAL 4313 if((c->nc) && (!(rIsSCA (c->r))))4314 4315 4316 4317 #endif 4318 4319 4320 4321 4322 if(qc < quality_a)4323 4324 4325 4326 4327 4328 4329 if(qc < quality_a)4330 4331 4332 4333 4334 4335 4336 4337 4338 4225 if((c->nc) && (!(rIsSCA (c->r)))) 4226 quality_a = 4227 quality_of_pos_in_strat_S_mult_high (erg.reduce_by, 4228 los[erg.to_reduce_u].p, c); 4229 #endif 4230 int best = erg.to_reduce_u + 1; 4231 wlen_type qc; 4232 best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c); 4233 assume (qc == los[best].guess_quality (c)); 4234 if(qc < quality_a) 4235 { 4236 los[best].flatten (); 4237 int b_pos = kBucketCanonicalize (los[best].bucket); 4238 los[best].p = los[best].bucket->buckets[b_pos]; 4239 qc = pQuality (los[best].bucket->buckets[b_pos], c); 4240 //(best!=erg.to_reduce_u+1) 4241 if(qc < quality_a) 4242 { 4243 red_object h = los[erg.to_reduce_u]; 4244 los[erg.to_reduce_u] = los[best]; 4245 los[best] = h; 4246 erg.reduce_by = erg.to_reduce_u; 4247 erg.fromS = FALSE; 4248 erg.to_reduce_u--; 4249 } 4250 } 4339 4251 } 4340 4252 else 4341 4253 { 4342 4343 4344 4345 if(qc < 0)4346 4347 if(qc < quality_a)4348 4349 4350 4351 4352 4353 4354 4355 if(qc < quality_a)4356 4357 4358 if(qc <= 2)4359 4360 4361 4362 4363 4364 4365 if(qc < quality_a / 2)4366 4367 else if(erg.reduce_by < c->n / 4)4368 4369 4370 if(exp)4371 4372 4373 4374 4375 4376 4377 4378 4379 if(TEST_OPT_PROT)4380 4381 4382 4383 4254 assume (erg.to_reduce_u == erg.to_reduce_l); 4255 wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c); 4256 wlen_type qc = los[erg.to_reduce_u].guess_quality (c); 4257 if(qc < 0) 4258 PrintS ("Wrong wlen_type"); 4259 if(qc < quality_a) 4260 { 4261 int best = erg.to_reduce_u; 4262 los[best].flatten (); 4263 int b_pos = kBucketCanonicalize (los[best].bucket); 4264 los[best].p = los[best].bucket->buckets[b_pos]; 4265 qc = pQuality (los[best].bucket->buckets[b_pos], c); 4266 assume (qc >= 0); 4267 if(qc < quality_a) 4268 { 4269 BOOLEAN exp = FALSE; 4270 if(qc <= 2) 4271 { 4272 //Print("\n qc is %lld \n",qc); 4273 exp = TRUE; 4274 } 4275 else 4276 { 4277 if(qc < quality_a / 2) 4278 exp = TRUE; 4279 else if(erg.reduce_by < c->n / 4) 4280 exp = TRUE; 4281 } 4282 if(exp) 4283 { 4284 poly clear_into; 4285 los[erg.to_reduce_u].flatten (); 4286 kBucketClear (los[erg.to_reduce_u].bucket, &clear_into, 4287 &erg.expand_length); 4288 erg.expand = pCopy (clear_into); 4289 kBucketInit (los[erg.to_reduce_u].bucket, clear_into, 4290 erg.expand_length); 4291 if(TEST_OPT_PROT) 4292 PrintS ("e"); 4293 } 4294 } 4295 } 4384 4296 } 4385 4297 … … 4390 4302 else 4391 4303 { 4392 if 4304 if(erg.reduce_by > erg.to_reduce_u) 4393 4305 { 4394 4306 //then lm(rb)>= lm(tru) so = … … 4399 4311 best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c); 4400 4312 4401 if 4402 { 4403 4404 4405 4313 if(qc < quality_a) 4314 { 4315 red_object h = los[erg.reduce_by]; 4316 los[erg.reduce_by] = los[best]; 4317 los[best] = h; 4406 4318 } 4407 4319 swap_roles = FALSE; … … 4417 4329 wlen_type quality_a = los[erg.reduce_by].guess_quality (c); 4418 4330 wlen_type qc; 4419 while 4420 { 4421 4422 4423 if(qc < quality_a)4424 4425 4426 4427 4331 while((il > 0) && pLmEqual (los[il - 1].p, los[il].p)) 4332 { 4333 il--; 4334 qc = los[il].guess_quality (c); 4335 if(qc < quality_a) 4336 { 4337 quality_a = qc; 4338 erg.reduce_by = il; 4339 } 4428 4340 } 4429 4341 swap_roles = FALSE; 4430 4342 } 4431 4343 } 4432 if 4433 { 4434 if 4344 if(swap_roles) 4345 { 4346 if(TEST_OPT_PROT) 4435 4347 PrintS ("b"); 4436 4348 poly clear_into; 4437 4349 int new_length; 4438 int bp = erg.to_reduce_u; 4350 int bp = erg.to_reduce_u; //bucket_positon 4439 4351 //kBucketClear(los[bp].bucket,&clear_into,&new_length); 4440 4352 new_length = los[bp].clear_to_poly (); … … 4442 4354 poly p = c->strat->S[erg.reduce_by]; 4443 4355 int j = erg.reduce_by; 4444 int old_length = c->strat->lenS[j]; 4356 int old_length = c->strat->lenS[j]; // in view of S 4445 4357 los[bp].p = p; 4446 if 4358 if(c->eliminationProblem) 4447 4359 { 4448 4360 los[bp].sugar = c->pTotaldegree_full (p); … … 4455 4367 new_pos = simple_posInS (c->strat, clear_into, new_length, qal); 4456 4368 assume (new_pos <= j); 4457 for 4458 { 4459 if 4460 { 4461 4462 4369 for(z = c->n; z; z--) 4370 { 4371 if(p == c->S->m[z - 1]) 4372 { 4373 pos_in_c = z - 1; 4374 break; 4463 4375 } 4464 4376 } … … 4466 4378 int tdeg_full = -1; 4467 4379 int tdeg = -1; 4468 if 4380 if(pos_in_c >= 0) 4469 4381 { 4470 4382 #ifdef TGB_RESORT_PAIRS … … 4476 4388 c->lengths[pos_in_c] = new_length; 4477 4389 c->weighted_lengths[pos_in_c] = qal; 4478 if 4479 4480 if 4481 4482 4390 if(c->gcd_of_terms[pos_in_c] == NULL) 4391 c->gcd_of_terms[pos_in_c] = gcd_of_terms (clear_into, c->r); 4392 if(c->T_deg_full) 4393 tdeg_full = c->T_deg_full[pos_in_c] = 4394 c->pTotaldegree_full (clear_into); 4483 4395 else 4484 4396 tdeg_full = tdeg; 4485 4397 c_S_element_changed_hook (pos_in_c, c); 4486 4398 } 4487 4399 else 4488 4400 { 4489 if 4490 { 4491 4492 4401 if(c->eliminationProblem) 4402 { 4403 tdeg_full = c->pTotaldegree_full (clear_into); 4404 tdeg = c->pTotaldegree (clear_into); 4493 4405 } 4494 4406 } … … 4497 4409 4498 4410 assume (pLength (clear_into) == new_length); 4499 if 4411 if(c->strat->lenSw != NULL) 4500 4412 c->strat->lenSw[j] = qal; 4501 if 4502 { 4503 p_Cleardenom (clear_into, c->r); 4413 if(!rField_is_Zp (c->r)) 4414 { 4415 p_Cleardenom (clear_into, c->r); //should be unnecessary 4504 4416 //p_Content(clear_into, c->r); 4505 4417 } … … 4512 4424 //input polys 4513 4425 #else 4514 if 4515 { 4516 if 4517 4426 if(new_pos < j) 4427 { 4428 if(c->strat->honey) 4429 c->strat->ecartS[j] = tdeg_full - tdeg; 4518 4430 move_forward_in_S (j, new_pos, c->strat); 4519 4431 erg.reduce_by = new_pos; … … 4523 4435 } 4524 4436 4525 static int 4526 fwbw (red_object * los, int i) 4437 static int fwbw (red_object * los, int i) 4527 4438 { 4528 4439 int i2 = i; … … 4532 4443 BOOLEAN incr = TRUE; 4533 4444 4534 while 4535 { 4536 if 4445 while(1) 4446 { 4447 if(!bw) 4537 4448 { 4538 4449 step = si_min (i2, step); 4539 if 4540 4450 if(step == 0) 4451 break; 4541 4452 i2 -= step; 4542 4453 4543 if 4544 { 4545 4546 4454 if(!pLmEqual (los[i].p, los[i2].p)) 4455 { 4456 bw = TRUE; 4457 incr = FALSE; 4547 4458 } 4548 4459 else 4549 4460 { 4550 if((!incr) && (step == 1))4551 4461 if((!incr) && (step == 1)) 4462 break; 4552 4463 } 4553 4464 } … … 4555 4466 { 4556 4467 step = si_min (i - i2, step); 4557 if 4558 4468 if(step == 0) 4469 break; 4559 4470 i2 += step; 4560 if 4561 { 4562 if(step == 1)4563 4564 4565 4566 4567 4568 } 4569 } 4570 if 4471 if(pLmEqual (los[i].p, los[i2].p)) 4472 { 4473 if(step == 1) 4474 break; 4475 else 4476 { 4477 bw = FALSE; 4478 } 4479 } 4480 } 4481 if(incr) 4571 4482 step *= 2; 4572 4483 else 4573 4484 { 4574 if 4575 4485 if(step % 2 == 1) 4486 step = (step + 1) / 2; 4576 4487 else 4577 4488 step /= 2; 4578 4489 } 4579 4490 } … … 4586 4497 assume (l <= u + 1); 4587 4498 int i; 4588 for 4499 for(i = l; i <= u; i++) 4589 4500 { 4590 4501 kBucketCanonicalize (los[i].bucket); … … 4594 4505 static void 4595 4506 multi_reduction_find (red_object * los, int losl, slimgb_alg * c, int startf, 4596 4507 find_erg & erg) 4597 4508 { 4598 4509 kStrategy strat = c->strat; … … 4600 4511 assume (startf <= losl); 4601 4512 assume ((startf == losl - 1) 4602 4513 || (pLmCmp (los[startf].p, los[startf + 1].p) == -1)); 4603 4514 int i = startf; 4604 4515 4605 4516 int j; 4606 while 4517 while(i >= 0) 4607 4518 { 4608 4519 assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) <= 0)); 4609 4520 assume (is_valid_ro (los[i])); 4610 4521 assume ((!(c->eliminationProblem)) 4611 4522 || (los[i].sugar >= c->pTotaldegree (los[i].p))); 4612 4523 j = kFindDivisibleByInS_easy (strat, los[i]); 4613 if 4524 if(j >= 0) 4614 4525 { 4615 4526 erg.to_reduce_u = i; … … 4626 4537 return; 4627 4538 } 4628 if 4539 if(j < 0) 4629 4540 { 4630 4541 //not reduceable, try to use this for reducing higher terms … … 4633 4544 assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p))); 4634 4545 assume (i >= i2); 4635 if 4636 { 4637 4638 4639 4640 4641 4642 4643 4546 if(i2 != i) 4547 { 4548 erg.to_reduce_u = i - 1; 4549 erg.to_reduce_l = i2; 4550 erg.reduce_by = i; 4551 erg.fromS = FALSE; 4552 assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1)); 4553 canonicalize_region (los, erg.to_reduce_u + 1, startf, c); 4554 return; 4644 4555 } 4645 4556 i--; 4646 4557 } 4647 4558 } 4648 erg.reduce_by = -1; 4559 erg.reduce_by = -1; //error code 4649 4560 return; 4650 4561 } … … 4661 4572 int i = l; 4662 4573 int last = -1; 4663 while 4664 { 4665 if 4574 while(i <= u) 4575 { 4576 if(los[i].p == NULL) 4666 4577 { 4667 4578 kBucketDestroy (&los[i].bucket); 4668 4579 // delete los[i];//here we assume los are constructed with new 4669 4580 //destroy resources, must be added here 4670 if 4671 { 4672 4673 4581 if(last >= 0) 4582 { 4583 memmove (los + (int) (last + 1 - deleted), los + (last + 1), 4584 sizeof (red_object) * (i - 1 - last)); 4674 4585 } 4675 4586 last = i; … … 4678 4589 i++; 4679 4590 } 4680 if 4591 if((last >= 0) && (last != losl - 1)) 4681 4592 memmove (los + (int) (last + 1 - deleted), los + last + 1, 4682 4593 sizeof (red_object) * (losl - 1 - last)); 4683 4594 return deleted; 4684 4595 } 4685 4596 4686 int 4687 search_red_object_pos (red_object * a, int top, red_object * key) 4597 int search_red_object_pos (red_object * a, int top, red_object * key) 4688 4598 { 4689 4599 int an = 0; 4690 4600 int en = top; 4691 if 4601 if(top == -1) 4692 4602 return 0; 4693 if 4603 if(pLmCmp (key->p, a[top].p) == 1) 4694 4604 return top + 1; 4695 4605 int i; 4696 4606 loop 4697 4607 { 4698 if 4699 { 4700 if 4701 4608 if(an >= en - 1) 4609 { 4610 if(pLmCmp (key->p, a[an].p) == -1) 4611 return an; 4702 4612 return en; 4703 4613 } 4704 4614 i = (an + en) / 2; 4705 if 4615 if(pLmCmp (key->p, a[i].p) == -1) 4706 4616 en = i; 4707 4617 else … … 4710 4620 } 4711 4621 4712 static void 4713 sort_region_down (red_object * los, int l, int u, slimgb_alg * c) 4622 static void sort_region_down (red_object * los, int l, int u, slimgb_alg * c) 4714 4623 { 4715 4624 int r_size = u - l + 1; … … 4719 4628 int bound = 0; 4720 4629 BOOLEAN at_end = FALSE; 4721 for 4722 { 4723 if 4630 for(i = l; i <= u; i++) 4631 { 4632 if(!(at_end)) 4724 4633 { 4725 4634 bound = new_indices[i - l] = 4726 4727 if 4728 4635 bound + search_red_object_pos (los + bound, l - bound - 1, los + i); 4636 if(bound == l) 4637 at_end = TRUE; 4729 4638 } 4730 4639 else … … 4735 4644 red_object *los_region = 4736 4645 (red_object *) omalloc (sizeof (red_object) * (u - l + 1)); 4737 for 4646 for(int i = 0; i < r_size; i++) 4738 4647 { 4739 4648 new_indices[i] += i; … … 4745 4654 int j = u; 4746 4655 int j2 = l - 1; 4747 while 4748 { 4749 if 4656 while(i >= 0) 4657 { 4658 if(new_indices[i] == j) 4750 4659 { 4751 4660 los[j] = los_region[i]; … … 4767 4676 4768 4677 //assume that los is ordered ascending by leading term, all non zero 4769 static void 4770 multi_reduction (red_object * los, int &losl, slimgb_alg * c) 4678 static void multi_reduction (red_object * los, int &losl, slimgb_alg * c) 4771 4679 { 4772 4680 poly *delay = (poly *) omalloc (losl * sizeof (poly)); … … 4778 4686 wlen_type max_initial_quality = 0; 4779 4687 4780 for 4688 for(i = 0; i < losl; i++) 4781 4689 { 4782 4690 los[i].sev = pGetShortExpVector (los[i].p); 4783 4691 //SetShortExpVector(); 4784 4692 los[i].p = kBucketGetLm (los[i].bucket); 4785 if 4693 if(los[i].initial_quality > max_initial_quality) 4786 4694 max_initial_quality = los[i].initial_quality; 4787 4695 // else … … 4794 4702 // nicht reduzierbare eintrᅵe in ergebnisliste schreiben 4795 4703 // nullen loeschen 4796 while 4797 { 4798 if 4799 4704 while(curr_pos >= 0) 4705 { 4706 if((c->use_noro_last_block) 4707 && (lies_in_last_dp_block (los[curr_pos].p, c))) 4800 4708 { 4801 4709 int pn_noro = curr_pos + 1; 4802 4710 poly *p_noro = (poly *) omalloc (pn_noro * sizeof (poly)); 4803 for 4804 { 4805 4806 4807 4808 4809 4810 } 4811 if 4812 { 4813 4711 for(i = 0; i < pn_noro; i++) 4712 { 4713 int dummy_len; 4714 poly p; 4715 los[i].p = NULL; 4716 kBucketClear (los[i].bucket, &p, &dummy_len); 4717 p_noro[i] = p; 4718 } 4719 if(npPrimeM < 255) 4720 { 4721 noro_step < tgb_uint8 > (p_noro, pn_noro, c); 4814 4722 } 4815 4723 else 4816 4724 { 4817 if(npPrimeM < 65000)4818 4819 4820 4821 4822 4823 4824 4825 } 4826 for 4827 { 4828 4829 4830 4831 4725 if(npPrimeM < 65000) 4726 { 4727 noro_step < tgb_uint16 > (p_noro, pn_noro, c); 4728 } 4729 else 4730 { 4731 noro_step < tgb_uint32 > (p_noro, pn_noro, c); 4732 } 4733 } 4734 for(i = 0; i < pn_noro; i++) 4735 { 4736 los[i].p = p_noro[i]; 4737 los[i].sev = pGetShortExpVector (los[i].p); 4738 //ignore quality 4739 kBucketInit (los[i].bucket, los[i].p, pLength (los[i].p)); 4832 4740 } 4833 4741 qsort (los, pn_noro, sizeof (red_object), red_object_better_gen); 4834 4742 int deleted = 4835 4743 multi_reduction_clear_zeroes (los, losl, pn_noro, curr_pos); 4836 4744 losl -= deleted; 4837 4745 curr_pos -= deleted; … … 4840 4748 find_erg erg; 4841 4749 4842 multi_reduction_find (los, losl, c, curr_pos, erg); 4843 if 4750 multi_reduction_find (los, losl, c, curr_pos, erg); //last argument should be curr_pos 4751 if(erg.reduce_by < 0) 4844 4752 break; 4845 4753 … … 4854 4762 4855 4763 4856 if (!TEST_OPT_REDTHROUGH) 4857 { 4858 for (i = erg.to_reduce_l; i <= erg.to_reduce_u; i++) 4859 { 4860 if (los[i].p != NULL) //the check (los[i].p!=NULL) might be invalid 4861 { 4862 // 4863 assume (los[i].initial_quality > 0); 4864 if (los[i].guess_quality (c) 4865 > 1.5 * delay_factor * max_initial_quality) 4866 { 4867 if (TEST_OPT_PROT) 4868 PrintS ("v"); 4869 los[i].canonicalize (); 4870 if (los[i].guess_quality (c) > delay_factor * max_initial_quality) 4871 { 4872 if (TEST_OPT_PROT) 4873 PrintS ("."); 4874 los[i].clear_to_poly (); 4875 //delay.push_back(los[i].p); 4876 delay[delay_s] = los[i].p; 4877 delay_s++; 4878 los[i].p = NULL; 4879 } 4880 } 4881 } 4882 } 4883 } 4884 int deleted = 4885 multi_reduction_clear_zeroes (los, losl, erg.to_reduce_l, 4886 erg.to_reduce_u); 4887 if (erg.fromS == FALSE) 4764 if(!TEST_OPT_REDTHROUGH) 4765 { 4766 for(i = erg.to_reduce_l; i <= erg.to_reduce_u; i++) 4767 { 4768 if(los[i].p != NULL) //the check (los[i].p!=NULL) might be invalid 4769 { 4770 // 4771 assume (los[i].initial_quality > 0); 4772 if(los[i].guess_quality (c) 4773 > 1.5 * delay_factor * max_initial_quality) 4774 { 4775 if(TEST_OPT_PROT) 4776 PrintS ("v"); 4777 los[i].canonicalize (); 4778 if(los[i].guess_quality (c) > delay_factor * max_initial_quality) 4779 { 4780 if(TEST_OPT_PROT) 4781 PrintS ("."); 4782 los[i].clear_to_poly (); 4783 //delay.push_back(los[i].p); 4784 delay[delay_s] = los[i].p; 4785 delay_s++; 4786 los[i].p = NULL; 4787 } 4788 } 4789 } 4790 } 4791 } 4792 int deleted = multi_reduction_clear_zeroes (los, losl, erg.to_reduce_l, 4793 erg.to_reduce_u); 4794 if(erg.fromS == FALSE) 4888 4795 curr_pos = si_max (erg.to_reduce_u, erg.reduce_by); 4889 4796 else … … 4893 4800 4894 4801 //Print("deleted %i \n",deleted); 4895 if 4802 if((TEST_V_UPTORADICAL) && (!(erg.fromS))) 4896 4803 sort_region_down (los, si_min (erg.to_reduce_l, erg.reduce_by), 4897 4898 4804 (si_max (erg.to_reduce_u, erg.reduce_by)) - deleted, 4805 c); 4899 4806 else 4900 4807 sort_region_down (los, erg.to_reduce_l, erg.to_reduce_u - deleted, c); 4901 4808 4902 if 4809 if(erg.expand) 4903 4810 { 4904 4811 #ifdef FIND_DETERMINISTIC 4905 4812 int i; 4906 for (i = 0; c->expandS[i]; i++);4813 for(i = 0; c->expandS[i]; i++) ; 4907 4814 c->expandS = (poly *) omrealloc (c->expandS, (i + 2) * sizeof (poly)); 4908 4815 c->expandS[i] = erg.expand; … … 4910 4817 #else 4911 4818 int ecart = 0; 4912 if 4913 { 4914 4915 4819 if(c->eliminationProblem) 4820 { 4821 ecart = 4822 c->pTotaldegree_full (erg.expand) - c->pTotaldegree (erg.expand); 4916 4823 } 4917 4824 add_to_reductors (c, erg.expand, erg.expand_length, ecart); … … 4952 4859 } 4953 4860 4954 void 4955 red_object::flatten () 4861 void red_object::flatten () 4956 4862 { 4957 4863 assume (p == kBucketGetLm (bucket)); 4958 4864 } 4959 4865 4960 void 4961 red_object::validate () 4866 void red_object::validate () 4962 4867 { 4963 4868 p = kBucketGetLm (bucket); 4964 if 4869 if(p) 4965 4870 sev = pGetShortExpVector (p); 4966 4871 } 4967 4872 4968 int 4969 red_object::clear_to_poly () 4873 int red_object::clear_to_poly () 4970 4874 { 4971 4875 flatten (); … … 4975 4879 } 4976 4880 4977 void 4978 reduction_step::reduce (red_object * r, int l, int u) 4979 { 4980 } 4981 4982 void 4983 simple_reducer::do_reduce (red_object & ro) 4881 void reduction_step::reduce (red_object * r, int l, int u) 4882 { 4883 } 4884 4885 void simple_reducer::do_reduce (red_object & ro) 4984 4886 { 4985 4887 number coef; 4986 4888 #ifdef HAVE_PLURAL 4987 if 4889 if(c->nc) 4988 4890 nc_BucketPolyRed_Z (ro.bucket, p, &coef); 4989 4891 else … … 4993 4895 } 4994 4896 4995 void 4996 simple_reducer::reduce (red_object * r, int l, int u) 4897 void simple_reducer::reduce (red_object * r, int l, int u) 4997 4898 { 4998 4899 this->pre_reduce (r, l, u); … … 5000 4901 //debug start 5001 4902 5002 if 4903 if(c->eliminationProblem) 5003 4904 { 5004 4905 assume (p_LmEqual (r[l].p, r[u].p, c->r)); … … 5007 4908 } 5008 4909 5009 for 4910 for(i = l; i <= u; i++) 5010 4911 { 5011 4912 this->do_reduce (r[i]); 5012 if 4913 if(c->eliminationProblem) 5013 4914 { 5014 4915 r[i].sugar = si_max (r[i].sugar, reducer_deg); 5015 4916 } 5016 4917 } 5017 for 4918 for(i = l; i <= u; i++) 5018 4919 { 5019 4920 kBucketSimpleContent (r[i].bucket); … … 5030 4931 simple_reducer::~simple_reducer () 5031 4932 { 5032 if 4933 if(fill_back != NULL) 5033 4934 { 5034 4935 kBucketInit (fill_back, p, p_len); … … 5037 4938 } 5038 4939 5039 void 5040 multi_reduce_step (find_erg & erg, red_object * r, slimgb_alg * c) 4940 void multi_reduce_step (find_erg & erg, red_object * r, slimgb_alg * c) 5041 4941 { 5042 4942 static int id = 0; … … 5049 4949 simple_reducer *pointer; 5050 4950 BOOLEAN work_on_copy = FALSE; 5051 if 4951 if(erg.fromS) 5052 4952 { 5053 4953 red = c->strat->S[rn]; … … 5060 4960 kBucketClear (r[rn].bucket, &red, &red_len); 5061 4961 5062 if 5063 { 5064 p_Cleardenom (red, c->r); 4962 if(!rField_is_Zp (c->r)) 4963 { 4964 p_Cleardenom (red, c->r); //should be unnecessary 5065 4965 //p_Content(red, c->r); 5066 4966 } 5067 4967 pNormalize (red); 5068 if 4968 if(c->eliminationProblem) 5069 4969 { 5070 4970 r[rn].sugar = c->pTotaldegree_full (red); 5071 4971 } 5072 4972 5073 if 5074 { 5075 if 5076 4973 if((!(erg.fromS)) && (TEST_V_UPTORADICAL)) 4974 { 4975 if(polynomial_root (red, c->r)) 4976 lt_changed = TRUE; 5077 4977 sev = p_GetShortExpVector (red, c->r); 5078 4978 } 5079 4979 red_len = pLength (red); 5080 4980 } 5081 if 5082 4981 if(((TEST_V_MODPSOLVSB) && (red_len > 1)) 4982 || ((c->nc) || (erg.to_reduce_u - erg.to_reduce_l > 5))) 5083 4983 { 5084 4984 work_on_copy = TRUE; … … 5087 4987 pSetCoeff (m, nInit (1)); 5088 4988 pSetComp (m, 0); 5089 for 4989 for(int i = 1; i <= pVariables; i++) 5090 4990 pSetExp (m, i, (pGetExp (r[erg.to_reduce_l].p, i) - pGetExp (red, i))); 5091 4991 pSetm (m); 5092 4992 poly red_cp; 5093 4993 #ifdef HAVE_PLURAL 5094 if 4994 if(c->nc) 5095 4995 red_cp = nc_mm_Mult_pp (m, red, c->r); 5096 4996 else 5097 4997 #endif 5098 4998 red_cp = ppMult_mm (red, m); 5099 if 4999 if(!erg.fromS) 5100 5000 { 5101 5001 kBucketInit (r[rn].bucket, red, red_len); … … 5104 5004 //static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) 5105 5005 5106 if 5006 if(!c->nc) 5107 5007 redTailShort (red_cp, c->strat); 5108 5008 //number mul; … … 5120 5020 5121 5021 int reducer_deg = 0; 5122 if 5022 if(c->eliminationProblem) 5123 5023 { 5124 5024 int lm_deg = c->pTotaldegree (r[erg.to_reduce_l].p); 5125 5025 int ecart; 5126 if 5026 if(erg.fromS) 5127 5027 { 5128 5028 ecart = c->strat->ecartS[erg.reduce_by]; … … 5136 5036 pointer = new simple_reducer (red, red_len, reducer_deg, c); 5137 5037 5138 if 5038 if((!work_on_copy) && (!erg.fromS)) 5139 5039 pointer->fill_back = r[rn].bucket; 5140 5040 else … … 5144 5044 5145 5045 pointer->reduce (r, erg.to_reduce_l, erg.to_reduce_u); 5146 if 5046 if(work_on_copy) 5147 5047 pDelete (&pointer->p); 5148 5048 delete pointer; 5149 if 5049 if(lt_changed) 5150 5050 { 5151 5051 assume (!erg.fromS); … … 5154 5054 } 5155 5055 5156 void 5157 simple_reducer::pre_reduce (red_object * r, int l, int u) 5158 { 5159 } 5056 void simple_reducer::pre_reduce (red_object * r, int l, int u) 5057 { 5058 }
Note: See TracChangeset
for help on using the changeset viewer.