Changeset 2fc974 in git
- Timestamp:
- Apr 12, 2011, 2:40:17 PM (12 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
- Children:
- c385d40ef3a9c855b644be8fed2928f6eedc7be1
- Parents:
- a64791477ec20b2ed1ff3c7042d7f2dc9c892600
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/tgb.cc
ra647914 r2fc974 11 11 //#include <vector> 12 12 //using namespace std; 13 14 13 15 14 ///@TODO: delay nur auf Sugarvergr?erung … … 69 68 } 70 69 } 71 static BOOLEAN monomial_root(poly m, ring r){ 70 static BOOLEAN monomial_root(poly m, ring r) 71 { 72 72 BOOLEAN changed=FALSE; 73 73 int i; 74 for(i=1;i<=rVar(r);i++){ 74 for(i=1;i<=rVar(r);i++) 75 { 75 76 int e=p_GetExp(m,i,r); 76 if (e>1){ 77 if (e>1) 78 { 77 79 p_SetExp(m,i,1,r); 78 80 changed=TRUE; … … 84 86 return changed; 85 87 } 86 static BOOLEAN polynomial_root(poly h, ring r){ 88 static BOOLEAN polynomial_root(poly h, ring r) 89 { 87 90 poly got=gcd_of_terms(h,r); 88 91 BOOLEAN changed=FALSE; … … 95 98 poly div_by=pDivide(copy, got); 96 99 poly iter=h; 97 while(iter){ 100 while(iter) 101 { 98 102 pExpVectorSub(iter,div_by); 99 103 pIter(iter); … … 127 131 //die meisten Varianten stossen sich an coef_buckets 128 132 129 130 131 133 #ifdef LEN_VAR1 132 134 // erste Variante: Laenge: Anzahl der Monome … … 156 158 #endif 157 159 158 159 160 161 162 163 int QlogSize(number n){ 164 165 if (SR_HDL(n) & SR_INT){ 160 int QlogSize(number n) 161 { 162 if (SR_HDL(n) & SR_INT) 163 { 166 164 long i=SR_TO_INT(n); 167 165 if (i==0) return 0; … … 181 179 } 182 180 183 184 181 #ifdef LEN_VAR3 185 182 static inline wlen_type pSLength(poly p,int l) … … 187 184 wlen_type c; 188 185 number coef=pGetCoeff(p); 189 if (rField_is_Q(currRing)){ 186 if (rField_is_Q(currRing)) 187 { 190 188 c=QlogSize(coef); 191 189 } … … 194 192 if (!(TEST_V_COEFSTRAT)) 195 193 return (wlen_type)c*(wlen_type)l /*pLength(p)*/; 196 else { 194 else 195 { 197 196 wlen_type res=l; 198 197 res*=c; … … 213 212 coef=pGetCoeff(lm); 214 213 //c=nSize(pGetCoeff(lm)); 215 if (rField_is_Q(currRing)){ 214 if (rField_is_Q(currRing)) 215 { 216 216 c=QlogSize(coef); 217 217 } … … 227 227 #ifdef HAVE_COEF_BUCKETS 228 228 assume(b->buckets[0]==kBucketGetLm(b)); 229 if (b->coef[0]!=NULL){ 230 231 if (rField_is_Q(currRing)){ 229 if (b->coef[0]!=NULL) 230 { 231 if (rField_is_Q(currRing)) 232 { 232 233 int modifier=QlogSize(pGetCoeff(b->coef[0])); 233 234 c+=modifier; 234 } 235 else{ 235 } 236 else 237 { 236 238 int modifier=nSize(pGetCoeff(b->coef[0])); 237 c*=modifier;} 238 } 239 c*=modifier; 240 } 241 } 239 242 #endif 240 if (!(TEST_V_COEFSTRAT)){ 241 return s*c; 242 } else 243 if (!(TEST_V_COEFSTRAT)) 244 { 245 return s*c; 246 } 247 else 243 248 { 244 249 wlen_type res=s; … … 254 259 int c; 255 260 number coef=pGetCoeff(p); 256 if (rField_is_Q(currRing)){ 261 if (rField_is_Q(currRing)) 262 { 257 263 c=QlogSize(coef); 258 264 } … … 278 284 coef=pGetCoeff(lm); 279 285 //c=nSize(pGetCoeff(lm)); 280 if (rField_is_Q(currRing)){ 286 if (rField_is_Q(currRing)) 287 { 281 288 c=QlogSize(coef); 282 289 } … … 292 299 #ifdef HAVE_COEF_BUCKETS 293 300 assume(b->buckets[0]==kBucketGetLm(b)); 294 if (b->coef[0]!=NULL){ 295 296 if (rField_is_Q(currRing)){ 301 if (b->coef[0]!=NULL) 302 { 303 if (rField_is_Q(currRing)) 304 { 297 305 int modifier=QlogSize(pGetCoeff(b->coef[0])); 298 306 c+=modifier; 299 } 300 else{ 307 } 308 else 309 { 301 310 int modifier=nSize(pGetCoeff(b->coef[0])); 302 311 c*=modifier;} … … 334 343 #endif 335 344 //BUG/TODO this stuff will fail on internal Schreyer orderings 336 static BOOLEAN elength_is_normal_length(poly p, slimgb_alg* c){ 345 static BOOLEAN elength_is_normal_length(poly p, slimgb_alg* c) 346 { 337 347 ring r=c->r; 338 348 if (p_GetComp(p,r)!=0) return FALSE; 339 if (c->lastDpBlockStart<=pVariables){ 349 if (c->lastDpBlockStart<=pVariables) 350 { 340 351 int i; 341 for(i=1;i<c->lastDpBlockStart;i++){ 342 if (p_GetExp(p,i,r)!=0){ 352 for(i=1;i<c->lastDpBlockStart;i++) 353 { 354 if (p_GetExp(p,i,r)!=0) 355 { 343 356 break; 344 357 } … … 350 363 } 351 364 else return FALSE; 352 }else 365 } 366 else 353 367 return FALSE; 354 368 } 355 369 356 static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg* c){ 370 static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg* c) 371 { 357 372 ring r=c->r; 358 373 if (p_GetComp(p,r)!=0) return FALSE; 359 if (c->lastDpBlockStart<=pVariables){ 374 if (c->lastDpBlockStart<=pVariables) 375 { 360 376 int i; 361 for(i=1;i<c->lastDpBlockStart;i++){ 362 if (p_GetExp(p,i,r)!=0){ 377 for(i=1;i<c->lastDpBlockStart;i++) 378 { 379 if (p_GetExp(p,i,r)!=0) 380 { 363 381 break; 364 382 } … … 370 388 } 371 389 else return FALSE; 372 }else 390 } 391 else 373 392 return FALSE; 374 393 } 375 394 376 static int get_last_dp_block_start(ring r){ 395 static int get_last_dp_block_start(ring r) 396 { 377 397 //ring r=c->r; 378 398 int last_block; 379 399 380 if (rRing_has_CompLastBlock(r)){ 400 if (rRing_has_CompLastBlock(r)) 401 { 381 402 last_block=rBlocks(r) - 3; 382 403 } 383 else {last_block=rBlocks(r)-2;} 404 else 405 {last_block=rBlocks(r)-2;} 384 406 assume(last_block>=0); 385 407 if (r->order[last_block]==ringorder_dp) 386 408 return r->block0[last_block]; 387 409 return pVariables+1; 388 389 } 390 391 static wlen_type do_pELength(poly p, slimgb_alg* c, int dlm=-1){ 392 410 } 411 412 static wlen_type do_pELength(poly p, slimgb_alg* c, int dlm=-1) 413 { 393 414 if(p==NULL) return 0; 394 415 wlen_type s=0; 395 416 poly pi=p; 396 if(dlm<0){ 417 if(dlm<0) 418 { 397 419 dlm=c->pTotaldegree(p); 398 420 s=1; … … 400 422 } 401 423 402 while(pi){ 424 while(pi) 425 { 403 426 int d=c->pTotaldegree(pi); 404 427 if(d>dlm) … … 411 434 } 412 435 413 wlen_type pELength(poly p, slimgb_alg* c, ring r){ 436 wlen_type pELength(poly p, slimgb_alg* c, ring r) 437 { 414 438 if(p==NULL) return 0; 415 439 wlen_type s=0; 416 440 poly pi=p; 417 441 int dlm; 418 419 420 421 422 423 while(pi){442 dlm=c->pTotaldegree(p); 443 s=1; 444 pi=p->next; 445 446 while(pi) 447 { 424 448 int d=c->pTotaldegree(pi); 425 449 if(d>dlm) … … 435 459 { 436 460 wlen_type s=0; 437 if(lm==NULL){ 461 if(lm==NULL) 462 { 438 463 lm=kBucketGetLm(b); 439 464 } 440 465 if(lm==NULL) return 0; 441 if(elength_is_normal_length(lm,ca)) { 466 if(elength_is_normal_length(lm,ca)) 467 { 442 468 return bucket_guess(b); 443 469 } … … 449 475 #else 450 476 451 452 477 //int d=pTotaldegree(lm,ca->r); 453 478 int i; … … 456 481 if(b->buckets[i]==NULL) continue; 457 482 458 if ((ca->pTotaldegree(b->buckets[i])<=d) &&(elength_is_normal_length(b->buckets[i],ca))){ 483 if ((ca->pTotaldegree(b->buckets[i])<=d) &&(elength_is_normal_length(b->buckets[i],ca))) 484 { 459 485 s+=b->buckets_length[i]; 460 } else 486 } 487 else 461 488 { 462 489 s+=do_pELength(b->buckets[i],ca,d); … … 467 494 } 468 495 469 static inline int pELength(poly p, slimgb_alg* c,int l){ 496 static inline int pELength(poly p, slimgb_alg* c,int l) 497 { 470 498 if (p==NULL) return 0; 471 499 if ((l>0) &&(elength_is_normal_length(p,c))) … … 474 502 } 475 503 476 477 478 479 static inline wlen_type pQuality(poly p, slimgb_alg* c, int l=-1){ 480 504 static inline wlen_type pQuality(poly p, slimgb_alg* c, int l=-1) 505 { 481 506 if(l<0) 482 507 l=pLength(p); 483 508 if(c->isDifficultField) { 484 if(c->eliminationProblem){ 509 if(c->eliminationProblem) 510 { 485 511 wlen_type cs; 486 512 number coef=pGetCoeff(p); 487 if (rField_is_Q(currRing)){ 513 if (rField_is_Q(currRing)) 514 { 488 515 cs=QlogSize(coef); 489 516 } … … 508 535 } 509 536 510 static inline int pTotaldegree_full(poly p){ 537 static inline int pTotaldegree_full(poly p) 538 { 511 539 int r=0; 512 while(p){ 540 while(p) 541 { 513 542 int d=pTotaldegree(p); 514 543 r=si_max(r,d); … … 518 547 } 519 548 520 wlen_type red_object::guess_quality(slimgb_alg* c){ 549 wlen_type red_object::guess_quality(slimgb_alg* c) 550 { 521 551 //works at the moment only for lenvar 1, because in different 522 552 //case, you have to look on coefs 523 553 wlen_type s=0; 524 if (c->isDifficultField){ 554 if (c->isDifficultField) 555 { 525 556 //s=kSBucketLength(bucket,this->p); 526 if(c->eliminationProblem){ 557 if(c->eliminationProblem) 558 { 527 559 wlen_type cs; 528 560 number coef; … … 532 564 533 565 //c=nSize(pGetCoeff(lm)); 534 if (rField_is_Q(currRing)){ 566 if (rField_is_Q(currRing)) 567 { 535 568 cs=QlogSize(coef); 536 569 } … … 538 571 cs=nSize(coef); 539 572 #ifdef HAVE_COEF_BUCKETS 540 if (bucket->coef[0]!=NULL){ 541 if (rField_is_Q(currRing)){ 573 if (bucket->coef[0]!=NULL) 574 { 575 if (rField_is_Q(currRing)) 576 { 542 577 int modifier=QlogSize(pGetCoeff(bucket->coef[0])); 543 578 cs+=modifier; 544 579 } 545 else{ 580 else 581 { 546 582 int modifier=nSize(pGetCoeff(bucket->coef[0])); 547 583 cs*=modifier;} … … 566 602 else s=bucket_guess(bucket); 567 603 } 568 569 604 return s; 570 605 } 571 606 572 573 574 static void finalize_reduction_step(reduction_step* r){ 607 static void finalize_reduction_step(reduction_step* r) 608 { 575 609 delete r; 576 610 } … … 583 617 static int red_object_better_gen(const void* ap, const void* bp) 584 618 { 585 586 587 619 return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p)); 588 620 } 589 621 590 591 static int pLmCmp_func_inverted(const void* ap1, const void* ap2){592 622 static int pLmCmp_func_inverted(const void* ap1, const void* ap2) 623 { 624 poly p1,p2; 593 625 p1=*((poly*) ap1); 594 626 p2=*((poly*)ap2); 595 596 627 return -pLmCmp(p1,p2); 597 628 } 598 629 599 int tgb_pair_better_gen2(const void* ap,const void* bp){ 630 int tgb_pair_better_gen2(const void* ap,const void* bp) 631 { 600 632 return(-tgb_pair_better_gen(ap,bp)); 601 633 } 602 int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){ 634 int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj) 635 { 603 636 int i; 604 637 long not_sev=~obj.sev; 605 638 poly p=obj.p; 606 for(i=0;i<=strat->sl;i++){ 639 for(i=0;i<=strat->sl;i++) 640 { 607 641 if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) 608 642 return i; … … 610 644 return -1; 611 645 } 612 int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev){ 646 int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev) 647 { 613 648 int i; 614 649 long not_sev=~sev; 615 for(i=0;i<=strat->sl;i++){ 650 for(i=0;i<=strat->sl;i++) 651 { 616 652 if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) 617 653 return i; … … 646 682 } 647 683 648 static BOOLEAN ascending(int* i,int top){ 684 static BOOLEAN ascending(int* i,int top) 685 { 649 686 if(top<1) return TRUE; 650 687 if(i[top]<i[top-1]) return FALSE; … … 652 689 } 653 690 654 sorted_pair_node** spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c){ 691 sorted_pair_node** spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c) 692 { 655 693 int i; 656 694 int* a= (int*) omalloc(qn*sizeof(int)); … … 659 697 // for(mc=0;mc<qn;mc++) 660 698 // { 661 662 699 // wrp(q[mc]->lcm_of_lm); 663 700 // PrintS("\n"); … … 666 703 // for(mc=0;mc<pn;mc++) 667 704 // { 668 669 705 // wrp(p[mc]->lcm_of_lm); 670 706 // PrintS("\n"); 671 707 // } 672 708 int lastpos=0; 673 for(i=0;i<qn;i++){ 709 for(i=0;i<qn;i++) 710 { 674 711 lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0)); 675 712 // cout<<lastpos<<"\n"; 676 713 a[i]=lastpos; 677 678 }679 if((pn+qn)>c->max_pairs){714 } 715 if((pn+qn)>c->max_pairs) 716 { 680 717 p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*)); 681 718 c->max_pairs=2*(pn+qn); 682 719 } 683 for(i=qn-1;i>=0;i--){ 720 for(i=qn-1;i>=0;i--) 721 { 684 722 size_t size; 685 723 if(qn-1>i) … … 694 732 } 695 733 696 697 static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c){ 698 699 734 static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c) 735 { 700 736 poly p1=c->S->m[pos1]; 701 737 poly p2=c->S->m[pos2]; 702 703 738 704 739 if (pGetComp(p1) > 0 || pGetComp(p2) > 0) … … 710 745 711 746 if((gcd1!=NULL) && (gcd2!=NULL)) 712 { 713 gcd1->next=gcd2; //may ordered incorrect 714 m=gcd_of_terms(gcd1,c->r); 715 gcd1->next=NULL; 716 717 } 718 747 { 748 gcd1->next=gcd2; //may ordered incorrect 749 m=gcd_of_terms(gcd1,c->r); 750 gcd1->next=NULL; 751 } 719 752 if (m==NULL) 720 753 { … … 722 755 { 723 756 if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; 724 if (i == pVariables){ 757 if (i == pVariables) 758 { 725 759 //PrintS("trivial"); 726 760 return TRUE; … … 736 770 pDelete(&m); 737 771 return FALSE;} 738 if (i == pVariables){ 772 if (i == pVariables) 773 { 739 774 pDelete(&m); 740 775 //PrintS("trivial"); … … 744 779 } 745 780 } 746 747 748 749 750 781 } 751 782 752 783 //! returns position sets w as weight 753 int find_best(red_object* r,int l, int u, wlen_type &w, slimgb_alg* c){ 784 int find_best(red_object* r,int l, int u, wlen_type &w, slimgb_alg* c) 785 { 754 786 int best=l; 755 787 int i; 756 788 w=r[l].guess_quality(c); 757 for(i=l+1;i<=u;i++){ 789 for(i=l+1;i<=u;i++) 790 { 758 791 wlen_type w2=r[i].guess_quality(c); 759 if(w2<w){ 792 if(w2<w) 793 { 760 794 w=w2; 761 795 best=i; 762 796 } 763 764 797 } 765 798 return best; 766 799 } 767 800 768 769 void red_object::canonicalize(){801 void red_object::canonicalize() 802 { 770 803 kBucketCanonicalize(bucket); 771 772 773 } 774 BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c){804 } 805 806 BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c) 807 { 775 808 assume(i>=0); 776 809 assume(j>=0); … … 787 820 //p_Delete(&lm,c->r); 788 821 789 790 for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ 791 if (i_con[n]==j){ 822 for (int n=0;((n<c->n) && (i_con[n]>=0));n++) 823 { 824 if (i_con[n]==j) 825 { 792 826 now_t_rep(i,j,c); 793 827 omfree(i_con); 794 795 828 return TRUE; 796 829 } … … 800 833 return FALSE; 801 834 } 802 BOOLEAN lenS_correct(kStrategy strat){ 835 BOOLEAN lenS_correct(kStrategy strat) 836 { 803 837 int i; 804 for(i=0;i<=strat->sl;i++){ 838 for(i=0;i<=strat->sl;i++) 839 { 805 840 if (strat->lenS[i]!=pLength(strat->S[i])) 806 841 return FALSE; … … 841 876 } 842 877 } 843 static int bucket_guess(kBucket* bucket){ 878 static int bucket_guess(kBucket* bucket) 879 { 844 880 int sum=0; 845 881 int i; 846 for (i=bucket->buckets_used;i>=0;i--){ 882 for (i=bucket->buckets_used;i>=0;i--) 883 { 847 884 if(bucket->buckets[i]) 848 885 sum+=bucket->buckets_length[i]; … … 850 887 return sum; 851 888 } 852 853 854 855 856 857 889 858 890 static int add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified) … … 888 920 c->strat->enterS(P,i,c->strat,-1); 889 921 890 891 892 922 c->strat->lenS[i]=len; 893 923 assume(pLength(c->strat->S[i])==c->strat->lenS[i]); … … 896 926 897 927 return i; 898 899 } 928 } 929 900 930 static void length_one_crit(slimgb_alg* c, int pos, int len) 901 931 { … … 910 940 c->states[pos][i]=HASTREP; 911 941 } 912 for ( i=pos+1;i<c->n;i++){ 942 for ( i=pos+1;i<c->n;i++) 943 { 913 944 if (c->lengths[i]==1) 914 945 c->states[i][pos]=HASTREP; … … 918 949 } 919 950 } 920 921 951 922 952 static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat) … … 1010 1040 int pos; 1011 1041 1012 while(TRUE){ 1013 if ((con_checked<connected_length)&& (not_yet_found>0)){ 1042 while(TRUE) 1043 { 1044 if ((con_checked<connected_length)&& (not_yet_found>0)) 1045 { 1014 1046 pos=connected[con_checked]; 1015 for(int i=0;i<cans_length;i++){ 1047 for(int i=0;i<cans_length;i++) 1048 { 1016 1049 if (cans[i]<0) continue; 1017 1050 //FIXME: triv. syz. does not hold on noncommutative, check it for modules 1018 1051 if ((has_t_rep(pos,cans[i],c)) ||((!rIsPluralRing(c->r))&&(trivial_syzygie(pos,cans[i],bound,c)))) 1019 1052 { 1020 1021 1053 connected[connected_length]=cans[i]; 1022 1054 connected_length++; … … 1024 1056 --not_yet_found; 1025 1057 1026 if (connected[connected_length-1]==to){ 1027 if (connected_length<c->n){ 1058 if (connected[connected_length-1]==to) 1059 { 1060 if (connected_length<c->n) 1061 { 1028 1062 connected[connected_length]=-1; 1029 1063 } … … 1037 1071 else 1038 1072 { 1039 for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){ 1040 if (last_cans_pos==c->n){ 1041 if (connected_length<c->n){ 1073 for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++) 1074 { 1075 if (last_cans_pos==c->n) 1076 { 1077 if (connected_length<c->n) 1078 { 1042 1079 connected[connected_length]=-1; 1043 1080 } … … 1047 1084 if ((last_cans_pos==from)||(last_cans_pos==to)) 1048 1085 continue; 1049 if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){ 1086 if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)) 1087 { 1050 1088 cans[cans_length]=last_cans_pos; 1051 1089 cans_length++; … … 1054 1092 } 1055 1093 not_yet_found++; 1056 for (int i=0;i<con_checked;i++){ 1057 if (has_t_rep(connected[i],last_cans_pos,c)){ 1058 1094 for (int i=0;i<con_checked;i++) 1095 { 1096 if (has_t_rep(connected[i],last_cans_pos,c)) 1097 { 1059 1098 connected[connected_length]=last_cans_pos; 1060 1099 connected_length++; 1061 1100 cans[cans_length-1]=-1; 1062 1063 1101 --not_yet_found; 1064 if (connected[connected_length-1]==to){ 1065 if (connected_length<c->n){ 1102 if (connected[connected_length-1]==to) 1103 { 1104 if (connected_length<c->n) 1105 { 1066 1106 connected[connected_length]=-1; 1067 1107 } 1068 1069 1108 omfree(cans); 1070 1109 return connected; … … 1075 1114 } 1076 1115 } 1077 if (connected_length<c->n){ 1116 if (connected_length<c->n) 1117 { 1078 1118 connected[connected_length]=-1; 1079 1119 } 1080 1081 1120 omfree(cans); 1082 1121 return connected; … … 1118 1157 int* j_con =make_connections(j,i,lm,c); 1119 1158 1120 // if(c->n>1){ 1159 // if(c->n>1) 1160 // { 1121 1161 // if (i_con[1]>=0) 1122 1162 // i=i_con[1]; 1123 // else { 1163 // else 1164 // { 1124 1165 // if (j_con[1]>=0) 1125 1166 // j=j_con[1]; … … 1127 1168 // } 1128 1169 1129 int sugar=c->pTotaldegree(lm); 1170 int sugar=syz_deg=c->pTotaldegree(lm); 1171 1130 1172 p_Delete(&lm, c->r); 1131 if(c->T_deg_full)//Sugar1132 {1133 int t_i=c->T_deg_full[i]-c->T_deg[i];1134 int t_j=c->T_deg_full[j]-c->T_deg[j];1135 sugar+=si_max(t_i,t_j);1136 //Print("\n max: %d\n",max(t_i,t_j));1137 }1173 if(c->T_deg_full)//Sugar 1174 { 1175 int t_i=c->T_deg_full[i]-c->T_deg[i]; 1176 int t_j=c->T_deg_full[j]-c->T_deg[j]; 1177 sugar+=si_max(t_i,t_j); 1178 //Print("\n max: %d\n",max(t_i,t_j)); 1179 } 1138 1180 1139 1181 for (int m=0;((m<c->n) && (i_con[m]>=0));m++) … … 1146 1188 if (c->weighted_lengths[i_con[m]]<c->weighted_lengths[i]) 1147 1189 i=i_con[m]; 1148 } 1149 for (int m=0;((m<c->n) && (j_con[m]>=0));m++) 1150 { 1151 if (c->T_deg_full!=NULL) 1152 { 1153 int s1=c->T_deg_full[j_con[m]]+syz_deg-c->T_deg[j_con[m]]; 1154 if (s1>sugar) continue; 1155 } 1156 if (c->weighted_lengths[j_con[m]]<c->weighted_lengths[j]) 1157 j=j_con[m]; 1158 } 1159 1160 //can also try dependend search 1190 } 1191 for (int m=0;((m<c->n) && (j_con[m]>=0));m++) 1192 { 1193 if (c->T_deg_full!=NULL) 1194 { 1195 int s1=c->T_deg_full[j_con[m]]+syz_deg-c->T_deg[j_con[m]]; 1196 if (s1>sugar) continue;} 1197 if (c->weighted_lengths[j_con[m]]<c->weighted_lengths[j]) 1198 j=j_con[m]; 1199 } 1200 1201 //can also try dependend search 1161 1202 omfree(i_con); 1162 1203 omfree(j_con); 1163 } 1164 1204 return; 1205 } 1165 1206 1166 1207 static void add_later(poly p, const char* prot, slimgb_alg* c) … … 1168 1209 int i=0; 1169 1210 //check, if it is already in the queue 1170 1171 1211 1172 1212 while(c->add_later->m[i]!=NULL) … … 1182 1222 static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen) 1183 1223 { 1184 1185 1186 1224 if(strat->sl==-1) return 0; 1187 1225 if (strat->lenSw) return pos_helper(strat,p,(wlen_type) wlen,(wlen_set) strat->lenSw,strat->S); 1188 1226 return pos_helper(strat,p,len,strat->lenS,strat->S); 1189 1190 1227 } 1191 1228 … … 1210 1247 } 1211 1248 1212 1213 1214 1249 static int iq_crit(const void* ap,const void* bp) 1215 1250 { … … 1218 1253 assume(a->i>a->j); 1219 1254 assume(b->i>b->j); 1220 1221 1255 1222 1256 if (a->deg<b->deg) return -1; … … 1231 1265 return 0; 1232 1266 } 1233 static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r){ 1267 static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r) 1268 { 1234 1269 if (rField_is_Q(r)) return s1+s2; 1235 1270 else return s1*s2; 1236 1271 } 1237 static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c){ 1272 static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c) 1273 { 1238 1274 if ((c->isDifficultField) && (c->eliminationProblem)) { 1239 1275 int c1=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r); … … 1255 1291 //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+ 1256 1292 // slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r); 1257 if(!(TEST_V_COEFSTRAT)){ 1293 if(!(TEST_V_COEFSTRAT)) 1294 { 1258 1295 wlen_type cs= 1259 1296 coeff_mult_size_estimate( … … 1262 1299 return (wlen_type)(c->lengths[i]+c->lengths[j]-2)* 1263 1300 (wlen_type)cs;} 1264 else { 1301 else 1302 { 1265 1303 1266 1304 wlen_type cs= … … 1293 1331 poly div_by=pDivide(copy, got); 1294 1332 poly iter=h; 1295 while(iter){ 1333 while(iter) 1334 { 1296 1335 pExpVectorSub(iter,div_by); 1297 1336 pIter(iter); … … 1336 1375 //} 1337 1376 //ENLARGE(c->S->m,poly); 1338 1339 1377 } 1340 1378 pEnlargeSet(&c->S->m,c->n-1,1); … … 1348 1386 assume(ecart>=0); 1349 1387 } 1350 1351 1352 1388 c->tmp_pair_lm[i]=pOne_Special(c->r); 1353 1389 1354 1355 1390 c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1356 1357 1391 1358 1392 c->lengths[i]=pLength(h); … … 1364 1398 p_Cleardenom(h, c->r); 1365 1399 //p_Content(h,c->r); //is a duplicate call, but belongs here 1366 1367 1400 } 1368 1401 else … … 1379 1412 1380 1413 c->states.push_back(vector<bool>(i)); 1381 1382 1414 1383 1415 #else … … 1393 1425 1394 1426 #undef ENLARGE 1395 if (p_GetComp(h,currRing)<=c->syz_comp){ 1396 for (j=0;j<i;j++){ 1427 if (p_GetComp(h,currRing)<=c->syz_comp) 1428 { 1429 for (j=0;j<i;j++) 1430 { 1397 1431 1398 1432 … … 1403 1437 p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)); 1404 1438 1405 1406 if (_p_GetComp(c->S->m[i],c->r)!=_p_GetComp(c->S->m[j],c->r)){1439 if (_p_GetComp(c->S->m[i],c->r)!=_p_GetComp(c->S->m[j],c->r)) 1440 { 1407 1441 //c->states[i][j]=UNCALCULATED; 1408 1442 //WARNUNG: be careful 1409 1443 continue; 1410 } else 1411 if ((!c->nc) && (c->lengths[i]==1) && (c->lengths[j]==1)){ 1444 } 1445 else 1446 if ((!c->nc) && (c->lengths[i]==1) && (c->lengths[j]==1)) 1447 { 1412 1448 c->states[i][j]=HASTREP; 1413 1414 } 1449 } 1415 1450 else if (( (!c->nc) || (c->is_homog && rIsSCA(c->r) ) ) && (pHasNotCF(c->S->m[i],c->S->m[j]))) 1416 1451 // else if ((!(c->nc)) && (pHasNotCF(c->S->m[i],c->S->m[j]))) … … 1424 1459 c->states[i][j]=HASTREP; 1425 1460 c->extended_product_crit++; 1426 1427 1461 //PrintS("E"); 1428 1462 } 1429 // if (c->states[i][j]==UNCALCULATED){ 1463 // if (c->states[i][j]==UNCALCULATED) 1464 // { 1430 1465 1431 1466 if ((TEST_V_FINDMONOM) &&(!c->nc)) { 1432 1467 //PrintS("COMMU"); 1433 // if (c->lengths[i]==c->lengths[j]){ 1468 // if (c->lengths[i]==c->lengths[j]) 1469 // { 1434 1470 // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); 1435 // if (short_s==NULL){ 1471 // if (short_s==NULL) 1472 // { 1436 1473 // c->states[i][j]=HASTREP; 1437 // } else 1474 // } 1475 // else 1438 1476 // { 1439 1477 // p_Delete(&short_s, currRing); 1440 1478 // } 1441 1479 // } 1442 if (c->lengths[i]+c->lengths[j]==3){ 1480 if (c->lengths[i]+c->lengths[j]==3) 1481 { 1443 1482 1444 1483 … … 1468 1507 else 1469 1508 { 1470 if (c->strat->lenS[iS]>1){ 1509 if (c->strat->lenS[iS]>1) 1510 { 1471 1511 //PrintS("O"); 1472 1512 if (TRUE) { 1473 1513 c->states[i][j]=HASTREP; 1474 1514 add_later(short_s,"O",c); 1475 } else p_Delete(&short_s,currRing); 1515 } 1516 else p_Delete(&short_s,currRing); 1476 1517 } 1477 1518 else … … 1522 1563 }//if syz_comp end 1523 1564 1524 1525 1526 1527 1565 assume(spc<=i); 1528 1566 //now ideal quotient crit … … 1541 1579 if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm)) 1542 1580 { 1543 1581 break; 1544 1582 } 1545 1583 if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c)) 1546 1584 has=TRUE; 1547 1585 } 1548 1586 upper=upper-1; … … 1592 1630 // Print("i:%d,spc_final:%d",i,spc_final); 1593 1631 1594 1595 1596 1597 1632 assume(spc_final<=spc); 1598 1633 omfree(nodes); … … 1601 1636 add_to_reductors(c, h, c->lengths[c->n-1], ecart,TRUE); 1602 1637 //i=posInS(c->strat,c->strat->sl,h,0 ecart); 1603 if (!(c->nc)){ 1638 if (!(c->nc)) 1639 { 1604 1640 if (c->lengths[c->n-1]==1) 1605 1641 shorten_tails(c,c->S->m[c->n-1]); … … 1656 1692 1657 1693 1658 if(!ip){ 1694 if(!ip) 1695 { 1659 1696 qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2); 1660 1697 … … 1670 1707 return nodes_final; 1671 1708 } 1672 1673 1674 1675 } 1676 1709 } 1677 1710 1678 1711 static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) … … 1758 1791 } 1759 1792 1760 1761 1762 static poly redTailShort(poly h, kStrategy strat){ 1793 static poly redTailShort(poly h, kStrategy strat) 1794 { 1763 1795 if (h==NULL) return NULL;//n_Init(1,currRing); 1764 if (TEST_V_MODPSOLVSB){ 1796 if (TEST_V_MODPSOLVSB) 1797 { 1765 1798 bit_reduce(pNext(h), strat->tailRing); 1766 1799 } … … 1768 1801 int i; 1769 1802 int len=pLength(h); 1770 for(i=0;i<=strat->sl;i++){ 1803 for(i=0;i<=strat->sl;i++) 1804 { 1771 1805 if((strat->lenS[i]>2) || ((strat->lenSw!=NULL) && (strat->lenSw[i]>2))) 1772 1806 break; … … 1775 1809 } 1776 1810 1777 static void line_of_extended_prod(int fixpos,slimgb_alg* c){ 1811 static void line_of_extended_prod(int fixpos,slimgb_alg* c) 1812 { 1778 1813 if (c->gcd_of_terms[fixpos]==NULL) 1779 1814 { … … 1796 1831 } 1797 1832 } 1798 static void c_S_element_changed_hook(int pos, slimgb_alg* c){ 1833 static void c_S_element_changed_hook(int pos, slimgb_alg* c) 1834 { 1799 1835 length_one_crit(c,pos, c->lengths[pos]); 1800 1836 if (!c->nc) … … 1807 1843 poly_tree_node* r; 1808 1844 int n; 1809 poly_tree_node(int sn):l(NULL),r(NULL),n(sn){} 1845 poly_tree_node(int sn):l(NULL),r(NULL),n(sn) 1846 {} 1810 1847 }; 1811 1848 class exp_number_builder{ … … 1814 1851 int n; 1815 1852 int get_n(poly p); 1816 exp_number_builder():top_level(0),n(0){} 1853 exp_number_builder():top_level(0),n(0) 1854 {} 1817 1855 }; 1818 int exp_number_builder::get_n(poly p){ 1856 int exp_number_builder::get_n(poly p) 1857 { 1819 1858 poly_tree_node** node=&top_level; 1820 while(*node!=NULL){ 1859 while(*node!=NULL) 1860 { 1821 1861 int c=pLmCmp(p,(*node)->p); 1822 1862 if (c==0) return (*node)->n; … … 1842 1882 1843 1883 //! obsolete 1844 void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset){ 1884 void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset) 1885 { 1845 1886 if(!k) return; 1846 1887 t2ippa_rec(ip,ia,k->l,offset); … … 1854 1895 1855 1896 //! obsolete 1856 void t2ippa(poly* ip,int* ia,exp_number_builder & e){ 1897 void t2ippa(poly* ip,int* ia,exp_number_builder & e) 1898 { 1857 1899 1858 1900 int o=0; 1859 1901 t2ippa_rec(ip,ia,e.top_level,o); 1860 1902 } 1861 int anti_poly_order(const void* a, const void* b){ 1903 int anti_poly_order(const void* a, const void* b) 1904 { 1862 1905 return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p ); 1863 1906 } 1864 1907 1865 BOOLEAN is_valid_ro(red_object & ro){ 1908 BOOLEAN is_valid_ro(red_object & ro) 1909 { 1866 1910 red_object r2=ro; 1867 1911 ro.validate(); … … 1869 1913 return TRUE; 1870 1914 } 1871 int terms_sort_crit(const void* a, const void* b){ 1915 int terms_sort_crit(const void* a, const void* b) 1916 { 1872 1917 return -pLmCmp(*((poly*) a),*((poly*) b)); 1873 1918 } 1874 static void unify_terms(poly* terms,int & sum){ 1919 static void unify_terms(poly* terms,int & sum) 1920 { 1875 1921 if (sum==0) return; 1876 1922 int last=0; 1877 1923 int curr=1; 1878 while(curr<sum){ 1879 if (!(pLmEqual(terms[curr],terms[last]))){ 1924 while(curr<sum) 1925 { 1926 if (!(pLmEqual(terms[curr],terms[last]))) 1927 { 1880 1928 terms[++last]=terms[curr]; 1881 1929 } … … 1884 1932 sum=last+1; 1885 1933 } 1886 static void export_mat(number* number_array,int pn, int tn,const char* format_str, int mat_nr){ 1934 static void export_mat(number* number_array,int pn, int tn,const char* format_str, int mat_nr) 1935 { 1887 1936 char matname[20]; 1888 1937 sprintf(matname,format_str,mat_nr); … … 1890 1939 int i,j; 1891 1940 fprintf(out,"mat=[\n"); 1892 for(i=0;i<pn;i++){ 1941 for(i=0;i<pn;i++) 1942 { 1893 1943 fprintf(out,"[\n"); 1894 1944 for(j=0;j<tn;j++) … … 1913 1963 #ifdef USE_NORO 1914 1964 #ifndef NORO_CACHE 1915 static void linalg_step_modp(poly *p, poly* p_out, int& pn, poly* terms,int tn, slimgb_alg* c){ 1965 static void linalg_step_modp(poly *p, poly* p_out, int& pn, poly* terms,int tn, slimgb_alg* c) 1966 { 1916 1967 static int export_n=0; 1917 1968 assume(terms[tn-1]!=NULL); … … 1922 1973 number_type* number_array=(number_type*) omalloc(pn*tn*sizeof(number_type)); 1923 1974 int i; 1924 for(i=0;i<array_size;i++){ 1975 for(i=0;i<array_size;i++) 1976 { 1925 1977 number_array[i]=zero; 1926 1978 } 1927 for(i=0;i<pn;i++){ 1979 for(i=0;i<pn;i++) 1980 { 1928 1981 poly h=p[i]; 1929 1982 //int base=tn*i; … … 1939 1992 int act_row=0; 1940 1993 int p_pos=0; 1941 for(i=0;i<pn;i++){ 1994 for(i=0;i<pn;i++) 1995 { 1942 1996 poly h=NULL; 1943 1997 int j; … … 1953 2007 pn=p_pos; 1954 2008 //assert(p_pos==rank) 1955 while(p_pos<pn){ 2009 while(p_pos<pn) 2010 { 1956 2011 p_out[p_pos++]=NULL; 1957 2012 } … … 1962 2017 #endif 1963 2018 #endif 1964 static void mass_add(poly* p, int pn,slimgb_alg* c){ 2019 static void mass_add(poly* p, int pn,slimgb_alg* c) 2020 { 1965 2021 int j; 1966 2022 int* ibuf=(int*) omalloc(pn*sizeof(int)); 1967 2023 sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(pn*sizeof(sorted_pair_node**)); 1968 for(j=0;j<pn;j++){ 2024 for(j=0;j<pn;j++) 2025 { 1969 2026 p_Test(p[j],c->r); 1970 2027 sbuf[j]=add_to_basis_ideal_quotient(p[j],c,ibuf+j); 1971 2028 } 1972 2029 int sum=0; 1973 for(j=0;j<pn;j++){ 2030 for(j=0;j<pn;j++) 2031 { 1974 2032 sum+=ibuf[j]; 1975 2033 } … … 2003 2061 #ifdef NORO_CACHE 2004 2062 #ifndef NORO_NON_POLY 2005 void NoroCache::evaluateRows(){ 2063 void NoroCache::evaluateRows() 2064 { 2006 2065 //after that can evaluate placeholders 2007 2066 int i; 2008 2067 buffer=(number*) omalloc(nIrreducibleMonomials*sizeof(number)); 2009 for(i=0;i<root.branches_len;i++){ 2068 for(i=0;i<root.branches_len;i++) 2069 { 2010 2070 evaluateRows(1,root.branches[i]); 2011 2071 } … … 2013 2073 buffer=NULL; 2014 2074 } 2015 void NoroCache::evaluateRows(int level, NoroCacheNode* node){ 2075 void NoroCache::evaluateRows(int level, NoroCacheNode* node) 2076 { 2016 2077 assume(level>=0); 2017 2078 if (node==NULL) return; 2018 if (level<pVariables){ 2079 if (level<pVariables) 2080 { 2019 2081 int i,sum; 2020 for(i=0;i<node->branches_len;i++){ 2082 for(i=0;i<node->branches_len;i++) 2083 { 2021 2084 evaluateRows(level+1,node->branches[i]); 2022 2085 } 2023 } else { 2086 } 2087 else 2088 { 2024 2089 DataNoroCacheNode* dn=(DataNoroCacheNode*) node; 2025 if (dn->value_len!=backLinkCode){ 2090 if (dn->value_len!=backLinkCode) 2091 { 2026 2092 poly p=dn->value_poly; 2027 2093 #ifndef NORO_SPARSE_ROWS_PRE … … 2034 2100 int idx; 2035 2101 number* a=buffer; 2036 while(p){ 2102 while(p) 2103 { 2037 2104 DataNoroCacheNode* ref=getCacheReference(p); 2038 2105 … … 2054 2121 SparseRow* row=dn->row; 2055 2122 int i=0; 2056 while(p){ 2123 while(p) 2124 { 2057 2125 DataNoroCacheNode* ref=getCacheReference(p); 2058 2126 … … 2061 2129 row->idx_array[i]=idx; 2062 2130 row->coef_array[i]=p_GetCoeff(p,currRing); 2063 2064 2131 i++; 2065 2132 pIter(p); 2066 2133 } 2067 if (i!=dn->value_len){ 2134 if (i!=dn->value_len) 2135 { 2068 2136 PrintS("F4 calc wrong, as poly len was wrong\n"); 2069 2137 } 2070 2138 assume(i==dn->value_len); 2071 2139 #endif 2072 2073 2074 2075 } 2076 2077 void NoroCache::evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders){2140 } 2141 } 2142 } 2143 2144 void NoroCache::evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders) 2145 { 2078 2146 int i; 2079 2147 int s=place_holders.size(); 2080 for(i=0;i<s;i++){ 2148 for(i=0;i<s;i++) 2149 { 2081 2150 DataNoroCacheNode* ref=place_holders[i].ref; 2082 2151 number coef=place_holders[i].coef; 2083 if (ref->value_len==backLinkCode){ 2152 if (ref->value_len==backLinkCode) 2153 { 2084 2154 row[ref->term_index]=npAddM(row[ref->term_index],coef); 2085 } else { 2155 } 2156 else 2157 { 2086 2158 #ifndef NORO_SPARSE_ROWS_PRE 2087 2159 DenseRow* ref_row=ref->row; … … 2091 2163 number* my_pos=row+ref_row->begin; 2092 2164 //TODO npisOne distinction 2093 if (!(npIsOne(coef))){ 2094 while(ref_begin!=ref_end){ 2165 if (!(npIsOne(coef))) 2166 { 2167 while(ref_begin!=ref_end) 2168 { 2095 2169 2096 2170 *my_pos=npAddM(*my_pos,npMult(coef,*ref_begin)); … … 2099 2173 } 2100 2174 } 2101 else{ 2102 while(ref_begin!=ref_end){ 2175 else 2176 { 2177 while(ref_begin!=ref_end) 2178 { 2103 2179 2104 2180 *my_pos=npAddM(*my_pos,*ref_begin); … … 2107 2183 } 2108 2184 } 2109 2110 2111 2185 2112 2186 #else … … 2117 2191 int* idx_array=ref_row->idx_array; 2118 2192 number* coef_array=ref_row->coef_array; 2119 for(j=0;j<n;j++){ 2193 for(j=0;j<n;j++) 2194 { 2120 2195 int idx=idx_array[j]; 2121 2196 number ref_coef=coef_array[j]; … … 2125 2200 } 2126 2201 } 2127 2128 2202 } 2129 2203 #endif 2130 2204 2131 2132 2133 2205 //poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c); 2134 2206 2135 2136 2207 #ifndef NORO_NON_POLY 2137 MonRedRes noro_red_mon(poly t, BOOLEAN force_unique, NoroCache* cache,slimgb_alg* c){ 2208 MonRedRes noro_red_mon(poly t, BOOLEAN force_unique, NoroCache* cache,slimgb_alg* c) 2209 { 2138 2210 MonRedRes res_holder; 2139 2211 2140 2212 //wrp(t); 2141 2213 res_holder.changed=TRUE; 2142 if (force_unique){ 2214 if (force_unique) 2215 { 2143 2216 DataNoroCacheNode* ref=cache->getCacheReference(t); 2144 if (ref!=NULL){ 2217 if (ref!=NULL) 2218 { 2145 2219 res_holder.len=ref->value_len; 2146 if (res_holder.len==NoroCache::backLinkCode){ 2220 if (res_holder.len==NoroCache::backLinkCode) 2221 { 2147 2222 res_holder.len=1; 2148 2149 2150 2223 } 2151 2224 res_holder.coef=p_GetCoeff(t,c->r); … … 2157 2230 return res_holder; 2158 2231 } 2159 } else{ 2232 } 2233 else 2234 { 2160 2235 BOOLEAN succ; 2161 2236 poly cache_lookup=cache->lookup(t,succ, res_holder.len);//don't own this yet 2162 if (succ){ 2163 if (cache_lookup==t){ 2237 if (succ) 2238 { 2239 if (cache_lookup==t) 2240 { 2164 2241 //know they are equal 2165 2242 //res_holder.len=1; … … 2212 2289 //p_Delete(&t_copy_mon,c->r); 2213 2290 //res=pMult_nn(res,coef_bak); 2214 2215 2291 res_holder.changed=TRUE; 2216 2292 res_holder.p=res; … … 2219 2295 res_holder.ref=ref; 2220 2296 return res_holder; 2221 2222 } else { 2297 } 2298 else 2299 { 2223 2300 number coef_bak=p_GetCoeff(t,c->r); 2224 2301 number one=npInit(1); 2225 2302 p_SetCoeff(t,one,c->r); 2226 2303 res_holder.len=1; 2227 if (!(force_unique)){ 2304 if (!(force_unique)) 2305 { 2228 2306 res_holder.ref=cache->insert(t,t,res_holder.len); 2229 2307 p_SetCoeff(t,coef_bak,c->r); … … 2237 2315 res_holder.onlyBorrowed=FALSE; 2238 2316 return res_holder; 2239 } else { 2317 } 2318 else 2319 { 2240 2320 res_holder.ref=cache->insertAndTransferOwnerShip(t,c->r); 2241 2321 res_holder.coef=coef_bak; … … 2252 2332 #ifndef NORO_NON_POLY 2253 2333 //len input and out: Idea: reverse addition 2254 poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c){ 2334 poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c) 2335 { 2255 2336 assume(len==pLength(p)); 2256 2337 poly orig_p=p; … … 2265 2346 int unchanged_size=0; 2266 2347 2267 while(p){ 2348 while(p) 2349 { 2268 2350 poly t=p; 2269 2351 pIter(p); … … 2273 2355 #endif 2274 2356 MonRedRes red=noro_red_mon(t,FALSE,cache,c); 2275 if ((!(red.changed))&&(!(red.onlyBorrowed))){ 2357 if ((!(red.changed))&&(!(red.onlyBorrowed))) 2358 { 2276 2359 unchanged_size++; 2277 2360 assume(npIsOne(red.coef)); 2278 2361 assume(p_GetCoeff(red.p,currRing)==coef_debug); 2279 if (unchanged_head){ 2362 if (unchanged_head) 2363 { 2280 2364 pNext(unchanged_tail)=red.p; 2281 2365 pIter(unchanged_tail); 2282 } else{ 2366 } 2367 else 2368 { 2283 2369 unchanged_tail=red.p; 2284 2370 unchanged_head=red.p; 2285 2371 } 2286 } else{ 2372 } 2373 else 2374 { 2287 2375 assume(red.len==pLength(red.p)); 2288 if (red.onlyBorrowed){ 2289 if (npIsOne(red.coef)){ 2376 if (red.onlyBorrowed) 2377 { 2378 if (npIsOne(red.coef)) 2379 { 2290 2380 t=p_Copy(red.p,currRing); 2291 }else 2381 } 2382 else 2292 2383 t=pp_Mult_nn(red.p,red.coef,currRing); 2293 } else { 2384 } 2385 else 2386 { 2294 2387 if (npIsOne(red.coef)) 2295 2388 t=red.p; … … 2305 2398 kBucketClear(bucket,&res,&len); 2306 2399 kBucketDestroy(&bucket); 2307 2308 2309 2310 2311 2400 return res; 2312 2401 } … … 2315 2404 //len input and out: Idea: reverse addition 2316 2405 2317 /*template <class number_type> SparseRow<number_type>* noro_red_to_non_poly(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c){ 2318 if (npPrimeM<255){ 2406 /*template <class number_type> SparseRow<number_type>* noro_red_to_non_poly(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c) 2407 * { 2408 if (npPrimeM<255) 2409 { 2319 2410 return noro_red_to_non_poly_t<tgb_uint8>(p,len,cache,c); 2320 } else { 2321 if (npPrimeM<65000){ 2411 } 2412 else 2413 { 2414 if (npPrimeM<65000) 2415 { 2322 2416 return noro_red_to_non_poly_t<tgb_uint16>(p,len,cache,c); 2323 } else{ 2417 } 2418 else 2419 { 2324 2420 return noro_red_to_non_poly_t<tgb_uint32>(p,len,cache,c); 2325 2421 } … … 2329 2425 //len input and out: Idea: reverse addition 2330 2426 #ifndef NORO_NON_POLY 2331 std::vector<NoroPlaceHolder> noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c){ 2427 std::vector<NoroPlaceHolder> noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c) 2428 { 2332 2429 std::vector<NoroPlaceHolder> res; 2333 while(p){ 2430 while(p) 2431 { 2334 2432 poly t=p; 2335 2433 pIter(p); … … 2351 2449 #endif 2352 2450 2353 2354 2355 2356 2357 2451 #endif 2358 2452 #ifdef USE_NORO 2359 2453 #ifndef NORO_CACHE 2360 void noro_step(poly*p,int &pn,slimgb_alg* c){ 2454 void noro_step(poly*p,int &pn,slimgb_alg* c) 2455 { 2361 2456 poly* reduced=(poly*) omalloc(pn*sizeof(poly)); 2362 2457 int j; … … 2368 2463 NoroCache cache; 2369 2464 #endif 2370 for(j=0;j<pn;j++){ 2465 for(j=0;j<pn;j++) 2466 { 2371 2467 2372 2468 poly h=p[j]; … … 2380 2476 assume(pLength(h)==h_len); 2381 2477 #endif 2382 if (h!=NULL){ 2478 if (h!=NULL) 2479 { 2383 2480 #ifndef NORO_CACHE 2384 2481 … … 2386 2483 h_len=pLength(h); 2387 2484 #endif 2388 2389 2390 2485 reduced[reduced_c]=h; 2391 2486 reduced_len[reduced_c]=h_len; … … 2396 2491 } 2397 2492 int reduced_sum=0; 2398 for(j=0;j<reduced_c;j++){ 2493 for(j=0;j<reduced_c;j++) 2494 { 2399 2495 reduced_sum+=reduced_len[j]; 2400 2496 } 2401 2497 poly* terms=(poly*) omalloc(reduced_sum*sizeof(poly)); 2402 2498 int tc=0; 2403 for(j=0;j<reduced_c;j++){ 2499 for(j=0;j<reduced_c;j++) 2500 { 2404 2501 poly h=reduced[j]; 2405 2502 2406 while(h!=NULL){ 2503 while(h!=NULL) 2504 { 2407 2505 terms[tc++]=h; 2408 2506 pIter(h); … … 2430 2528 #else 2431 2529 2432 2433 2434 2530 #endif 2435 2531 #endif 2436 static void go_on (slimgb_alg* c){ 2532 static void go_on (slimgb_alg* c) 2533 { 2437 2534 //set limit of 1000 for multireductions, at the moment for 2438 2535 //programming reasons … … 2445 2542 int i=0; 2446 2543 c->average_length=0; 2447 for(i=0;i<c->n;i++){ 2544 for(i=0;i<c->n;i++) 2545 { 2448 2546 c->average_length+=c->lengths[i]; 2449 2547 } … … 2459 2557 2460 2558 int curr_deg=-1; 2461 while(i<max_pairs){ 2559 while(i<max_pairs) 2560 { 2462 2561 sorted_pair_node* s=top_pair(c);//here is actually chain criterium done 2463 2562 2464 2465 2563 if (!s) break; 2466 2564 2467 if(curr_deg>=0){ 2565 if(curr_deg>=0) 2566 { 2468 2567 if (s->deg >curr_deg) break; 2469 2568 } … … 2471 2570 else curr_deg=s->deg; 2472 2571 quick_pop_pair(c); 2473 if(s->i>=0){ 2572 if(s->i>=0) 2573 { 2474 2574 //be careful replace_pair use createShortSpoly which is not noncommutative 2475 2575 now_t_rep(s->i,s->j,c); … … 2498 2598 p_Test(h,c->r); 2499 2599 } 2500 else{ 2600 else 2601 { 2501 2602 h=s->lcm_of_lm; 2502 2603 p_Test(h,c->r); … … 2507 2608 int mlen=pLength(h); 2508 2609 p_Test(h,c->r); 2509 if ((!c->nc)&(!(use_noro))){ 2610 if ((!c->nc)&(!(use_noro))) 2611 { 2510 2612 h=redNF2(h,c,mlen,coef,2); 2511 2613 redTailShort(h,c->strat); … … 2517 2619 int len=pLength(h); 2518 2620 p[i]=h; 2519 2520 2621 i++; 2521 2622 } 2522 2623 p[i]=NULL; 2523 2624 // pre_comp(p,i,c); 2524 if(i==0){ 2625 if(i==0) 2626 { 2525 2627 omfree(p); 2526 2628 return; … … 2534 2636 int j; 2535 2637 #ifdef USE_NORO 2536 //if ((!(c->nc))&&(rField_is_Zp(c->r))){ 2537 if (use_noro){ 2638 //if ((!(c->nc))&&(rField_is_Zp(c->r))) 2639 //{ 2640 if (use_noro) 2641 { 2538 2642 int pn=i; 2539 2643 if (pn==0) {omfree(p);return;} 2540 2541 { 2542 2543 if (npPrimeM<255){ 2644 { 2645 if (npPrimeM<255) 2646 { 2544 2647 noro_step<tgb_uint8>(p,pn,c); 2545 } else { 2546 if (npPrimeM<65000){ 2648 } 2649 else 2650 { 2651 if (npPrimeM<65000) 2652 { 2547 2653 noro_step<tgb_uint16>(p,pn,c); 2548 } else{ 2654 } 2655 else 2656 { 2549 2657 noro_step<tgb_uint32>(p,pn,c); 2550 2658 } 2551 2659 } 2552 2553 2554 2555 } 2556 2557 //if (TEST_OPT_PROT){ 2660 } 2661 2662 //if (TEST_OPT_PROT) 2663 //{ 2558 2664 // Print("reported rank:%i\n",pn); 2559 2665 //} … … 2562 2668 return; 2563 2669 /*if (TEST_OPT_PROT) 2564 for(j=0;j<pn;j++){ 2670 for(j=0;j<pn;j++) 2671 { 2565 2672 p_wrp(p[j],c->r); 2566 2673 }*/ … … 2568 2675 #endif 2569 2676 red_object* buf=(red_object*) omalloc(i*sizeof(red_object)); 2570 for(j=0;j<i;j++){ 2677 for(j=0;j<i;j++) 2678 { 2571 2679 p_Test(p[j],c->r); 2572 2680 buf[j].p=p[j]; … … 2574 2682 buf[j].bucket = kBucketCreate(currRing); 2575 2683 p_Test(p[j],c->r); 2576 if (c->eliminationProblem){ 2684 if (c->eliminationProblem) 2685 { 2577 2686 buf[j].sugar=c->pTotaldegree_full(p[j]); 2578 2687 } … … 2596 2705 PrintS("B"); 2597 2706 int e; 2598 for(e=0;e<=c->pair_top;e++){ 2707 for(e=0;e<=c->pair_top;e++) 2708 { 2599 2709 if(c->apairs[e]->i<0) continue; 2600 2710 assume(c->apairs[e]->j>=0); … … 2637 2747 p_Test(p,c->r); 2638 2748 //if (!c->nc) { 2639 if ((c->tailReductions) ||(lies_in_last_dp_block(p,c))){ 2749 if ((c->tailReductions) ||(lies_in_last_dp_block(p,c))) 2750 { 2640 2751 p=redNFTail(p,c->strat->sl,c->strat, 0); 2641 } else { 2752 } 2753 else 2754 { 2642 2755 p=redTailShort(p, c->strat); 2643 2756 } … … 2651 2764 omfree(add_those); 2652 2765 omfree(buf); 2653 2654 2655 2656 2657 2658 2659 2766 2660 2767 if (TEST_OPT_PROT) … … 2668 2775 return; 2669 2776 } 2670 2671 2672 2777 2673 2778 #ifdef REDTAIL_S … … 2720 2825 pTest(strat->S[j]); 2721 2826 #ifdef HAVE_PLURAL 2722 if (nc){ 2827 if (nc) 2828 { 2723 2829 nc_BucketPolyRed_Z(P.bucket, strat->S[j], &coef); 2724 } else 2830 } 2831 else 2725 2832 #endif 2726 2833 coef=kBucketPolyRed(P.bucket,strat->S[j], … … 2780 2887 2781 2888 //transfers ownership of m to mat 2782 void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m){ 2889 void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m) 2890 { 2783 2891 assume(mat->mp[row]==NULL); 2784 2892 mat->mp[row]=m; 2785 2893 #ifdef TGB_DEBUG 2786 2894 mac_poly r=m; 2787 while(r){ 2895 while(r) 2896 { 2788 2897 assume(r->exp<mat->columns); 2789 2898 r=r->next; … … 2791 2900 #endif 2792 2901 } 2793 poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){ 2902 poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index) 2903 { 2794 2904 poly p=NULL; 2795 2905 poly* set_this=&p; … … 2807 2917 } 2808 2918 return p; 2809 2810 } 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 static int poly_crit(const void* ap1, const void* ap2){ 2919 } 2920 2921 static int poly_crit(const void* ap1, const void* ap2) 2922 { 2823 2923 poly p1,p2; 2824 2924 p1=*((poly*) ap1); … … 2833 2933 return 0; 2834 2934 } 2835 void slimgb_alg::introduceDelayedPairs(poly* pa,int s){ 2935 2936 void slimgb_alg::introduceDelayedPairs(poly* pa,int s) 2937 { 2836 2938 if (s==0) return; 2837 2939 sorted_pair_node** si_array=(sorted_pair_node**) omalloc(s* sizeof(sorted_pair_node*)); … … 2857 2959 // c->apairs[n-1-i]=si; 2858 2960 si_array[i]=si; 2859 2860 2961 } 2861 2962 … … 2865 2966 omfree(si_array); 2866 2967 } 2968 2867 2969 slimgb_alg::slimgb_alg(ideal I, int syz_comp,BOOLEAN F4,int deg_pos) 2868 2970 { … … 2932 3034 pair_top=-1; 2933 3035 2934 int nn=IDELEMS(I); 2935 array_lengths=nn; 3036 int n=IDELEMS(I); 3037 array_lengths=n; 3038 2936 3039 2937 3040 i=0; 2938 3041 this->n=0; 2939 T_deg=(int*) omalloc(n n*sizeof(int));3042 T_deg=(int*) omalloc(n*sizeof(int)); 2940 3043 if(eliminationProblem) 2941 T_deg_full=(int*) omalloc(n n*sizeof(int));3044 T_deg_full=(int*) omalloc(n*sizeof(int)); 2942 3045 else 2943 3046 T_deg_full=NULL; 2944 tmp_pair_lm=(poly*) omalloc(n n*sizeof(poly));2945 tmp_spn=(sorted_pair_node**) omalloc(n n*sizeof(sorted_pair_node*));3047 tmp_pair_lm=(poly*) omalloc(n*sizeof(poly)); 3048 tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*)); 2946 3049 lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long)); 2947 3050 #ifdef HEAD_BIN … … 2952 3055 #ifdef USE_STDVECBOOL 2953 3056 #else 2954 h=omalloc(n n*sizeof(char*));3057 h=omalloc(n*sizeof(char*)); 2955 3058 2956 3059 states=(char**) h; … … 2959 3062 h=omalloc(n*sizeof(int)); 2960 3063 lengths=(int*) h; 2961 weighted_lengths=(wlen_type*)omalloc(n n*sizeof(wlen_type));2962 gcd_of_terms=(poly*) omalloc(n n*sizeof(poly));2963 2964 short_Exps=(long*) omalloc(n n*sizeof(long));3064 weighted_lengths=(wlen_type*)omalloc(n*sizeof(wlen_type)); 3065 gcd_of_terms=(poly*) omalloc(n*sizeof(poly)); 3066 3067 short_Exps=(long*) omalloc(n*sizeof(long)); 2965 3068 if (F4_mode) 2966 S=idInit(n n,I->rank);3069 S=idInit(n,I->rank); 2967 3070 else 2968 3071 S=idInit(1,I->rank); … … 2977 3080 strat->enterS = enterSBba; 2978 3081 strat->sl = -1; 2979 i=n n;3082 i=n; 2980 3083 i=1;//some strange bug else 2981 3084 /* initS(c->S,NULL,c->strat); */ … … 2995 3098 strat->lenSw=NULL; 2996 3099 sorted_pair_node* si; 2997 assume(n n>0);3100 assume(n>0); 2998 3101 add_to_basis_ideal_quotient(I->m[0],this,NULL); 2999 3102 … … 3001 3104 if(!(F4_mode)) 3002 3105 { 3003 poly* array_arg=I->m;3004 array_arg++;3005 introduceDelayedPairs(array_arg,n-1);3006 /*3106 poly* array_arg=I->m; 3107 array_arg++; 3108 introduceDelayedPairs(array_arg,n-1); 3109 /* 3007 3110 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis 3008 3111 { … … 3019 3122 si->lcm_of_lm=I->m[i]; 3020 3123 3021 // c->apairs[n n-1-i]=si;3022 apairs[n n-i-1]=si;3124 // c->apairs[n-1-i]=si; 3125 apairs[n-i-1]=si; 3023 3126 ++(pair_top); 3024 } 3025 */ 3127 }*/ 3026 3128 } 3027 3129 else 3028 3130 { 3029 for (i=1;i<n n;i++)//the 1 is wanted, because first element is added to basis3131 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis 3030 3132 add_to_basis_ideal_quotient(I->m[i],this,NULL); 3031 3133 } … … 3052 3154 slimgb_alg::~slimgb_alg() 3053 3155 { 3156 3054 3157 if (!(completed)) 3055 3158 { 3056 poly* add=(poly*) omalloc((pair_top+2)*sizeof(poly)); 3057 int piter; 3058 int pos=0; 3059 for(piter=0;piter<=pair_top;piter++) 3060 { 3061 sorted_pair_node* s=apairs[piter]; 3062 if (s->i<0) 3063 { 3064 //delayed element 3065 if (s->lcm_of_lm!=NULL) 3066 { 3067 add[pos]=s->lcm_of_lm; 3068 pos++; 3159 poly* add=(poly*) omalloc((pair_top+2)*sizeof(poly)); 3160 int piter; 3161 int pos=0; 3162 for(piter=0;piter<=pair_top;piter++) 3163 { 3164 sorted_pair_node* s=apairs[piter]; 3165 if (s->i<0) 3166 { 3167 //delayed element 3168 if (s->lcm_of_lm!=NULL) 3169 { 3170 add[pos]=s->lcm_of_lm; 3171 pos++; 3172 } 3069 3173 } 3070 } 3071 free_sorted_pair_node(s,r); 3072 apairs[piter]=NULL; 3073 } 3074 pair_top=-1; 3075 add[pos]=NULL; 3076 pos=0; 3077 while(add[pos]!=NULL) 3078 { 3079 add_to_basis_ideal_quotient(add[pos],this,NULL); 3080 pos++; 3081 } 3082 for(piter=0;piter<=pair_top;piter++) 3083 { 3084 sorted_pair_node* s=apairs[piter]; 3085 assume(s->i>=0); 3086 free_sorted_pair_node(s,r); 3087 apairs[piter]=NULL; 3088 } 3089 pair_top=-1; 3174 free_sorted_pair_node(s,r); 3175 apairs[piter]=NULL; 3176 } 3177 pair_top=-1; 3178 add[pos]=NULL; 3179 pos=0; 3180 while(add[pos]!=NULL) 3181 { 3182 add_to_basis_ideal_quotient(add[pos],this,NULL); 3183 pos++; 3184 } 3185 for(piter=0;piter<=pair_top;piter++) 3186 { 3187 sorted_pair_node* s=apairs[piter]; 3188 assume(s->i>=0); 3189 free_sorted_pair_node(s,r); 3190 apairs[piter]=NULL; 3191 } 3192 pair_top=-1; 3090 3193 } 3091 3194 id_Delete(&add_later,r); … … 3151 3254 // initsevS(i); 3152 3255 omFree(c->strat->S_2_R); 3256 3257 3153 3258 omFree(c->strat->lenS); 3154 3259 … … 3184 3289 if(!found) pDelete(&c->strat->S[i]); 3185 3290 } 3186 // for(i=0;i<c->n;i++){ 3187 // if (c->rep[i]!=i){ 3188 // // for(j=0;j<=c->strat->sl;j++){ 3189 // // if(c->strat->S[j]==c->S->m[i]){ 3291 // for(i=0;i<c->n;i++) 3292 // { 3293 // if (c->rep[i]!=i) 3294 // { 3295 // // for(j=0;j<=c->strat->sl;j++) 3296 // { 3297 // // if(c->strat->S[j]==c->S->m[i]) 3298 // { 3190 3299 // // c->strat->S[j]=NULL; 3191 3300 // // break; … … 3199 3308 if (completed) 3200 3309 { 3201 3202 3203 3204 3205 3206 3207 3208 3209 3310 for(i=0;i<c->n;i++) 3311 { 3312 assume(c->S->m[i]!=NULL); 3313 if (p_GetComp(c->S->m[i],currRing)>this->syz_comp) continue; 3314 for(j=0;j<c->n;j++) 3315 { 3316 if((c->S->m[j]==NULL)||(i==j)) 3317 continue; 3318 assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], 3210 3319 c->S->m[i],~c->short_Exps[i], 3211 3320 c->r)==p_LmDivisibleBy(c->S->m[j], 3212 3321 c->S->m[i], 3213 3322 c->r)); 3214 3323 if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], 3215 3324 c->S->m[i],~c->short_Exps[i], 3216 3325 c->r)) 3217 3218 3219 3220 3221 3222 3326 { 3327 pDelete(&c->S->m[i]); 3328 break; 3329 } 3330 } 3331 } 3223 3332 } 3224 3333 omfree(c->short_Exps); 3225 3334 3226 3335 ideal I=c->S; 3227 3228 3336 IDELEMS(I)=c->n; 3229 3230 3337 idSkipZeroes(I); 3231 3338 for(i=0;i<=c->strat->sl;i++) … … 3238 3345 ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3239 3346 { 3240 assume(r==currRing); 3241 ring orig_ring=r; 3242 int pos; 3243 ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos); 3244 3245 ideal s_h; 3246 if (orig_ring != new_ring) 3247 { 3248 rChangeCurrRing(new_ring); 3249 s_h=idrCopyR_NoSort(arg_I,orig_ring); 3250 idTest(s_h); 3251 /*int i; 3252 3253 for(i=0;i<IDELEMS(s_h);i++) 3254 { 3255 poly p=s_h->m[i]; 3256 while(p) 3257 { 3347 assume(r==currRing); 3348 ring orig_ring=r; 3349 int pos; 3350 ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos); 3351 ideal s_h; 3352 if (orig_ring != new_ring) 3353 { 3354 rChangeCurrRing(new_ring); 3355 s_h=idrCopyR_NoSort(arg_I,orig_ring); 3356 idTest(s_h); 3357 /*int i; 3358 for(i=0;i<IDELEMS(s_h);i++) 3359 { 3360 poly p=s_h->m[i]; 3361 while(p) 3362 { 3258 3363 p_Setm(p,new_ring); 3259 3364 pIter(p); 3260 } 3261 } 3262 */ 3263 } 3264 else 3265 { 3266 s_h = id_Copy(arg_I,orig_ring); 3267 } 3268 3269 ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos); 3270 ideal result; 3271 if(orig_ring != new_ring) 3272 { 3273 idTest(s_result); 3274 rChangeCurrRing(orig_ring); 3275 result = idrMoveR_NoSort(s_result, new_ring); 3276 3365 } 3366 }*/ 3367 } 3368 else 3369 { 3370 s_h = id_Copy(arg_I,orig_ring); 3371 } 3372 3373 ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos); 3374 ideal result; 3375 if(orig_ring != new_ring) 3376 { 3377 idTest(s_result); 3378 rChangeCurrRing(orig_ring); 3379 result = idrMoveR_NoSort(s_result, new_ring); 3380 3381 idTest(result); 3382 //rChangeCurrRing(new_ring); 3383 rKill(new_ring); 3384 //rChangeCurrRing(orig_ring); 3385 } 3386 else 3387 result=s_result; 3277 3388 idTest(result); 3278 //rChangeCurrRing(new_ring); 3279 rKill(new_ring); 3280 //rChangeCurrRing(orig_ring); 3281 } 3282 else 3283 result=s_result; 3284 idTest(result); 3285 return result; 3286 } 3287 3288 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos){ 3389 return result; 3390 } 3391 3392 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos) 3393 { 3289 3394 // 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))); 3290 3395 … … 3336 3441 return(I); 3337 3442 } 3443 3338 3444 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c) 3339 3445 { … … 3393 3499 { 3394 3500 //enter tail 3501 3395 3502 if (c->S->m[i]==NULL) continue; 3396 3503 poly tail=c->S->m[i]->next; … … 3444 3551 if (c->strat->lenSw) 3445 3552 c->strat->lenSw[old_pos]=q; 3446 3447 3553 if (new_pos<old_pos) 3448 3554 move_forward_in_S(old_pos,new_pos,c->strat); 3449 3450 3555 length_one_crit(c,i,c->lengths[i]); 3451 3556 } 3452 3557 } 3453 3558 } 3559 3454 3560 static sorted_pair_node* pop_pair(slimgb_alg* c) 3455 3561 { … … 3459 3565 else return (c->apairs[c->pair_top--]); 3460 3566 } 3567 3461 3568 void slimgb_alg::cleanDegs(int lower, int upper) 3462 3569 { … … 3474 3581 if (T_deg[i]==deg) 3475 3582 { 3476 poly h;3477 h=S->m[i];3478 h=redNFTail(h,strat->sl,strat,lengths[i]);3479 if (!rField_is_Zp(r))3480 {3481 p_Cleardenom(h,r);3482 //p_Content(h,r);3483 }3484 else pNorm(h);3583 poly h; 3584 h=S->m[i]; 3585 h=redNFTail(h,strat->sl,strat,lengths[i]); 3586 if (!rField_is_Zp(r)) 3587 { 3588 p_Cleardenom(h,r); 3589 //p_Content(h,r); 3590 } 3591 else pNorm(h); 3485 3592 //TODO:GCD of TERMS 3486 poly got=::gcd_of_terms(h,r); 3487 p_Delete(&gcd_of_terms[i],r); 3488 gcd_of_terms[i]=got; 3489 int len=pLength(h); 3490 wlen_type wlen=pQuality(h,this,len); 3491 if (weighted_lengths) 3492 weighted_lengths[i]=wlen; 3493 lengths[i]=len; 3494 assume(h==S->m[i]); 3495 int j; 3496 for(j=0;j<=strat->sl;j++) 3497 { 3498 if (h==strat->S[j]) 3499 { 3500 int new_pos=simple_posInS(strat, h,len, wlen); 3501 if (strat->lenS) 3502 { 3503 strat->lenS[j]=len; 3593 poly got=::gcd_of_terms(h,r); 3594 p_Delete(&gcd_of_terms[i],r); 3595 gcd_of_terms[i]=got; 3596 int len=pLength(h); 3597 wlen_type wlen=pQuality(h,this,len); 3598 if (weighted_lengths) 3599 weighted_lengths[i]=wlen; 3600 lengths[i]=len; 3601 assume(h==S->m[i]); 3602 int j; 3603 for(j=0;j<=strat->sl;j++) 3604 { 3605 if (h==strat->S[j]) 3606 { 3607 int new_pos=simple_posInS(strat, h,len, wlen); 3608 if (strat->lenS) 3609 { 3610 strat->lenS[j]=len; 3611 } 3612 if (strat->lenSw) 3613 { 3614 strat->lenSw[j]=wlen; 3615 } 3616 if (new_pos<j) 3617 { 3618 move_forward_in_S(j,new_pos,strat); 3619 } 3620 else 3621 { 3622 if (new_pos>j) 3623 new_pos=new_pos-1;//is identical with one element 3624 if (new_pos>j) 3625 move_backward_in_S(j,new_pos,strat); 3626 } 3627 break; 3504 3628 } 3505 if (strat->lenSw)3506 {3507 strat->lenSw[j]=wlen;3508 }3509 if (new_pos<j)3510 {3511 move_forward_in_S(j,new_pos,strat);3512 }3513 else3514 {3515 if (new_pos>j)3516 new_pos=new_pos-1;//is identical with one element3517 if (new_pos>j)3518 move_backward_in_S(j,new_pos,strat);3519 }3520 break;3521 3629 } 3522 3630 } 3523 }3524 3631 } 3525 3632 } … … 3531 3638 { 3532 3639 if (T_deg[i]+T_deg[j]<=upper) 3533 3640 { 3534 3641 now_t_rep(i,j,this); 3535 3642 } … … 3540 3647 //TODO mark pairs 3541 3648 } 3649 3542 3650 sorted_pair_node* top_pair(slimgb_alg* c) 3543 3651 { … … 3556 3664 } 3557 3665 } 3666 3558 3667 if(c->pair_top<0) return NULL; 3559 3668 else return (c->apairs[c->pair_top]); 3560 3669 } 3670 3561 3671 sorted_pair_node* quick_pop_pair(slimgb_alg* c) 3562 3672 { … … 3575 3685 } 3576 3686 } 3687 3577 3688 void clean_top_of_pair_list(slimgb_alg* c) 3578 3689 { … … 3583 3694 } 3584 3695 } 3696 3585 3697 static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, slimgb_alg* c) 3586 3698 { … … 3606 3718 omfree(s); 3607 3719 } 3720 3608 3721 static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c) 3609 3722 { … … 3632 3745 if (a->deg>b->deg) return 1; 3633 3746 3634 3747 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); 3635 3748 3636 3749 if (comp==1) return 1; 3637 3750 if (-1==comp) return -1; 3638 if (a->expected_length<b->expected_length) return -1;3751 if (a->expected_length<b->expected_length) return -1; 3639 3752 if (a->expected_length>b->expected_length) return 1; 3640 3753 if (a->i+a->j<b->i+b->j) return -1; 3641 if (a->i+a->j>b->i+b->j) return 1;3754 if (a->i+a->j>b->i+b->j) return 1; 3642 3755 if (a->i<b->i) return -1; 3643 if (a->i>b->i) return 1;3756 if (a->i>b->i) return 1; 3644 3757 return 0; 3645 3758 } … … 3654 3767 for (i=pVariables; i; i--) 3655 3768 { 3656 pSetExp(m,i, pGetExp(p,i)); 3657 if (max_g_0==0) 3658 if (pGetExp(m,i)>0) 3659 max_g_0=i; 3660 } 3769 pSetExp(m,i, pGetExp(p,i)); 3770 if (max_g_0==0) 3771 if (pGetExp(m,i)>0) 3772 max_g_0=i; 3773 } 3774 3661 3775 t=p->next; 3662 3776 while (t!=NULL) … … 3667 3781 pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i))); 3668 3782 if (max_g_0==i) 3669 3670 3783 if (pGetExp(m,i)==0) 3784 max_g_0=0; 3671 3785 if ((max_g_0==0) && (pGetExp(m,i)>0)) 3672 3786 { 3673 3787 max_g_0=i; 3674 3788 } 3675 3789 } … … 3682 3796 return NULL; 3683 3797 } 3798 3684 3799 static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m) 3685 3800 { 3801 3686 3802 if (pGetComp(p1) > 0 || pGetComp(p2) > 0) 3687 3803 return FALSE; … … 3695 3811 } 3696 3812 3697 3698 3813 //for impl reasons may return false if the the normal product criterion matches 3699 3814 static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c) … … 3702 3817 return FALSE; 3703 3818 if(gcd1==NULL) return FALSE; 3704 if(gcd2==NULL) return FALSE; 3705 gcd1->next=gcd2; //may ordered incorrect 3706 poly m=gcd_of_terms(gcd1,c->r); 3707 gcd1->next=NULL; 3708 if (m==NULL) return FALSE; 3709 3710 BOOLEAN erg=pHasNotCFExtended(p1,p2,m); 3711 pDelete(&m); 3712 return erg; 3713 } 3819 if(gcd2==NULL) return FALSE; 3820 gcd1->next=gcd2; //may ordered incorrect 3821 poly m=gcd_of_terms(gcd1,c->r); 3822 gcd1->next=NULL; 3823 if (m==NULL) return FALSE; 3824 3825 BOOLEAN erg=pHasNotCFExtended(p1,p2,m); 3826 pDelete(&m); 3827 return erg; 3828 } 3829 3714 3830 static poly kBucketGcd(kBucket* b, ring r) 3715 3831 { … … 3724 3840 if (!initialized) 3725 3841 { 3726 3727 3728 3842 m=gcd_of_terms(b->buckets[i],r); 3843 initialized=TRUE; 3844 if (m==NULL) return NULL; 3729 3845 } 3730 3846 else 3731 3732 3733 if (n==NULL)3734 {3735 pDelete(&m);3736 return NULL;3737 }3738 n->next=m;3739 poly t=gcd_of_terms(n,r);3740 n->next=NULL;3741 pDelete(&m);3742 pDelete(&n);3743 m=t;3744 if (m==NULL) return NULL; 3745 3847 { 3848 n=gcd_of_terms(b->buckets[i],r); 3849 if (n==NULL) { 3850 pDelete(&m); 3851 return NULL; 3852 } 3853 n->next=m; 3854 poly t=gcd_of_terms(n,r); 3855 n->next=NULL; 3856 pDelete(&m); 3857 pDelete(&n); 3858 m=t; 3859 if (m==NULL) return NULL; 3860 3861 } 3746 3862 } 3747 3863 } … … 3754 3870 return c->strat->lenS[pos]; 3755 3871 } 3872 3756 3873 #ifdef HAVE_PLURAL 3757 3874 static inline wlen_type quality_of_pos_in_strat_S_mult_high(int pos, poly high, slimgb_alg* c) … … 3780 3897 int best=erg.to_reduce_u+1; 3781 3898 /* 3782 for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){ 3899 for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--) 3900 { 3783 3901 int qc=los[i].guess_quality(c); 3784 if (qc<quality_a){ 3902 if (qc<quality_a) 3903 { 3785 3904 best=i; 3786 3905 quality_a=qc; 3787 3906 } 3788 3907 } 3789 if(best!=erg.to_reduce_u+1) {3790 */3908 if(best!=erg.to_reduce_u+1) 3909 {*/ 3791 3910 wlen_type qc; 3792 3911 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3793 3912 if(qc<quality_a) 3794 3913 { 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3914 los[best].flatten(); 3915 int b_pos=kBucketCanonicalize(los[best].bucket); 3916 los[best].p=los[best].bucket->buckets[b_pos]; 3917 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3918 if(qc<quality_a) 3919 { 3920 red_object h=los[erg.to_reduce_u]; 3921 los[erg.to_reduce_u]=los[best]; 3922 los[best]=h; 3923 swap_roles=TRUE; 3924 } 3925 else 3926 swap_roles=FALSE; 3808 3927 } 3809 3928 else 3810 3929 { 3811 swap_roles=FALSE; 3812 } 3930 swap_roles=FALSE; 3931 } 3932 } 3933 else 3934 { 3935 if (erg.to_reduce_u>erg.to_reduce_l) 3936 { 3937 int i; 3938 wlen_type quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); 3939 #ifdef HAVE_PLURAL 3940 if ((c->nc) && (!(rIsSCA(c->r)))) 3941 quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c); 3942 #endif 3943 int best=erg.to_reduce_u+1; 3944 wlen_type qc; 3945 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3946 assume(qc==los[best].guess_quality(c)); 3947 if(qc<quality_a) 3948 { 3949 los[best].flatten(); 3950 int b_pos=kBucketCanonicalize(los[best].bucket); 3951 los[best].p=los[best].bucket->buckets[b_pos]; 3952 qc==pQuality(los[best].bucket->buckets[b_pos],c); 3953 //(best!=erg.to_reduce_u+1) 3954 if(qc<quality_a) 3955 { 3956 red_object h=los[erg.to_reduce_u]; 3957 los[erg.to_reduce_u]=los[best]; 3958 los[best]=h; 3959 erg.reduce_by=erg.to_reduce_u; 3960 erg.fromS=FALSE; 3961 erg.to_reduce_u--; 3962 } 3963 } 3964 } 3965 else 3966 { 3967 assume(erg.to_reduce_u==erg.to_reduce_l); 3968 wlen_type quality_a= 3969 quality_of_pos_in_strat_S(erg.reduce_by,c); 3970 wlen_type qc=los[erg.to_reduce_u].guess_quality(c); 3971 if (qc<0) PrintS("Wrong wlen_type"); 3972 if(qc<quality_a) 3973 { 3974 int best=erg.to_reduce_u; 3975 los[best].flatten(); 3976 int b_pos=kBucketCanonicalize(los[best].bucket); 3977 los[best].p=los[best].bucket->buckets[b_pos]; 3978 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3979 assume(qc>=0); 3980 if(qc<quality_a) 3981 { 3982 BOOLEAN exp=FALSE; 3983 if(qc<=2) 3984 { 3985 //Print("\n qc is %lld \n",qc); 3986 exp=TRUE; 3987 } 3988 else 3989 { 3990 if (qc<quality_a/2) 3991 exp=TRUE; 3992 else 3993 if(erg.reduce_by<c->n/4) 3994 exp=TRUE; 3995 } 3996 if (exp) 3997 { 3998 poly clear_into; 3999 los[erg.to_reduce_u].flatten(); 4000 kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); 4001 erg.expand=pCopy(clear_into); 4002 kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); 4003 if (TEST_OPT_PROT) 4004 PrintS("e"); 4005 } 4006 } 4007 } 4008 } 4009 4010 swap_roles=FALSE; 4011 return; 4012 } 4013 } 4014 else 4015 { 4016 if(erg.reduce_by>erg.to_reduce_u) 4017 { 4018 //then lm(rb)>= lm(tru) so = 4019 assume(erg.reduce_by==erg.to_reduce_u+1); 4020 int best=erg.reduce_by; 4021 wlen_type quality_a=los[erg.reduce_by].guess_quality(c); 4022 wlen_type qc; 4023 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 4024 4025 int i; 4026 if(qc<quality_a) 4027 { 4028 red_object h=los[erg.reduce_by]; 4029 los[erg.reduce_by]=los[best]; 4030 los[best]=h; 4031 } 4032 swap_roles=FALSE; 4033 return; 3813 4034 } 3814 4035 else 3815 4036 { 3816 if (erg.to_reduce_u>erg.to_reduce_l) 3817 { 3818 int i; 3819 wlen_type quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); 3820 #ifdef HAVE_PLURAL 3821 if ((c->nc) && (!(rIsSCA(c->r)))) 3822 quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c); 4037 assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); 4038 assume(erg.to_reduce_u==erg.to_reduce_l); 4039 //further assume, that reduce_by is the above all other polys 4040 //with same leading term 4041 int il=erg.reduce_by; 4042 wlen_type quality_a =los[erg.reduce_by].guess_quality(c); 4043 wlen_type qc; 4044 while((il>0) && pLmEqual(los[il-1].p,los[il].p)) 4045 { 4046 il--; 4047 qc=los[il].guess_quality(c); 4048 if (qc<quality_a) 4049 { 4050 quality_a=qc; 4051 erg.reduce_by=il; 4052 } 4053 } 4054 swap_roles=FALSE; 4055 } 4056 } 4057 if(swap_roles) 4058 { 4059 if (TEST_OPT_PROT) 4060 PrintS("b"); 4061 poly clear_into; 4062 int dummy_len; 4063 int new_length; 4064 int bp=erg.to_reduce_u;//bucket_positon 4065 //kBucketClear(los[bp].bucket,&clear_into,&new_length); 4066 new_length=los[bp].clear_to_poly(); 4067 clear_into=los[bp].p; 4068 poly p=c->strat->S[erg.reduce_by]; 4069 int j=erg.reduce_by; 4070 int old_length=c->strat->lenS[j];// in view of S 4071 los[bp].p=p; 4072 if (c->eliminationProblem) 4073 { 4074 los[bp].sugar=c->pTotaldegree_full(p); 4075 } 4076 kBucketInit(los[bp].bucket,p,old_length); 4077 wlen_type qal=pQuality(clear_into,c,new_length); 4078 int pos_in_c=-1; 4079 int z; 4080 int new_pos; 4081 new_pos=simple_posInS(c->strat,clear_into,new_length, qal); 4082 assume(new_pos<=j); 4083 for (z=c->n;z;z--) 4084 { 4085 if(p==c->S->m[z-1]) 4086 { 4087 pos_in_c=z-1; 4088 break; 4089 } 4090 } 4091 4092 int tdeg_full=-1; 4093 int tdeg=-1; 4094 if(pos_in_c>=0) 4095 { 4096 #ifdef TGB_RESORT_PAIRS 4097 c->used_b=TRUE; 4098 c->replaced[pos_in_c]=TRUE; 4099 #endif 4100 tdeg=c->T_deg[pos_in_c]; 4101 c->S->m[pos_in_c]=clear_into; 4102 c->lengths[pos_in_c]=new_length; 4103 c->weighted_lengths[pos_in_c]=qal; 4104 if (c->gcd_of_terms[pos_in_c]==NULL) 4105 c->gcd_of_terms[pos_in_c]=gcd_of_terms(clear_into,c->r); 4106 if (c->T_deg_full) 4107 tdeg_full=c->T_deg_full[pos_in_c]=c->pTotaldegree_full(clear_into); 4108 else tdeg_full=tdeg; 4109 c_S_element_changed_hook(pos_in_c,c); 4110 } 4111 else 4112 { 4113 if (c->eliminationProblem) 4114 { 4115 tdeg_full=c->pTotaldegree_full(clear_into); 4116 tdeg=c->pTotaldegree(clear_into); 4117 } 4118 } 4119 c->strat->S[j]=clear_into; 4120 c->strat->lenS[j]=new_length; 4121 4122 assume(pLength(clear_into)==new_length); 4123 if(c->strat->lenSw!=NULL) 4124 c->strat->lenSw[j]=qal; 4125 if (!rField_is_Zp(c->r)) 4126 { 4127 p_Cleardenom(clear_into,c->r);//should be unnecessary 4128 //p_Content(clear_into, c->r); 4129 } 4130 else 4131 pNorm(clear_into); 4132 #ifdef FIND_DETERMINISTIC 4133 erg.reduce_by=j; 4134 //resort later see diploma thesis, find_in_S must be deterministic 4135 //during multireduction if spolys are only in the span of the 4136 //input polys 4137 #else 4138 if (new_pos<j) 4139 { 4140 if (c->strat->honey) c->strat->ecartS[j]=tdeg_full-tdeg; 4141 move_forward_in_S(j,new_pos,c->strat); 4142 erg.reduce_by=new_pos; 4143 } 3823 4144 #endif 3824 int best=erg.to_reduce_u+1; 3825 wlen_type qc; 3826 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3827 assume(qc==los[best].guess_quality(c)); 3828 if(qc<quality_a) 3829 { 3830 los[best].flatten(); 3831 int b_pos=kBucketCanonicalize(los[best].bucket); 3832 los[best].p=los[best].bucket->buckets[b_pos]; 3833 qc==pQuality(los[best].bucket->buckets[b_pos],c); 3834 //(best!=erg.to_reduce_u+1) 3835 if(qc<quality_a) 3836 { 3837 red_object h=los[erg.to_reduce_u]; 3838 los[erg.to_reduce_u]=los[best]; 3839 los[best]=h; 3840 erg.reduce_by=erg.to_reduce_u; 3841 erg.fromS=FALSE; 3842 erg.to_reduce_u--; 3843 } 3844 } 3845 } 3846 else 3847 { 3848 assume(erg.to_reduce_u==erg.to_reduce_l); 3849 wlen_type quality_a= 3850 quality_of_pos_in_strat_S(erg.reduce_by,c); 3851 wlen_type qc=los[erg.to_reduce_u].guess_quality(c); 3852 if (qc<0) PrintS("Wrong wlen_type"); 3853 if(qc<quality_a) 3854 { 3855 int best=erg.to_reduce_u; 3856 los[best].flatten(); 3857 int b_pos=kBucketCanonicalize(los[best].bucket); 3858 los[best].p=los[best].bucket->buckets[b_pos]; 3859 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3860 assume(qc>=0); 3861 if(qc<quality_a) 3862 { 3863 BOOLEAN exp=FALSE; 3864 if(qc<=2) 3865 { 3866 //Print("\n qc is %lld \n",qc); 3867 exp=TRUE; 3868 } 3869 else 3870 { 3871 if (qc<quality_a/2) 3872 exp=TRUE; 3873 else 3874 if(erg.reduce_by<c->n/4) 3875 exp=TRUE; 3876 } 3877 if (exp) 3878 { 3879 poly clear_into; 3880 los[erg.to_reduce_u].flatten(); 3881 kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); 3882 erg.expand=pCopy(clear_into); 3883 kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); 3884 if (TEST_OPT_PROT) PrintS("e"); 3885 } 3886 } 3887 } 3888 } 3889 swap_roles=FALSE; 3890 return; 3891 } 3892 } 3893 else 3894 { 3895 if(erg.reduce_by>erg.to_reduce_u) 3896 { 3897 //then lm(rb)>= lm(tru) so = 3898 assume(erg.reduce_by==erg.to_reduce_u+1); 3899 int best=erg.reduce_by; 3900 wlen_type quality_a=los[erg.reduce_by].guess_quality(c); 3901 wlen_type qc; 3902 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3903 3904 int i; 3905 if(qc<quality_a) 3906 { 3907 red_object h=los[erg.reduce_by]; 3908 los[erg.reduce_by]=los[best]; 3909 los[best]=h; 3910 } 3911 swap_roles=FALSE; 3912 return; 3913 } 3914 else 3915 { 3916 assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); 3917 assume(erg.to_reduce_u==erg.to_reduce_l); 3918 //further assume, that reduce_by is the above all other polys 3919 //with same leading term 3920 int il=erg.reduce_by; 3921 wlen_type quality_a =los[erg.reduce_by].guess_quality(c); 3922 wlen_type qc; 3923 while((il>0) && pLmEqual(los[il-1].p,los[il].p)) 3924 { 3925 il--; 3926 qc=los[il].guess_quality(c); 3927 if (qc<quality_a) 3928 { 3929 quality_a=qc; 3930 erg.reduce_by=il; 3931 } 3932 } 3933 swap_roles=FALSE; 3934 } 3935 } 3936 if(swap_roles) 3937 { 3938 if (TEST_OPT_PROT) PrintS("b"); 3939 poly clear_into; 3940 int dummy_len; 3941 int new_length; 3942 int bp=erg.to_reduce_u;//bucket_positon 3943 //kBucketClear(los[bp].bucket,&clear_into,&new_length); 3944 new_length=los[bp].clear_to_poly(); 3945 clear_into=los[bp].p; 3946 poly p=c->strat->S[erg.reduce_by]; 3947 int j=erg.reduce_by; 3948 int old_length=c->strat->lenS[j];// in view of S 3949 los[bp].p=p; 3950 if (c->eliminationProblem) 3951 { 3952 los[bp].sugar=c->pTotaldegree_full(p); 3953 } 3954 kBucketInit(los[bp].bucket,p,old_length); 3955 wlen_type qal=pQuality(clear_into,c,new_length); 3956 int pos_in_c=-1; 3957 int z; 3958 int new_pos; 3959 new_pos=simple_posInS(c->strat,clear_into,new_length, qal); 3960 assume(new_pos<=j); 3961 for (z=c->n;z;z--) 3962 { 3963 if(p==c->S->m[z-1]) 3964 { 3965 pos_in_c=z-1; 3966 break; 3967 } 3968 } 3969 3970 int tdeg_full=-1; 3971 int tdeg=-1; 3972 if(pos_in_c>=0) 3973 { 3974 #ifdef TGB_RESORT_PAIRS 3975 c->used_b=TRUE; 3976 c->replaced[pos_in_c]=TRUE; 3977 #endif 3978 tdeg=c->T_deg[pos_in_c]; 3979 c->S->m[pos_in_c]=clear_into; 3980 c->lengths[pos_in_c]=new_length; 3981 c->weighted_lengths[pos_in_c]=qal; 3982 if (c->gcd_of_terms[pos_in_c]==NULL) 3983 c->gcd_of_terms[pos_in_c]=gcd_of_terms(clear_into,c->r); 3984 if (c->T_deg_full) 3985 tdeg_full=c->T_deg_full[pos_in_c]=c->pTotaldegree_full(clear_into); 3986 else tdeg_full=tdeg; 3987 c_S_element_changed_hook(pos_in_c,c); 3988 } 3989 else 3990 { 3991 if (c->eliminationProblem) 3992 { 3993 tdeg_full=c->pTotaldegree_full(clear_into); 3994 tdeg=c->pTotaldegree(clear_into); 3995 } 3996 } 3997 c->strat->S[j]=clear_into; 3998 c->strat->lenS[j]=new_length; 3999 4000 assume(pLength(clear_into)==new_length); 4001 if(c->strat->lenSw!=NULL) 4002 c->strat->lenSw[j]=qal; 4003 if (!rField_is_Zp(c->r)) 4004 { 4005 p_Cleardenom(clear_into,c->r);//should be unnecessary 4006 //p_Content(clear_into, c->r); 4007 } 4008 else 4009 pNorm(clear_into); 4010 #ifdef FIND_DETERMINISTIC 4011 erg.reduce_by=j; 4012 //resort later see diploma thesis, find_in_S must be deterministic 4013 //during multireduction if spolys are only in the span of the 4014 //input polys 4015 #else 4016 if (new_pos<j) 4017 { 4018 if (c->strat->honey) c->strat->ecartS[j]=tdeg_full-tdeg; 4019 move_forward_in_S(j,new_pos,c->strat); 4020 erg.reduce_by=new_pos; 4021 } 4022 #endif 4023 } 4024 } 4025 static int fwbw(red_object* los, int i){ 4145 } 4146 } 4147 4148 static int fwbw(red_object* los, int i) 4149 { 4026 4150 int i2=i; 4027 4151 int step=1; … … 4047 4171 if ((!incr) &&(step==1)) break; 4048 4172 } 4049 4050 4051 4173 } 4052 4174 else 4053 4175 { 4054 4055 4176 step=si_min(i-i2,step); 4056 4177 if (step==0) break; 4057 4178 i2+=step; 4058 if(pLmEqual(los[i].p,los[i2].p)){ 4179 if(pLmEqual(los[i].p,los[i2].p)) 4180 { 4059 4181 if(step==1) break; 4060 4182 else … … 4063 4185 } 4064 4186 } 4065 4066 4187 } 4067 4188 if (incr) … … 4073 4194 else 4074 4195 step/=2; 4075 4076 4196 } 4077 4197 } 4078 4198 return i2; 4079 4199 } 4080 static void canonicalize_region(red_object* los, int l, int u,slimgb_alg* c){ 4200 4201 static void canonicalize_region(red_object* los, int l, int u,slimgb_alg* c) 4202 { 4081 4203 assume(l<=u+1); 4082 4204 int i; 4083 for(i=l;i<=u;i++){ 4205 for(i=l;i<=u;i++) 4206 { 4084 4207 kBucketCanonicalize(los[i].bucket); 4085 4208 } 4086 4087 } 4088 static void multi_reduction_find(red_object* los, int losl,slimgb_alg* c,int startf,find_erg & erg){4209 } 4210 static void multi_reduction_find(red_object* los, int losl,slimgb_alg* c,int startf,find_erg & erg) 4211 { 4089 4212 kStrategy strat=c->strat; 4090 4213 … … 4094 4217 4095 4218 int j; 4096 while(i>=0){ 4219 while(i>=0) 4220 { 4097 4221 assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0)); 4098 4222 assume(is_valid_ro(los[i])); 4099 4223 assume((!(c->eliminationProblem))||(los[i].sugar>=c->pTotaldegree(los[i].p))); 4100 4224 j=kFindDivisibleByInS_easy(strat,los[i]); 4101 if(j>=0) {4102 4225 if(j>=0) 4226 { 4103 4227 erg.to_reduce_u=i; 4104 4228 erg.reduce_by=j; … … 4109 4233 assume(i>=i2); 4110 4234 4111 4112 4235 erg.to_reduce_l=i2; 4113 4236 assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); … … 4115 4238 return; 4116 4239 } 4117 if (j<0) {4118 4240 if (j<0) 4241 { 4119 4242 //not reduceable, try to use this for reducing higher terms 4120 4243 int i2=fwbw(los,i); … … 4122 4245 assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); 4123 4246 assume(i>=i2); 4124 if(i2!=i){ 4125 4126 4247 if(i2!=i) 4248 { 4127 4249 erg.to_reduce_u=i-1; 4128 4250 erg.to_reduce_l=i2; … … 4133 4255 return; 4134 4256 } 4135 4136 4257 i--; 4137 4258 } … … 4143 4264 // nicht reduzierbare eintraege in ergebnisliste schreiben 4144 4265 // nullen loeschen 4145 // while(finde_groessten leitterm reduzierbar(c,erg)){ 4266 // while(finde_groessten leitterm reduzierbar(c,erg)) 4267 // { 4146 4268 4147 4269 static int multi_reduction_clear_zeroes(red_object* los, int losl, int l, int u) 4148 4270 { 4149 4150 4151 4271 int deleted=0; 4152 4272 int i=l; … … 4154 4274 while(i<=u) 4155 4275 { 4156 4157 if(los[i].p==NULL){4276 if(los[i].p==NULL) 4277 { 4158 4278 kBucketDestroy(&los[i].bucket); 4159 4279 // delete los[i];//here we assume los are constructed with new … … 4171 4291 memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last)); 4172 4292 return deleted; 4173 4174 } 4175 int search_red_object_pos(red_object* a, int top, red_object* key ) {4176 4293 } 4294 4295 int search_red_object_pos(red_object* a, int top, red_object* key ) 4296 { 4177 4297 int an = 0; 4178 4298 int en= top; … … 4195 4315 an=i; 4196 4316 } 4197 4198 } 4317 } 4318 4199 4319 static void sort_region_down(red_object* los, int l, int u, slimgb_alg* c) 4200 4320 { … … 4205 4325 int bound=0; 4206 4326 BOOLEAN at_end=FALSE; 4207 for(i=l;i<=u;i++){ 4208 if (!(at_end)){ 4327 for(i=l;i<=u;i++) 4328 { 4329 if (!(at_end)) 4330 { 4209 4331 bound=new_indices[i-l]=bound+search_red_object_pos(los+bound,l-bound-1,los+i); 4210 4332 if (bound==l) at_end=TRUE; 4211 4333 } 4212 else{ 4334 else 4335 { 4213 4336 new_indices[i-l]=l; 4214 4337 } 4215 4338 } 4216 4339 red_object* los_region=(red_object*) omalloc(sizeof(red_object)*(u-l+1)); 4217 for (int i=0;i<r_size;i++){ 4340 for (int i=0;i<r_size;i++) 4341 { 4218 4342 new_indices[i]+=i; 4219 4343 los_region[i]=los[l+i]; 4220 4344 assume((i==0)||(new_indices[i]>new_indices[i-1])); 4221 4222 4345 } 4223 4346 … … 4225 4348 int j=u; 4226 4349 int j2=l-1; 4227 while(i>=0){ 4228 if (new_indices[i]==j){ 4350 while(i>=0) 4351 { 4352 if (new_indices[i]==j) 4353 { 4229 4354 los[j]=los_region[i]; 4230 4355 i--; 4231 4356 j--; 4232 } else{ 4357 } 4358 else 4359 { 4233 4360 assume(new_indices[i]<j); 4234 4361 los[j]=los[j2]; … … 4239 4366 } 4240 4367 omfree(los_region); 4241 4242 4368 omfree(new_indices); 4243 4244 4369 } 4245 4370 … … 4255 4380 wlen_type max_initial_quality=0; 4256 4381 4257 for(i=0;i<losl;i++){ 4382 for(i=0;i<losl;i++) 4383 { 4258 4384 los[i].sev=pGetShortExpVector(los[i].p); 4259 4385 //SetShortExpVector(); … … 4269 4395 int curr_pos=losl-1; 4270 4396 4271 4272 4397 // nicht reduzierbare eintrᅵe in ergebnisliste schreiben 4273 4398 // nullen loeschen 4274 while(curr_pos>=0){ 4275 if ((c->use_noro_last_block)&&(lies_in_last_dp_block(los[curr_pos].p,c))){ 4399 while(curr_pos>=0) 4400 { 4401 if ((c->use_noro_last_block)&&(lies_in_last_dp_block(los[curr_pos].p,c))) 4402 { 4276 4403 int pn_noro=curr_pos+1; 4277 4404 poly* p_noro=(poly*) omalloc(pn_noro*sizeof(poly)); 4278 for(i=0;i<pn_noro;i++){ 4405 for(i=0;i<pn_noro;i++) 4406 { 4279 4407 int dummy_len; 4280 4408 poly p; … … 4283 4411 p_noro[i]=p; 4284 4412 } 4285 4286 4287 if (npPrimeM<255){ 4413 if (npPrimeM<255) 4414 { 4288 4415 noro_step<tgb_uint8>(p_noro,pn_noro,c); 4289 } else { 4290 if (npPrimeM<65000){ 4416 } 4417 else 4418 { 4419 if (npPrimeM<65000) 4420 { 4291 4421 noro_step<tgb_uint16>(p_noro,pn_noro,c); 4292 } else{ 4422 } 4423 else 4424 { 4293 4425 noro_step<tgb_uint32>(p_noro,pn_noro,c); 4294 4426 } 4295 4427 } 4296 for(i=0;i<pn_noro;i++){ 4428 for(i=0;i<pn_noro;i++) 4429 { 4297 4430 los[i].p=p_noro[i]; 4298 4431 los[i].sev=pGetShortExpVector(los[i].p); 4299 4432 //ignore quality 4300 4433 kBucketInit(los[i].bucket,los[i].p,pLength(los[i].p)); 4301 4302 4434 } 4303 4435 qsort(los,pn_noro,sizeof(red_object),red_object_better_gen); … … 4312 4444 if(erg.reduce_by<0) break; 4313 4445 4314 4315 4316 4446 erg.expand=NULL; 4317 4447 int d=erg.to_reduce_u-erg.to_reduce_l+1; 4318 4448 4319 4320 4449 multi_reduction_lls_trick(los,losl,c,erg); 4321 4322 4450 4323 4451 int i; … … 4336 4464 // 4337 4465 assume(los[i].initial_quality>0); 4338 4339 4466 if(los[i].guess_quality(c) 4340 >1.5*delay_factor*max_initial_quality){ 4467 >1.5*delay_factor*max_initial_quality) 4468 { 4341 4469 if (TEST_OPT_PROT) 4342 4470 PrintS("v"); 4343 4471 los[i].canonicalize(); 4344 4472 if(los[i].guess_quality(c) 4345 >delay_factor*max_initial_quality){ 4473 >delay_factor*max_initial_quality) 4474 { 4346 4475 if (TEST_OPT_PROT) 4347 4476 PrintS("."); … … 4350 4479 delay[delay_s]=los[i].p; 4351 4480 delay_s++; 4352 4353 4481 los[i].p=NULL; 4354 4355 4482 } 4356 4483 } 4357 4358 4484 } 4359 4485 } … … 4372 4498 else 4373 4499 sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c); 4374 4375 4500 4376 4501 if(erg.expand) … … 4384 4509 #else 4385 4510 int ecart=0; 4386 if (c->eliminationProblem){ 4511 if (c->eliminationProblem) 4512 { 4387 4513 ecart=c->pTotaldegree_full(erg.expand)-c->pTotaldegree(erg.expand); 4388 4514 } … … 4390 4516 #endif 4391 4517 } 4392 4393 } 4394 4518 } 4395 4519 4396 4520 //sorted_pair_node** pairs=(sorted_pair_node**) … … 4398 4522 c->introduceDelayedPairs(delay,delay_s); 4399 4523 /* 4400 for(i=0;i<delay_s;i++) {4401 4524 for(i=0;i<delay_s;i++) 4525 { 4402 4526 poly p=delay[i]; 4403 4527 //if (rPar(c->r)==0) … … 4406 4530 si->i=-1; 4407 4531 si->j=-1; 4408 if (!rField_is_Zp(c->r)){ 4532 if (!rField_is_Zp(c->r)) 4533 { 4409 4534 if (!c->nc) 4410 4535 p=redTailShort(p, c->strat); … … 4414 4539 si->expected_length=pQuality(p,c,pLength(p)); 4415 4540 si->deg=pTotaldegree(p); 4416 4417 4541 si->lcm_of_lm=p; 4418 4542 pairs[i]=si; … … 4425 4549 return; 4426 4550 } 4427 void red_object::flatten(){ 4551 4552 void red_object::flatten() 4553 { 4428 4554 assume(p==kBucketGetLm(bucket)); 4429 4555 } 4430 void red_object::validate(){ 4556 4557 void red_object::validate() 4558 { 4431 4559 p=kBucketGetLm(bucket); 4432 4560 if(p) 4433 4561 sev=pGetShortExpVector(p); 4434 4562 } 4435 int red_object::clear_to_poly(){ 4563 4564 int red_object::clear_to_poly() 4565 { 4436 4566 flatten(); 4437 4567 int l; … … 4440 4570 } 4441 4571 4442 4443 4444 4445 4446 4572 void reduction_step::reduce(red_object* r, int l, int u){} 4573 4447 4574 void simple_reducer::do_reduce(red_object & ro) 4448 4575 { … … 4459 4586 } 4460 4587 4461 4462 void simple_reducer::reduce(red_object* r, int l, int u){4588 void simple_reducer::reduce(red_object* r, int l, int u) 4589 { 4463 4590 this->pre_reduce(r,l,u); 4464 4591 int i; … … 4466 4593 int im; 4467 4594 4468 4469 if(c->eliminationProblem){4595 if(c->eliminationProblem) 4596 { 4470 4597 assume(p_LmEqual(r[l].p,r[u].p,c->r)); 4471 4598 /*int lm_deg=pTotaldegree(r[l].p); … … 4473 4600 } 4474 4601 4475 for(i=l;i<=u;i++){ 4476 4477 4478 4602 for(i=l;i<=u;i++) 4603 { 4479 4604 this->do_reduce(r[i]); 4480 if (c->eliminationProblem){ 4605 if (c->eliminationProblem) 4606 { 4481 4607 r[i].sugar=si_max(r[i].sugar,reducer_deg); 4482 4608 } 4483 4609 } 4484 for(i=l;i<=u;i++) {4485 4610 for(i=l;i<=u;i++) 4611 { 4486 4612 kBucketSimpleContent(r[i].bucket); 4487 4613 r[i].validate(); … … 4490 4616 } 4491 4617 } 4618 4492 4619 reduction_step::~reduction_step(){} 4493 simple_reducer::~simple_reducer(){ 4620 4621 simple_reducer::~simple_reducer() 4622 { 4494 4623 if(fill_back!=NULL) 4495 4624 { … … 4497 4626 } 4498 4627 fill_back=NULL; 4499 4500 } 4501 4502 void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c){4628 } 4629 4630 void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c) 4631 { 4503 4632 static int id=0; 4504 4633 id++; … … 4510 4639 simple_reducer* pointer; 4511 4640 BOOLEAN work_on_copy=FALSE; 4512 if(erg.fromS){ 4641 if(erg.fromS) 4642 { 4513 4643 red=c->strat->S[rn]; 4514 4644 red_len=c->strat->lenS[rn]; … … 4539 4669 red_len=pLength(red); 4540 4670 } 4541 if (((TEST_V_MODPSOLVSB)&&(red_len>1))||((c->nc)||(erg.to_reduce_u-erg.to_reduce_l>5))){ 4671 if (((TEST_V_MODPSOLVSB)&&(red_len>1))||((c->nc)||(erg.to_reduce_u-erg.to_reduce_l>5))) 4672 { 4542 4673 work_on_copy=TRUE; 4543 4674 // poly m=pOne(); … … 4555 4686 #endif 4556 4687 red_cp=ppMult_mm(red,m); 4557 if(!erg.fromS){ 4688 if(!erg.fromS) 4689 { 4558 4690 kBucketInit(r[rn].bucket,red,red_len); 4559 4691 } … … 4572 4704 red_len=pLength(red); 4573 4705 // pDelete(&m); 4574 4575 4706 } 4576 4707 int i; 4577 4708 4578 4579 4580 4709 assume(red_len==pLength(red)); 4581 4710 4582 4711 int reducer_deg=0; 4583 if (c->eliminationProblem){ 4712 if (c->eliminationProblem) 4713 { 4584 4714 int lm_deg=c->pTotaldegree(r[erg.to_reduce_l].p); 4585 4715 int ecart; 4586 if (erg.fromS){ 4716 if (erg.fromS) 4717 { 4587 4718 ecart=c->strat->ecartS[erg.reduce_by]; 4588 } else { 4719 } 4720 else 4721 { 4589 4722 ecart=c->pTotaldegree_full(red)-lm_deg; 4590 4723 } … … 4603 4736 if(work_on_copy) pDelete(&pointer->p); 4604 4737 delete pointer; 4605 if (lt_changed){ 4738 if (lt_changed) 4739 { 4606 4740 assume(!erg.fromS); 4607 4741 r[erg.reduce_by].sev=sev; 4608 4742 } 4609 4610 }; 4611 4612 4613 4743 } 4614 4744 4615 4745 void simple_reducer:: pre_reduce(red_object* r, int l, int u){}
Note: See TracChangeset
for help on using the changeset viewer.