[b553e5] | 1 | //! \file tgb.cc |
---|
[4f858ce] | 2 | // multiple rings |
---|
| 3 | // shorten_tails und dessen Aufrufe pruefen wlength!!! |
---|
[6b9532] | 4 | /**************************************** |
---|
| 5 | * Computer Algebra System SINGULAR * |
---|
| 6 | ****************************************/ |
---|
[2bc80b] | 7 | /* $Id: tgb.cc,v 1.44 2005-10-20 11:51:28 Singular Exp $ */ |
---|
[6b9532] | 8 | /* |
---|
| 9 | * ABSTRACT: slimgb and F4 implementation |
---|
| 10 | */ |
---|
[4f858ce] | 11 | |
---|
[ef0269] | 12 | #include "mod2.h" |
---|
[4f858ce] | 13 | #include "tgb.h" |
---|
[0f7b79] | 14 | #include "tgb_internal.h" |
---|
[b055de9] | 15 | #include "tgbgauss.h" |
---|
[b75d13] | 16 | #include "F4.h" |
---|
[d491e3] | 17 | #include "gring.h" |
---|
[25061a] | 18 | //#include "Number.h" |
---|
[d491e3] | 19 | //#include "gr_kstd2.h" |
---|
[1821d6] | 20 | #include "longrat.h" |
---|
[4f858ce] | 21 | static const int bundle_size=100; |
---|
| 22 | #if 1 |
---|
| 23 | static omBin lm_bin=NULL; |
---|
| 24 | static inline poly p_Init_Special(const ring r) |
---|
| 25 | { |
---|
| 26 | return p_Init(r,lm_bin); |
---|
| 27 | } |
---|
| 28 | static inline poly pOne_Special(const ring r=currRing) |
---|
| 29 | { |
---|
| 30 | poly rc = p_Init_Special(r); |
---|
| 31 | pSetCoeff0(rc,r->cf->nInit(1)); |
---|
| 32 | return rc; |
---|
| 33 | } |
---|
| 34 | // zum Initialiseren: in t_rep_gb plazieren: |
---|
| 35 | |
---|
| 36 | #endif |
---|
| 37 | #define LEN_VAR3 |
---|
| 38 | #define degbound(p) assume(pTotaldegree(p)<10) |
---|
| 39 | //#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0)) |
---|
| 40 | |
---|
| 41 | //die meisten Varianten stossen sich an coef_buckets |
---|
| 42 | #ifdef LEN_VAR1 |
---|
| 43 | // erste Variante: Laenge: Anzahl der Monome |
---|
| 44 | inline int pSLength(poly p, int l) { |
---|
| 45 | return l; } |
---|
| 46 | inline int kSBucketLength(kBucket* bucket, poly lm) {return bucket_guess(bucket);} |
---|
| 47 | #endif |
---|
| 48 | |
---|
| 49 | #ifdef LEN_VAR2 |
---|
| 50 | // 2. Variante: Laenge: Platz fuer die Koeff. |
---|
| 51 | int pSLength(poly p,int l) |
---|
| 52 | { |
---|
| 53 | int s=0; |
---|
| 54 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 55 | return s; |
---|
| 56 | } |
---|
| 57 | int kSBucketLength(kBucket* b, poly lm) |
---|
| 58 | { |
---|
| 59 | int s=0; |
---|
| 60 | int i; |
---|
| 61 | for (i=MAX_BUCKET;i>=0;i--) |
---|
| 62 | { |
---|
| 63 | s+=pSLength(b->buckets[i],0); |
---|
| 64 | } |
---|
| 65 | return s; |
---|
| 66 | } |
---|
| 67 | #endif |
---|
| 68 | |
---|
| 69 | #ifdef LEN_VAR3 |
---|
| 70 | // 3.Variante: Laenge: Platz fuer Leitk * Monomanzahl |
---|
[1821d6] | 71 | |
---|
| 72 | int QlogSizeClassic(number bigint){ |
---|
| 73 | if(nlIsZero(bigint)) return 0; |
---|
| 74 | number absv=nlCopy(bigint); |
---|
| 75 | number two=nlInit(2); |
---|
| 76 | if(!(nlGreaterZero(absv))) |
---|
| 77 | absv=nlNeg(absv); |
---|
| 78 | int ls=0; |
---|
| 79 | number comp=nlInit(1); |
---|
| 80 | BOOLEAN equal=FALSE; |
---|
| 81 | while(!(nlGreater(comp,absv))) { |
---|
| 82 | ls++; |
---|
| 83 | if (nlEqual(comp,absv)){ |
---|
| 84 | equal=TRUE; |
---|
| 85 | break; |
---|
| 86 | } |
---|
| 87 | number temp=comp; |
---|
| 88 | comp=nlMult(comp,two); |
---|
| 89 | nlDelete(&temp, currRing); |
---|
| 90 | |
---|
| 91 | } |
---|
| 92 | if(!equal) |
---|
| 93 | ls++; |
---|
| 94 | nlDelete(&two,currRing); |
---|
| 95 | nlDelete(&absv,currRing); |
---|
| 96 | nlDelete(&comp,currRing); |
---|
| 97 | //Print("%d\n",ls); |
---|
| 98 | return ls; |
---|
| 99 | } |
---|
| 100 | int QlogSize(number bigint){ |
---|
| 101 | int size=nlSize(bigint); |
---|
| 102 | if(size<=1) return QlogSizeClassic(bigint); |
---|
| 103 | else return sizeof(mp_limb_t)*size*8; |
---|
| 104 | } |
---|
[4f858ce] | 105 | inline int pSLength(poly p,int l) |
---|
| 106 | { |
---|
[1821d6] | 107 | int c; |
---|
| 108 | number coef=pGetCoeff(p); |
---|
| 109 | if (rField_is_Q(currRing)){ |
---|
| 110 | c=QlogSize(coef); |
---|
| 111 | } |
---|
| 112 | else |
---|
| 113 | c=nSize(coef); |
---|
| 114 | |
---|
[4f858ce] | 115 | return c*l /*pLength(p)*/; |
---|
| 116 | } |
---|
[1821d6] | 117 | //! TODO CoefBuckets berücksichtigen |
---|
[4f858ce] | 118 | int kSBucketLength(kBucket* b, poly lm=NULL) |
---|
| 119 | { |
---|
| 120 | int s=0; |
---|
| 121 | int c; |
---|
[1821d6] | 122 | number coef; |
---|
[4f858ce] | 123 | if(lm==NULL) |
---|
[1821d6] | 124 | coef=pGetCoeff(kBucketGetLm(b)); |
---|
| 125 | //c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 126 | else |
---|
| 127 | coef=pGetCoeff(lm); |
---|
| 128 | //c=nSize(pGetCoeff(lm)); |
---|
| 129 | if (rField_is_Q(currRing)){ |
---|
| 130 | c=QlogSize(coef); |
---|
| 131 | } |
---|
[4f858ce] | 132 | else |
---|
[1821d6] | 133 | c=nSize(coef); |
---|
| 134 | |
---|
[4f858ce] | 135 | int i; |
---|
| 136 | for (i=b->buckets_used;i>=0;i--) |
---|
| 137 | { |
---|
| 138 | assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL)); |
---|
| 139 | s+=b->buckets_length[i] /*pLength(b->buckets[i])*/; |
---|
| 140 | } |
---|
[1821d6] | 141 | #ifdef HAVE_COEF_BUCKETS |
---|
| 142 | assume(b->buckets[0]==kBucketGetLm(b)); |
---|
| 143 | if (b->coef[0]!=NULL){ |
---|
| 144 | |
---|
| 145 | if (rField_is_Q(currRing)){ |
---|
| 146 | int modifier=QlogSize(pGetCoeff(b->coef[0])); |
---|
| 147 | c+=modifier; |
---|
| 148 | } |
---|
| 149 | else{ |
---|
| 150 | int modifier=nSize(pGetCoeff(b->coef[0])); |
---|
| 151 | c*=modifier;} |
---|
| 152 | } |
---|
| 153 | #endif |
---|
[4f858ce] | 154 | return s*c; |
---|
| 155 | } |
---|
| 156 | #endif |
---|
| 157 | |
---|
| 158 | #ifdef LEN_VAR4 |
---|
| 159 | // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.) |
---|
| 160 | int pSLength(poly p, int l) |
---|
| 161 | { |
---|
| 162 | int s=1; |
---|
| 163 | int c=nSize(pGetCoeff(p)); |
---|
| 164 | pIter(p); |
---|
| 165 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 166 | return s*c; |
---|
| 167 | } |
---|
| 168 | int kSBucketLength(kBucket* b) |
---|
| 169 | { |
---|
| 170 | int s=1; |
---|
| 171 | int c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 172 | int i; |
---|
| 173 | for (i=MAX_BUCKET;i>0;i--) |
---|
| 174 | { |
---|
| 175 | if(b->buckets[i]==NULL) continue; |
---|
| 176 | s+=pSLength(b->buckets[i],0); |
---|
| 177 | } |
---|
| 178 | return s*c; |
---|
| 179 | } |
---|
| 180 | #endif |
---|
[9cbb7a3] | 181 | static int do_pELength(poly p, slimgb_alg* c, int dlm=-1){ |
---|
[4f858ce] | 182 | if(p==NULL) return 0; |
---|
| 183 | int s=0; |
---|
| 184 | poly pi=p; |
---|
| 185 | if(dlm<0){ |
---|
| 186 | dlm=pTotaldegree(p,c->r); |
---|
| 187 | s=1; |
---|
| 188 | pi=p->next; |
---|
| 189 | } |
---|
| 190 | |
---|
| 191 | while(pi){ |
---|
| 192 | int d=pTotaldegree(pi,c->r); |
---|
| 193 | if(d>dlm) |
---|
| 194 | s+=1+d-dlm; |
---|
| 195 | else |
---|
| 196 | ++s; |
---|
| 197 | pi=pi->next; |
---|
| 198 | } |
---|
| 199 | return s; |
---|
| 200 | } |
---|
[9cbb7a3] | 201 | int kEBucketLength(kBucket* b, poly lm,slimgb_alg* ca) |
---|
[4f858ce] | 202 | { |
---|
| 203 | int s=0; |
---|
| 204 | if(lm==NULL){ |
---|
| 205 | lm=kBucketGetLm(b); |
---|
| 206 | } |
---|
| 207 | if(lm==NULL) return 0; |
---|
| 208 | int d=pTotaldegree(lm,ca->r); |
---|
| 209 | int i; |
---|
| 210 | for (i=b->buckets_used;i>=0;i--) |
---|
| 211 | { |
---|
| 212 | if(b->buckets[i]==NULL) continue; |
---|
| 213 | s+=do_pELength(b->buckets[i],ca,d); |
---|
| 214 | } |
---|
| 215 | return s; |
---|
| 216 | } |
---|
| 217 | |
---|
[9cbb7a3] | 218 | static inline int pELength(poly p, slimgb_alg* c,int l){ |
---|
[4f858ce] | 219 | if (p==NULL) return 0; |
---|
| 220 | return do_pELength(p,c); |
---|
| 221 | } |
---|
[9cbb7a3] | 222 | // static int quality(poly p, int len, slimgb_alg* c){ |
---|
[4f858ce] | 223 | // if (c->is_char0) return pSLength(p,len); |
---|
| 224 | // return pLength(p); |
---|
| 225 | // } |
---|
[d491e3] | 226 | |
---|
| 227 | |
---|
| 228 | |
---|
| 229 | |
---|
| 230 | |
---|
| 231 | |
---|
| 232 | |
---|
| 233 | |
---|
[9cbb7a3] | 234 | static inline int pQuality(poly p, slimgb_alg* c, int l=-1){ |
---|
[4f858ce] | 235 | |
---|
| 236 | if(l<0) |
---|
| 237 | l=pLength(p); |
---|
[d491e3] | 238 | if(c->is_char0) { |
---|
| 239 | if((pLexOrder) &&(!c->is_homog)){ |
---|
| 240 | int cs; |
---|
| 241 | number coef=pGetCoeff(p); |
---|
| 242 | if (rField_is_Q(currRing)){ |
---|
| 243 | cs=QlogSize(coef); |
---|
| 244 | } |
---|
| 245 | else |
---|
| 246 | cs=nSize(coef); |
---|
| 247 | return cs*pELength(p,c,l); |
---|
| 248 | } |
---|
| 249 | return pSLength(p,l); |
---|
| 250 | } |
---|
[4f858ce] | 251 | if((pLexOrder) &&(!c->is_homog)) return pELength(p,c,l); |
---|
| 252 | return l; |
---|
| 253 | } |
---|
[d491e3] | 254 | |
---|
[4f858ce] | 255 | static inline int pTotaldegree_full(poly p){ |
---|
| 256 | int r=0; |
---|
| 257 | while(p){ |
---|
| 258 | int d=pTotaldegree(p); |
---|
| 259 | r=si_max(r,d); |
---|
| 260 | pIter(p); |
---|
| 261 | } |
---|
| 262 | return r; |
---|
| 263 | } |
---|
| 264 | |
---|
[9cbb7a3] | 265 | int red_object::guess_quality(slimgb_alg* c){ |
---|
[4f858ce] | 266 | //works at the moment only for lenvar 1, because in different |
---|
| 267 | //case, you have to look on coefs |
---|
| 268 | int s=0; |
---|
[d491e3] | 269 | if (c->is_char0){ |
---|
[1821d6] | 270 | //s=kSBucketLength(bucket,this->p); |
---|
[d491e3] | 271 | if((pLexOrder) &&(!c->is_homog)){ |
---|
| 272 | int cs; |
---|
| 273 | number coef; |
---|
| 274 | |
---|
| 275 | coef=pGetCoeff(kBucketGetLm(bucket)); |
---|
| 276 | //c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 277 | |
---|
| 278 | //c=nSize(pGetCoeff(lm)); |
---|
| 279 | if (rField_is_Q(currRing)){ |
---|
| 280 | cs=QlogSize(coef); |
---|
| 281 | } |
---|
| 282 | else |
---|
| 283 | cs=nSize(coef); |
---|
| 284 | if (bucket->coef[0]!=NULL){ |
---|
| 285 | if (rField_is_Q(currRing)){ |
---|
| 286 | int modifier=QlogSize(pGetCoeff(bucket->coef[0])); |
---|
| 287 | cs+=modifier; |
---|
| 288 | } |
---|
| 289 | else{ |
---|
| 290 | int modifier=nSize(pGetCoeff(bucket->coef[0])); |
---|
| 291 | cs*=modifier;} |
---|
| 292 | } |
---|
| 293 | return cs*kEBucketLength(this->bucket,this->p,c); |
---|
| 294 | } |
---|
[1821d6] | 295 | s=kSBucketLength(bucket,NULL); |
---|
[d491e3] | 296 | } |
---|
[4f858ce] | 297 | else |
---|
| 298 | { |
---|
| 299 | if((pLexOrder) &&(!c->is_homog)) |
---|
| 300 | //if (false) |
---|
| 301 | s=kEBucketLength(this->bucket,this->p,c); |
---|
| 302 | else s=bucket_guess(bucket); |
---|
| 303 | } |
---|
[bddc9d] | 304 | |
---|
[4f858ce] | 305 | return s; |
---|
| 306 | } |
---|
[d491e3] | 307 | |
---|
[9cbb7a3] | 308 | // static int guess_quality(const red_object & p, slimgb_alg* c){ |
---|
[4f858ce] | 309 | // //looks only on bucket |
---|
| 310 | // if (c->is_char0) return kSBucketLength(p.bucket,p.p); |
---|
| 311 | // if((pLexOrder) &&(!c->is_homog)) return kEBucketLength(p.bucket,p.p,c); |
---|
| 312 | // return (bucket_guess(p.bucket)); |
---|
| 313 | // } |
---|
| 314 | |
---|
| 315 | static void finalize_reduction_step(reduction_step* r){ |
---|
| 316 | delete r; |
---|
| 317 | } |
---|
| 318 | static int LObject_better_gen(const void* ap, const void* bp) |
---|
| 319 | { |
---|
| 320 | LObject* a=*(LObject**)ap; |
---|
| 321 | LObject* b=*(LObject**)bp; |
---|
| 322 | return(pLmCmp(a->p,b->p)); |
---|
| 323 | } |
---|
| 324 | static int red_object_better_gen(const void* ap, const void* bp) |
---|
| 325 | { |
---|
| 326 | |
---|
| 327 | |
---|
| 328 | return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p)); |
---|
| 329 | } |
---|
| 330 | |
---|
| 331 | |
---|
| 332 | static int pLmCmp_func_inverted(const void* ap1, const void* ap2){ |
---|
| 333 | poly p1,p2; |
---|
| 334 | p1=*((poly*) ap1); |
---|
| 335 | p2=*((poly*)ap2); |
---|
| 336 | |
---|
| 337 | return -pLmCmp(p1,p2); |
---|
| 338 | } |
---|
| 339 | |
---|
[b75d13] | 340 | int tgb_pair_better_gen2(const void* ap,const void* bp){ |
---|
| 341 | return(-tgb_pair_better_gen(ap,bp)); |
---|
[4f858ce] | 342 | } |
---|
[b75d13] | 343 | int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){ |
---|
[4f858ce] | 344 | int i; |
---|
| 345 | long not_sev=~obj.sev; |
---|
| 346 | poly p=obj.p; |
---|
| 347 | for(i=0;i<=strat->sl;i++){ |
---|
| 348 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 349 | return i; |
---|
| 350 | } |
---|
| 351 | return -1; |
---|
| 352 | } |
---|
[b75d13] | 353 | int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev){ |
---|
[4f858ce] | 354 | int i; |
---|
| 355 | long not_sev=~sev; |
---|
| 356 | for(i=0;i<=strat->sl;i++){ |
---|
| 357 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 358 | return i; |
---|
| 359 | } |
---|
| 360 | return -1; |
---|
| 361 | } |
---|
[9cbb7a3] | 362 | static int posInPairs (sorted_pair_node** p, int pn, sorted_pair_node* qe,slimgb_alg* c,int an=0) |
---|
[4f858ce] | 363 | { |
---|
| 364 | if(pn==0) return 0; |
---|
| 365 | |
---|
| 366 | int length=pn-1; |
---|
| 367 | int i; |
---|
| 368 | //int an = 0; |
---|
| 369 | int en= length; |
---|
| 370 | |
---|
| 371 | if (pair_better(qe,p[en],c)) |
---|
| 372 | return length+1; |
---|
| 373 | |
---|
| 374 | while(1) |
---|
| 375 | { |
---|
| 376 | //if (an >= en-1) |
---|
| 377 | if(en-1<=an) |
---|
| 378 | { |
---|
| 379 | if (pair_better(p[an],qe,c)) return an; |
---|
| 380 | return en; |
---|
| 381 | } |
---|
| 382 | i=(an+en) / 2; |
---|
| 383 | if (pair_better(p[i],qe,c)) |
---|
| 384 | en=i; |
---|
| 385 | else an=i; |
---|
| 386 | } |
---|
| 387 | } |
---|
| 388 | |
---|
| 389 | static BOOLEAN ascending(int* i,int top){ |
---|
| 390 | if(top<1) return TRUE; |
---|
| 391 | if(i[top]<i[top-1]) return FALSE; |
---|
| 392 | return ascending(i,top-1); |
---|
| 393 | } |
---|
| 394 | |
---|
[9cbb7a3] | 395 | sorted_pair_node** spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c){ |
---|
[4f858ce] | 396 | int i; |
---|
[ec8a6b6] | 397 | int* a= (int*) omalloc(qn*sizeof(int)); |
---|
[4f858ce] | 398 | // int mc; |
---|
| 399 | // PrintS("Debug\n"); |
---|
| 400 | // for(mc=0;mc<qn;mc++) |
---|
| 401 | // { |
---|
| 402 | |
---|
| 403 | // wrp(q[mc]->lcm_of_lm); |
---|
| 404 | // PrintS("\n"); |
---|
| 405 | // } |
---|
| 406 | // PrintS("Debug they are in\n"); |
---|
| 407 | // for(mc=0;mc<pn;mc++) |
---|
| 408 | // { |
---|
| 409 | |
---|
| 410 | // wrp(p[mc]->lcm_of_lm); |
---|
| 411 | // PrintS("\n"); |
---|
| 412 | // } |
---|
| 413 | int lastpos=0; |
---|
| 414 | for(i=0;i<qn;i++){ |
---|
| 415 | lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0)); |
---|
| 416 | // cout<<lastpos<<"\n"; |
---|
| 417 | a[i]=lastpos; |
---|
| 418 | |
---|
| 419 | } |
---|
| 420 | if((pn+qn)>c->max_pairs){ |
---|
[ec8a6b6] | 421 | p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 422 | c->max_pairs=2*(pn+qn); |
---|
| 423 | } |
---|
| 424 | for(i=qn-1;i>=0;i--){ |
---|
| 425 | size_t size; |
---|
| 426 | if(qn-1>i) |
---|
| 427 | size=(a[i+1]-a[i])*sizeof(sorted_pair_node*); |
---|
| 428 | else |
---|
| 429 | size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0 |
---|
| 430 | memmove (p+a[i]+(1+i), p+a[i], size); |
---|
| 431 | p[a[i]+i]=q[i]; |
---|
| 432 | } |
---|
| 433 | omfree(a); |
---|
| 434 | return p; |
---|
| 435 | } |
---|
| 436 | |
---|
| 437 | |
---|
[9cbb7a3] | 438 | static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c){ |
---|
[4f858ce] | 439 | |
---|
| 440 | |
---|
| 441 | poly p1=c->S->m[pos1]; |
---|
| 442 | poly p2=c->S->m[pos2]; |
---|
| 443 | ring r=c->r; |
---|
| 444 | |
---|
| 445 | |
---|
| 446 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 447 | return FALSE; |
---|
| 448 | int i = 1; |
---|
| 449 | poly m=NULL; |
---|
| 450 | poly gcd1=c->gcd_of_terms[pos1]; |
---|
| 451 | poly gcd2=c->gcd_of_terms[pos2]; |
---|
| 452 | |
---|
| 453 | if((gcd1!=NULL) && (gcd2!=NULL)) |
---|
| 454 | { |
---|
| 455 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 456 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 457 | gcd1->next=NULL; |
---|
| 458 | |
---|
| 459 | } |
---|
| 460 | |
---|
| 461 | if (m==NULL) |
---|
| 462 | { |
---|
| 463 | loop |
---|
| 464 | { |
---|
| 465 | if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 466 | if (i == pVariables){ |
---|
| 467 | //PrintS("trivial"); |
---|
| 468 | return TRUE; |
---|
| 469 | } |
---|
| 470 | i++; |
---|
| 471 | } |
---|
| 472 | } |
---|
| 473 | else |
---|
| 474 | { |
---|
| 475 | loop |
---|
| 476 | { |
---|
| 477 | if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 478 | if (i == pVariables){ |
---|
| 479 | pDelete(&m); |
---|
| 480 | //PrintS("trivial"); |
---|
| 481 | return TRUE; |
---|
| 482 | } |
---|
| 483 | i++; |
---|
| 484 | } |
---|
| 485 | } |
---|
| 486 | |
---|
| 487 | |
---|
| 488 | |
---|
| 489 | |
---|
| 490 | } |
---|
| 491 | |
---|
[b553e5] | 492 | //! returns position sets w as weight |
---|
[9cbb7a3] | 493 | int find_best(red_object* r,int l, int u, int &w, slimgb_alg* c){ |
---|
[4f858ce] | 494 | int best=l; |
---|
| 495 | int i; |
---|
| 496 | w=r[l].guess_quality(c); |
---|
| 497 | for(i=l+1;i<=u;i++){ |
---|
| 498 | int w2=r[i].guess_quality(c); |
---|
| 499 | if(w2<w){ |
---|
| 500 | w=w2; |
---|
| 501 | best=i; |
---|
| 502 | } |
---|
| 503 | |
---|
| 504 | } |
---|
| 505 | return best; |
---|
| 506 | } |
---|
| 507 | |
---|
| 508 | |
---|
| 509 | void red_object::canonicalize(){ |
---|
| 510 | kBucketCanonicalize(bucket); |
---|
[bddc9d] | 511 | |
---|
[4f858ce] | 512 | |
---|
| 513 | } |
---|
[9cbb7a3] | 514 | BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c){ |
---|
[4f858ce] | 515 | assume(i>=0); |
---|
| 516 | assume(j>=0); |
---|
| 517 | if (has_t_rep(i,j,c)) return TRUE; |
---|
| 518 | //poly lm=pOne(); |
---|
| 519 | assume (c->tmp_lm!=NULL); |
---|
| 520 | poly lm=c->tmp_lm; |
---|
| 521 | |
---|
| 522 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 523 | pSetm(lm); |
---|
| 524 | assume(lm!=NULL); |
---|
| 525 | //int deciding_deg= pTotaldegree(lm); |
---|
| 526 | int* i_con =make_connections(i,j,lm,c); |
---|
| 527 | //p_Delete(&lm,c->r); |
---|
| 528 | |
---|
| 529 | |
---|
| 530 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 531 | if (i_con[n]==j){ |
---|
| 532 | now_t_rep(i,j,c); |
---|
| 533 | omfree(i_con); |
---|
| 534 | |
---|
| 535 | return TRUE; |
---|
| 536 | } |
---|
| 537 | } |
---|
| 538 | omfree(i_con); |
---|
| 539 | |
---|
| 540 | return FALSE; |
---|
| 541 | } |
---|
| 542 | BOOLEAN lenS_correct(kStrategy strat){ |
---|
| 543 | int i; |
---|
| 544 | for(i=0;i<=strat->sl;i++){ |
---|
| 545 | if (strat->lenS[i]!=pLength(strat->S[i])) |
---|
| 546 | return FALSE; |
---|
| 547 | } |
---|
| 548 | return TRUE; |
---|
| 549 | } |
---|
| 550 | |
---|
[9cbb7a3] | 551 | static void notice_miss(int i, int j, slimgb_alg* c){ |
---|
[4f858ce] | 552 | if (TEST_OPT_PROT) |
---|
| 553 | PrintS("-"); |
---|
| 554 | |
---|
| 555 | } |
---|
| 556 | |
---|
[9cbb7a3] | 557 | static void cleanS(kStrategy strat, slimgb_alg* c){ |
---|
[4f858ce] | 558 | int i=0; |
---|
| 559 | LObject P; |
---|
| 560 | while(i<=strat->sl){ |
---|
| 561 | P.p=strat->S[i]; |
---|
| 562 | P.sev=strat->sevS[i]; |
---|
| 563 | if(kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P)!=i) |
---|
| 564 | { |
---|
| 565 | deleteInS(i,strat); |
---|
| 566 | //remember destroying poly |
---|
| 567 | BOOLEAN found=FALSE; |
---|
| 568 | int j; |
---|
| 569 | for(j=0;j<c->n;j++) |
---|
| 570 | if(c->S->m[j]==P.p) |
---|
| 571 | { |
---|
| 572 | found=TRUE; |
---|
| 573 | break; |
---|
| 574 | } |
---|
| 575 | if (!found) |
---|
| 576 | pDelete(&P.p); |
---|
| 577 | //remember additional reductors |
---|
| 578 | } |
---|
| 579 | else i++; |
---|
| 580 | } |
---|
| 581 | } |
---|
| 582 | static int bucket_guess(kBucket* bucket){ |
---|
| 583 | int sum=0; |
---|
| 584 | int i; |
---|
| 585 | for (i=bucket->buckets_used;i>=0;i--){ |
---|
| 586 | if(bucket->buckets[i]) |
---|
| 587 | sum+=bucket->buckets_length[i]; |
---|
| 588 | } |
---|
| 589 | return sum; |
---|
| 590 | } |
---|
| 591 | |
---|
| 592 | |
---|
| 593 | |
---|
| 594 | |
---|
| 595 | |
---|
| 596 | |
---|
[9cbb7a3] | 597 | static int add_to_reductors(slimgb_alg* c, poly h, int len){ |
---|
[4f858ce] | 598 | //inDebug(h); |
---|
| 599 | assume(lenS_correct(c->strat)); |
---|
| 600 | assume(len==pLength(h)); |
---|
| 601 | int i; |
---|
| 602 | // if (c->is_char0) |
---|
| 603 | // i=simple_posInS(c->strat,h,pSLength(h,len),c->is_char0); |
---|
| 604 | // else |
---|
| 605 | // i=simple_posInS(c->strat,h,len,c->is_char0); |
---|
| 606 | |
---|
| 607 | LObject P; memset(&P,0,sizeof(P)); |
---|
| 608 | P.tailRing=c->r; |
---|
| 609 | P.p=h; /*p_Copy(h,c->r);*/ |
---|
| 610 | P.FDeg=pFDeg(P.p,c->r); |
---|
| 611 | |
---|
| 612 | if (!rField_is_Zp(c->r)){ |
---|
| 613 | pCleardenom(P.p); |
---|
| 614 | pContent(P.p); //is a duplicate call, but belongs here |
---|
| 615 | |
---|
| 616 | } |
---|
| 617 | else |
---|
| 618 | pNorm(P.p); |
---|
| 619 | pNormalize(P.p); |
---|
[25061a] | 620 | wlen_type pq=pQuality(h,c,len); |
---|
| 621 | i=simple_posInS(c->strat,h,len,pq); |
---|
[4f858ce] | 622 | c->strat->enterS(P,i,c->strat,-1); |
---|
| 623 | |
---|
| 624 | |
---|
| 625 | |
---|
| 626 | c->strat->lenS[i]=len; |
---|
| 627 | assume(pLength(c->strat->S[i])==c->strat->lenS[i]); |
---|
[6bcdc53] | 628 | if(c->strat->lenSw!=NULL) |
---|
[4f858ce] | 629 | c->strat->lenSw[i]=pq; |
---|
| 630 | |
---|
| 631 | return i; |
---|
| 632 | |
---|
| 633 | } |
---|
[9cbb7a3] | 634 | static void length_one_crit(slimgb_alg* c, int pos, int len) |
---|
[4f858ce] | 635 | { |
---|
[d491e3] | 636 | if (c->nc) |
---|
| 637 | return; |
---|
[4f858ce] | 638 | if (len==1) |
---|
| 639 | { |
---|
| 640 | int i; |
---|
| 641 | for ( i=0;i<pos;i++) |
---|
| 642 | { |
---|
| 643 | if (c->lengths[i]==1) |
---|
| 644 | c->states[pos][i]=HASTREP; |
---|
| 645 | } |
---|
| 646 | for ( i=pos+1;i<c->n;i++){ |
---|
| 647 | if (c->lengths[i]==1) |
---|
| 648 | c->states[i][pos]=HASTREP; |
---|
| 649 | } |
---|
[d491e3] | 650 | if (!c->nc) |
---|
| 651 | shorten_tails(c,c->S->m[pos]); |
---|
[4f858ce] | 652 | } |
---|
| 653 | } |
---|
[9cbb7a3] | 654 | static sorted_pair_node* find_next_pair2(slimgb_alg* c, BOOLEAN go_higher){ |
---|
[4f858ce] | 655 | clean_top_of_pair_list(c); |
---|
| 656 | sorted_pair_node* s=pop_pair(c); |
---|
| 657 | |
---|
| 658 | |
---|
| 659 | return s; |
---|
| 660 | } |
---|
| 661 | |
---|
| 662 | static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat) |
---|
| 663 | { |
---|
| 664 | assume(old_pos>=new_pos); |
---|
| 665 | poly p=strat->S[old_pos]; |
---|
| 666 | int ecart=strat->ecartS[old_pos]; |
---|
| 667 | long sev=strat->sevS[old_pos]; |
---|
| 668 | int s_2_r=strat->S_2_R[old_pos]; |
---|
| 669 | int length=strat->lenS[old_pos]; |
---|
| 670 | assume(length==pLength(strat->S[old_pos])); |
---|
[6bcdc53] | 671 | wlen_type length_w; |
---|
| 672 | if(strat->lenSw!=NULL) |
---|
[4f858ce] | 673 | length_w=strat->lenSw[old_pos]; |
---|
| 674 | int i; |
---|
| 675 | for (i=old_pos; i>new_pos; i--) |
---|
| 676 | { |
---|
| 677 | strat->S[i] = strat->S[i-1]; |
---|
| 678 | strat->ecartS[i] = strat->ecartS[i-1]; |
---|
| 679 | strat->sevS[i] = strat->sevS[i-1]; |
---|
| 680 | strat->S_2_R[i] = strat->S_2_R[i-1]; |
---|
| 681 | } |
---|
| 682 | if (strat->lenS!=NULL) |
---|
| 683 | for (i=old_pos; i>new_pos; i--) |
---|
| 684 | strat->lenS[i] = strat->lenS[i-1]; |
---|
| 685 | if (strat->lenSw!=NULL) |
---|
| 686 | for (i=old_pos; i>new_pos; i--) |
---|
| 687 | strat->lenSw[i] = strat->lenSw[i-1]; |
---|
| 688 | |
---|
| 689 | strat->S[new_pos]=p; |
---|
| 690 | strat->ecartS[new_pos]=ecart; |
---|
| 691 | strat->sevS[new_pos]=sev; |
---|
| 692 | strat->S_2_R[new_pos]=s_2_r; |
---|
| 693 | strat->lenS[new_pos]=length; |
---|
[6bcdc53] | 694 | if(strat->lenSw!=NULL) |
---|
[4f858ce] | 695 | strat->lenSw[new_pos]=length_w; |
---|
| 696 | //assume(lenS_correct(strat)); |
---|
| 697 | } |
---|
[9cbb7a3] | 698 | static void replace_pair(int & i, int & j, slimgb_alg* c) |
---|
[4f858ce] | 699 | { |
---|
| 700 | c->soon_free=NULL; |
---|
| 701 | int curr_deg; |
---|
| 702 | poly lm=pOne(); |
---|
| 703 | |
---|
| 704 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 705 | pSetm(lm); |
---|
| 706 | int deciding_deg= pTotaldegree(lm); |
---|
| 707 | int* i_con =make_connections(i,j,lm,c); |
---|
| 708 | int z=0; |
---|
| 709 | |
---|
| 710 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 711 | if (i_con[n]==j){ |
---|
| 712 | now_t_rep(i,j,c); |
---|
| 713 | omfree(i_con); |
---|
| 714 | p_Delete(&lm,c->r); |
---|
| 715 | return; |
---|
| 716 | } |
---|
| 717 | } |
---|
| 718 | |
---|
| 719 | int* j_con =make_connections(j,lm,c); |
---|
| 720 | i= i_con[0]; |
---|
| 721 | j=j_con[0]; |
---|
| 722 | if(c->n>1){ |
---|
| 723 | if (i_con[1]>=0) |
---|
| 724 | i=i_con[1]; |
---|
| 725 | else { |
---|
| 726 | if (j_con[1]>=0) |
---|
| 727 | j=j_con[1]; |
---|
| 728 | } |
---|
| 729 | } |
---|
| 730 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 731 | pSetm(lm); |
---|
| 732 | poly short_s; |
---|
| 733 | curr_deg=pTotaldegree(lm); |
---|
| 734 | int_pair_node* last=NULL; |
---|
| 735 | |
---|
| 736 | for (int n=0;((n<c->n) && (j_con[n]>=0));n++){ |
---|
| 737 | for (int m=0;((m<c->n) && (i_con[m]>=0));m++){ |
---|
| 738 | pLcm(c->S->m[i_con[m]], c->S->m[j_con[n]], lm); |
---|
| 739 | pSetm(lm); |
---|
| 740 | if (pTotaldegree(lm)>=deciding_deg) |
---|
| 741 | { |
---|
| 742 | soon_t_rep(i_con[m],j_con[n],c); |
---|
[ec8a6b6] | 743 | int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node)); |
---|
[4f858ce] | 744 | if (last!=NULL) |
---|
| 745 | last->next=h; |
---|
| 746 | else |
---|
| 747 | c->soon_free=h; |
---|
| 748 | h->next=NULL; |
---|
| 749 | h->a=i_con[m]; |
---|
| 750 | h->b=j_con[n]; |
---|
| 751 | last=h; |
---|
| 752 | } |
---|
| 753 | // if ((comp_deg<curr_deg) |
---|
| 754 | // || |
---|
| 755 | // ((comp_deg==curr_deg) && |
---|
| 756 | short_s=ksCreateShortSpoly(c->S->m[i_con[m]],c->S->m[j_con[n]],c->r); |
---|
| 757 | if (short_s==NULL) { |
---|
| 758 | i=i_con[m]; |
---|
| 759 | j=j_con[n]; |
---|
| 760 | now_t_rep(i_con[m],j_con[n],c); |
---|
| 761 | p_Delete(&lm,c->r); |
---|
| 762 | omfree(i_con); |
---|
| 763 | omfree(j_con); |
---|
| 764 | |
---|
| 765 | return; |
---|
| 766 | } |
---|
| 767 | #ifdef QUICK_SPOLY_TEST |
---|
| 768 | for (int dz=0;dz<=c->n;dz++){ |
---|
| 769 | if (dz==c->n) { |
---|
| 770 | //have found not head reducing pair |
---|
| 771 | i=i_con[m]; |
---|
| 772 | j=j_con[n]; |
---|
| 773 | p_Delete(&short_s,c->r); |
---|
| 774 | p_Delete(&lm,c->r); |
---|
| 775 | omfree(i_con); |
---|
| 776 | omfree(j_con); |
---|
| 777 | |
---|
| 778 | return; |
---|
| 779 | } |
---|
| 780 | if (p_LmDivisibleBy(c->S->m[dz],short_s,c->r)) break; |
---|
| 781 | } |
---|
| 782 | #endif |
---|
| 783 | int comp_deg(pTotaldegree(short_s)); |
---|
| 784 | p_Delete(&short_s,c->r); |
---|
| 785 | if ((comp_deg<curr_deg)) |
---|
| 786 | |
---|
| 787 | { |
---|
| 788 | curr_deg=comp_deg; |
---|
| 789 | i=i_con[m]; |
---|
| 790 | j=j_con[n]; |
---|
| 791 | } |
---|
| 792 | } |
---|
| 793 | } |
---|
| 794 | p_Delete(&lm,c->r); |
---|
| 795 | omfree(i_con); |
---|
| 796 | omfree(j_con); |
---|
| 797 | return; |
---|
| 798 | } |
---|
| 799 | |
---|
| 800 | |
---|
[9cbb7a3] | 801 | static int* make_connections(int from, poly bound, slimgb_alg* c) |
---|
[4f858ce] | 802 | { |
---|
| 803 | ideal I=c->S; |
---|
| 804 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 805 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 806 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 807 | int cans_length=0; |
---|
| 808 | connected[0]=from; |
---|
| 809 | int connected_length=1; |
---|
| 810 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 811 | for (int i=0;i<c->n;i++){ |
---|
| 812 | if (c->T_deg[i]>s) continue; |
---|
| 813 | if (i!=from){ |
---|
| 814 | if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){ |
---|
| 815 | cans[cans_length]=i; |
---|
| 816 | cans_length++; |
---|
| 817 | } |
---|
| 818 | } |
---|
| 819 | } |
---|
| 820 | int not_yet_found=cans_length; |
---|
| 821 | int con_checked=0; |
---|
| 822 | int pos; |
---|
| 823 | while((not_yet_found>0) && (con_checked<connected_length)){ |
---|
| 824 | pos=connected[con_checked]; |
---|
| 825 | for(int i=0;i<cans_length;i++){ |
---|
| 826 | if (cans[i]<0) continue; |
---|
| 827 | if (has_t_rep(pos,cans[i],c)) |
---|
| 828 | { |
---|
| 829 | connected[connected_length]=cans[i]; |
---|
| 830 | connected_length++; |
---|
| 831 | cans[i]=-1; |
---|
| 832 | --not_yet_found; |
---|
| 833 | } |
---|
| 834 | } |
---|
| 835 | con_checked++; |
---|
| 836 | } |
---|
| 837 | if (connected_length<c->n){ |
---|
| 838 | connected[connected_length]=-1; |
---|
| 839 | } |
---|
| 840 | omfree(cans); |
---|
| 841 | return connected; |
---|
| 842 | } |
---|
[9cbb7a3] | 843 | static int* make_connections(int from, int to, poly bound, slimgb_alg* c) |
---|
[4f858ce] | 844 | { |
---|
| 845 | ideal I=c->S; |
---|
| 846 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 847 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 848 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 849 | cans[0]=to; |
---|
| 850 | int cans_length=1; |
---|
| 851 | connected[0]=from; |
---|
| 852 | int last_cans_pos=-1; |
---|
| 853 | int connected_length=1; |
---|
| 854 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 855 | |
---|
| 856 | int not_yet_found=cans_length; |
---|
| 857 | int con_checked=0; |
---|
| 858 | int pos; |
---|
| 859 | BOOLEAN can_find_more=TRUE; |
---|
| 860 | while(TRUE){ |
---|
| 861 | if ((con_checked<connected_length)&& (not_yet_found>0)){ |
---|
| 862 | pos=connected[con_checked]; |
---|
| 863 | for(int i=0;i<cans_length;i++){ |
---|
| 864 | if (cans[i]<0) continue; |
---|
| 865 | if (has_t_rep(pos,cans[i],c))//||(trivial_syzygie(pos,cans[i],bound,c)) |
---|
| 866 | { |
---|
| 867 | |
---|
| 868 | connected[connected_length]=cans[i]; |
---|
| 869 | connected_length++; |
---|
| 870 | cans[i]=-1; |
---|
| 871 | --not_yet_found; |
---|
| 872 | |
---|
| 873 | if (connected[connected_length-1]==to){ |
---|
| 874 | if (connected_length<c->n){ |
---|
| 875 | connected[connected_length]=-1; |
---|
| 876 | } |
---|
| 877 | omfree(cans); |
---|
| 878 | return connected; |
---|
| 879 | } |
---|
| 880 | } |
---|
| 881 | } |
---|
| 882 | con_checked++; |
---|
| 883 | } |
---|
| 884 | else |
---|
| 885 | { |
---|
| 886 | for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){ |
---|
| 887 | if (last_cans_pos==c->n){ |
---|
| 888 | if (connected_length<c->n){ |
---|
| 889 | connected[connected_length]=-1; |
---|
| 890 | } |
---|
| 891 | omfree(cans); |
---|
| 892 | return connected; |
---|
| 893 | } |
---|
| 894 | if ((last_cans_pos==from)||(last_cans_pos==to)) |
---|
| 895 | continue; |
---|
| 896 | if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){ |
---|
| 897 | cans[cans_length]=last_cans_pos; |
---|
| 898 | cans_length++; |
---|
| 899 | break; |
---|
| 900 | } |
---|
| 901 | } |
---|
| 902 | not_yet_found++; |
---|
| 903 | for (int i=0;i<con_checked;i++){ |
---|
| 904 | if (has_t_rep(connected[i],last_cans_pos,c)){ |
---|
| 905 | |
---|
| 906 | connected[connected_length]=last_cans_pos; |
---|
| 907 | connected_length++; |
---|
| 908 | cans[cans_length-1]=-1; |
---|
| 909 | |
---|
| 910 | --not_yet_found; |
---|
| 911 | if (connected[connected_length-1]==to){ |
---|
| 912 | if (connected_length<c->n){ |
---|
| 913 | connected[connected_length]=-1; |
---|
| 914 | } |
---|
| 915 | |
---|
| 916 | omfree(cans); |
---|
| 917 | return connected; |
---|
| 918 | } |
---|
| 919 | break; |
---|
| 920 | } |
---|
| 921 | } |
---|
| 922 | } |
---|
| 923 | } |
---|
| 924 | if (connected_length<c->n){ |
---|
| 925 | connected[connected_length]=-1; |
---|
| 926 | } |
---|
| 927 | |
---|
| 928 | omfree(cans); |
---|
| 929 | return connected; |
---|
| 930 | } |
---|
| 931 | #ifdef HEAD_BIN |
---|
| 932 | static inline poly p_MoveHead(poly p, omBin b) |
---|
| 933 | { |
---|
| 934 | poly np; |
---|
| 935 | omTypeAllocBin(poly, np, b); |
---|
| 936 | memmove(np, p, b->sizeW*sizeof(long)); |
---|
| 937 | omFreeBinAddr(p); |
---|
| 938 | return np; |
---|
| 939 | } |
---|
| 940 | #endif |
---|
| 941 | |
---|
| 942 | |
---|
[25061a] | 943 | static int simple_posInS_whelper(kStrategy strat, poly p, int len){ |
---|
| 944 | return 0; |
---|
| 945 | } |
---|
[4f858ce] | 946 | //len should be weighted length in char 0 |
---|
| 947 | |
---|
| 948 | |
---|
[25061a] | 949 | static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen) |
---|
| 950 | { |
---|
[4f858ce] | 951 | |
---|
| 952 | |
---|
[25061a] | 953 | if(strat->sl==-1) return 0; |
---|
| 954 | if (strat->lenSw) return pos_helper(strat,p,wlen,strat->lenSw,strat->S); |
---|
| 955 | return pos_helper(strat,p,len,strat->lenS,strat->S); |
---|
| 956 | // |
---|
| 957 | //if (strat->lenSw) setL=strat->lenSw; |
---|
| 958 | //int length=strat->sl; |
---|
| 959 | //int i; |
---|
| 960 | //int an = 0; |
---|
| 961 | //int en= length; |
---|
| 962 | // |
---|
| 963 | //if ((len>setL[length]) |
---|
| 964 | // || ((len==setL[length]) && (pLmCmp(set[length],p)== -1))) |
---|
| 965 | // return length+1; |
---|
| 966 | // |
---|
| 967 | //loop |
---|
| 968 | //{ |
---|
| 969 | // if (an >= en-1) |
---|
| 970 | // { |
---|
| 971 | // if ((len<setL[an]) |
---|
| 972 | // || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an; |
---|
| 973 | // return en; |
---|
| 974 | // } |
---|
| 975 | // i=(an+en) / 2; |
---|
| 976 | // if ((len<setL[i]) |
---|
| 977 | // || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i; |
---|
| 978 | // //else if ((len>setL[i]) |
---|
| 979 | // //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i; |
---|
| 980 | // else an=i; |
---|
| 981 | //} |
---|
[4f858ce] | 982 | } |
---|
[25061a] | 983 | |
---|
[4f858ce] | 984 | /*2 |
---|
| 985 | *if the leading term of p |
---|
| 986 | *divides the leading term of some S[i] it will be canceled |
---|
| 987 | */ |
---|
| 988 | static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k, |
---|
| 989 | kStrategy strat) |
---|
| 990 | { |
---|
| 991 | assume(p_sev == pGetShortExpVector(p)); |
---|
| 992 | if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return; |
---|
| 993 | if (l>=strat->lenS[*at]) return; |
---|
| 994 | if (TEST_OPT_PROT) |
---|
| 995 | PrintS("!"); |
---|
| 996 | mflush(); |
---|
| 997 | //pDelete(&strat->S[*at]); |
---|
| 998 | deleteInS((*at),strat); |
---|
| 999 | (*at)--; |
---|
| 1000 | (*k)--; |
---|
| 1001 | // assume(lenS_correct(strat)); |
---|
| 1002 | } |
---|
| 1003 | |
---|
| 1004 | |
---|
| 1005 | |
---|
| 1006 | static int iq_crit(const void* ap,const void* bp){ |
---|
| 1007 | |
---|
| 1008 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 1009 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 1010 | assume(a->i>a->j); |
---|
| 1011 | assume(b->i>b->j); |
---|
[5f2720f] | 1012 | |
---|
| 1013 | |
---|
| 1014 | if (a->deg<b->deg) return -1; |
---|
| 1015 | if (a->deg>b->deg) return 1; |
---|
[4f858ce] | 1016 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 1017 | if(comp!=0) |
---|
| 1018 | return comp; |
---|
| 1019 | if (a->expected_length<b->expected_length) return -1; |
---|
| 1020 | if (a->expected_length>b->expected_length) return 1; |
---|
| 1021 | if (a->j>b->j) return 1; |
---|
| 1022 | if (a->j<b->j) return -1; |
---|
| 1023 | return 0; |
---|
| 1024 | } |
---|
| 1025 | |
---|
[9cbb7a3] | 1026 | sorted_pair_node** add_to_basis_ideal_quotient(poly h, int i_pos, int j_pos,slimgb_alg* c, int* ip) |
---|
[4f858ce] | 1027 | { |
---|
| 1028 | |
---|
| 1029 | assume(h!=NULL); |
---|
[6d7605] | 1030 | #define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type)) |
---|
[4f858ce] | 1031 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 1032 | BOOLEAN R_found=FALSE; |
---|
| 1033 | void* hp; |
---|
| 1034 | |
---|
| 1035 | ++(c->n); |
---|
| 1036 | ++(c->S->ncols); |
---|
| 1037 | int i,j; |
---|
| 1038 | i=c->n-1; |
---|
[ec8a6b6] | 1039 | sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1040 | int spc=0; |
---|
[6d7605] | 1041 | if(c->n>c->array_lengths){ |
---|
| 1042 | c->array_lengths=c->array_lengths*2; |
---|
| 1043 | assume(c->array_lengths>=c->n); |
---|
| 1044 | ENLARGE(c->T_deg, int); |
---|
| 1045 | ENLARGE(c->tmp_pair_lm,poly); |
---|
| 1046 | ENLARGE(c->tmp_spn,sorted_pair_node*); |
---|
[e046042] | 1047 | |
---|
[6d7605] | 1048 | ENLARGE(c->short_Exps,long); |
---|
| 1049 | ENLARGE(c->lengths,int); |
---|
| 1050 | ENLARGE(c->states, char*); |
---|
| 1051 | ENLARGE(c->gcd_of_terms,poly); |
---|
[2d8ce9] | 1052 | //ENLARGE(c->S->m,poly); |
---|
| 1053 | |
---|
[6d7605] | 1054 | } |
---|
[2d8ce9] | 1055 | pEnlargeSet(&c->S->m,c->n-1,1); |
---|
[85eb7d] | 1056 | if (c->T_deg_full) |
---|
| 1057 | ENLARGE(c->T_deg_full,int); |
---|
[4f858ce] | 1058 | c->T_deg[i]=pTotaldegree(h); |
---|
| 1059 | if(c->T_deg_full){ |
---|
| 1060 | c->T_deg_full[i]=pTotaldegree_full(h); |
---|
| 1061 | } |
---|
[85eb7d] | 1062 | |
---|
| 1063 | |
---|
[4f858ce] | 1064 | c->tmp_pair_lm[i]=pOne_Special(c->r); |
---|
[85eb7d] | 1065 | |
---|
| 1066 | |
---|
[ec8a6b6] | 1067 | c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1068 | |
---|
| 1069 | |
---|
| 1070 | c->lengths[i]=pLength(h); |
---|
| 1071 | |
---|
| 1072 | c->gcd_of_terms[i]=gcd_of_terms(h,c->r); |
---|
[e046042] | 1073 | |
---|
[65c4dc] | 1074 | if (i>0) |
---|
| 1075 | c->states[i]=(char*) omalloc(i*sizeof(char)); |
---|
| 1076 | else |
---|
| 1077 | c->states[i]=NULL; |
---|
[85eb7d] | 1078 | |
---|
| 1079 | |
---|
[4f858ce] | 1080 | c->S->m[i]=h; |
---|
| 1081 | c->short_Exps[i]=p_GetShortExpVector(h,c->r); |
---|
[02e2f7] | 1082 | |
---|
[85eb7d] | 1083 | #undef ENLARGE |
---|
[4f858ce] | 1084 | for (j=0;j<i;j++){ |
---|
| 1085 | |
---|
| 1086 | //check product criterion |
---|
| 1087 | |
---|
| 1088 | c->states[i][j]=UNCALCULATED; |
---|
| 1089 | assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)== |
---|
| 1090 | p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)); |
---|
| 1091 | if(!c->F4_mode) |
---|
| 1092 | { |
---|
[457bd50] | 1093 | // assume(!(p_LmDivisibleBy(c->S->m[j],c->S->m[i],c->r))); |
---|
[4f858ce] | 1094 | } |
---|
| 1095 | |
---|
[02e2f7] | 1096 | if (_p_GetComp(c->S->m[i],c->r)!=_p_GetComp(c->S->m[j],c->r)){ |
---|
| 1097 | c->states[i][j]=UNIMPORTANT; |
---|
| 1098 | continue; |
---|
| 1099 | } else |
---|
[d491e3] | 1100 | if ((!c->nc) && (c->lengths[i]==1) && (c->lengths[j]==1)) |
---|
[4f858ce] | 1101 | c->states[i][j]=HASTREP; |
---|
[d491e3] | 1102 | else if ((!(c->nc)) && (pHasNotCF(c->S->m[i],c->S->m[j]))) |
---|
[4f858ce] | 1103 | { |
---|
| 1104 | c->easy_product_crit++; |
---|
| 1105 | c->states[i][j]=HASTREP; |
---|
| 1106 | } |
---|
| 1107 | else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)) |
---|
| 1108 | { |
---|
| 1109 | c->states[i][j]=HASTREP; |
---|
| 1110 | c->extended_product_crit++; |
---|
| 1111 | //PrintS("E"); |
---|
| 1112 | } |
---|
| 1113 | // if (c->states[i][j]==UNCALCULATED){ |
---|
| 1114 | |
---|
| 1115 | |
---|
| 1116 | // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); |
---|
| 1117 | // if (short_s) |
---|
| 1118 | // { |
---|
[02e2f7] | 1119 | assume(spc<=j); |
---|
| 1120 | sorted_pair_node* s=c->tmp_spn[spc];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1121 | s->i=si_max(i,j); |
---|
| 1122 | s->j=si_min(i,j); |
---|
| 1123 | assume(s->j==j); |
---|
| 1124 | s->expected_length=c->lengths[i]+c->lengths[j]-2; |
---|
| 1125 | |
---|
[02e2f7] | 1126 | poly lm=c->tmp_pair_lm[spc];//=pOne_Special(); |
---|
[4f858ce] | 1127 | |
---|
| 1128 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 1129 | pSetm(lm); |
---|
| 1130 | s->deg=pTotaldegree(lm); |
---|
[02e2f7] | 1131 | |
---|
| 1132 | if(c->T_deg_full)//Sugar |
---|
[4f858ce] | 1133 | { |
---|
| 1134 | int t_i=c->T_deg_full[s->i]-c->T_deg[s->i]; |
---|
| 1135 | int t_j=c->T_deg_full[s->j]-c->T_deg[s->j]; |
---|
| 1136 | s->deg+=si_max(t_i,t_j); |
---|
| 1137 | //Print("\n max: %d\n",max(t_i,t_j)); |
---|
| 1138 | } |
---|
| 1139 | s->lcm_of_lm=lm; |
---|
| 1140 | // pDelete(&short_s); |
---|
| 1141 | //assume(lm!=NULL); |
---|
| 1142 | nodes[spc]=s; |
---|
| 1143 | spc++; |
---|
[02e2f7] | 1144 | |
---|
[4f858ce] | 1145 | // } |
---|
| 1146 | //else |
---|
| 1147 | //{ |
---|
| 1148 | //c->states[i][j]=HASTREP; |
---|
| 1149 | //} |
---|
| 1150 | } |
---|
| 1151 | |
---|
[2bc80b] | 1152 | assume(spc<=i); |
---|
[4f858ce] | 1153 | //now ideal quotient crit |
---|
| 1154 | qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit); |
---|
| 1155 | |
---|
[ec8a6b6] | 1156 | sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1157 | int spc_final=0; |
---|
| 1158 | j=0; |
---|
| 1159 | while(j<spc) |
---|
| 1160 | { |
---|
| 1161 | int lower=j; |
---|
| 1162 | int upper; |
---|
| 1163 | BOOLEAN has=FALSE; |
---|
| 1164 | for(upper=lower+1;upper<spc;upper++) |
---|
| 1165 | { |
---|
| 1166 | |
---|
| 1167 | if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm)) |
---|
| 1168 | { |
---|
| 1169 | break; |
---|
| 1170 | } |
---|
| 1171 | if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c)) |
---|
| 1172 | has=TRUE; |
---|
| 1173 | |
---|
| 1174 | } |
---|
| 1175 | upper=upper-1; |
---|
| 1176 | int z; |
---|
| 1177 | assume(spc_final<=j); |
---|
| 1178 | for(z=0;z<spc_final;z++) |
---|
| 1179 | { |
---|
| 1180 | if(p_LmDivisibleBy(nodes_final[z]->lcm_of_lm,nodes[lower]->lcm_of_lm,c->r)) |
---|
| 1181 | { |
---|
| 1182 | has=TRUE; |
---|
| 1183 | break; |
---|
| 1184 | } |
---|
| 1185 | } |
---|
| 1186 | |
---|
| 1187 | if(has) |
---|
| 1188 | { |
---|
| 1189 | for(;lower<=upper;lower++) |
---|
| 1190 | { |
---|
| 1191 | //free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1192 | //omfree(nodes[lower]); |
---|
| 1193 | nodes[lower]=NULL; |
---|
| 1194 | } |
---|
| 1195 | j=upper+1; |
---|
| 1196 | continue; |
---|
| 1197 | } |
---|
| 1198 | else |
---|
| 1199 | { |
---|
| 1200 | nodes[lower]->lcm_of_lm=pCopy(nodes[lower]->lcm_of_lm); |
---|
[02e2f7] | 1201 | assume(_p_GetComp(c->S->m[nodes[lower]->i],c->r)==_p_GetComp(c->S->m[nodes[lower]->j],c->r)); |
---|
| 1202 | nodes_final[spc_final]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
| 1203 | |
---|
| 1204 | *(nodes_final[spc_final++])=*(nodes[lower]); |
---|
| 1205 | //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1206 | nodes[lower]=NULL; |
---|
| 1207 | for(lower=lower+1;lower<=upper;lower++) |
---|
| 1208 | { |
---|
| 1209 | // free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1210 | //omfree(nodes[lower]); |
---|
| 1211 | nodes[lower]=NULL; |
---|
| 1212 | } |
---|
| 1213 | j=upper+1; |
---|
| 1214 | continue; |
---|
| 1215 | } |
---|
| 1216 | } |
---|
| 1217 | |
---|
| 1218 | // Print("i:%d,spc_final:%d",i,spc_final); |
---|
| 1219 | |
---|
| 1220 | |
---|
| 1221 | |
---|
| 1222 | |
---|
| 1223 | assume(spc_final<=spc); |
---|
| 1224 | omfree(nodes); |
---|
| 1225 | nodes=NULL; |
---|
| 1226 | |
---|
| 1227 | add_to_reductors(c, h, c->lengths[c->n-1]); |
---|
| 1228 | //i=posInS(c->strat,c->strat->sl,h,0 ecart); |
---|
[d491e3] | 1229 | if (!(c->nc)){ |
---|
| 1230 | if (c->lengths[c->n-1]==1) |
---|
| 1231 | shorten_tails(c,c->S->m[c->n-1]); |
---|
| 1232 | } |
---|
[4f858ce] | 1233 | //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths |
---|
| 1234 | |
---|
| 1235 | //for(i=c->strat->sl; i>0;i--) |
---|
| 1236 | // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i); |
---|
| 1237 | if (c->Rcounter>50) { |
---|
| 1238 | c->Rcounter=0; |
---|
| 1239 | cleanS(c->strat,c); |
---|
| 1240 | } |
---|
| 1241 | if(!ip){ |
---|
[b75d13] | 1242 | qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2); |
---|
[4f858ce] | 1243 | |
---|
| 1244 | |
---|
[b75d13] | 1245 | c->apairs=spn_merge(c->apairs,c->pair_top+1,nodes_final,spc_final,c); |
---|
[4f858ce] | 1246 | c->pair_top+=spc_final; |
---|
| 1247 | clean_top_of_pair_list(c); |
---|
| 1248 | omfree(nodes_final); |
---|
| 1249 | return NULL; |
---|
| 1250 | } |
---|
| 1251 | { |
---|
| 1252 | *ip=spc_final; |
---|
| 1253 | return nodes_final; |
---|
| 1254 | } |
---|
| 1255 | |
---|
| 1256 | |
---|
| 1257 | |
---|
| 1258 | } |
---|
| 1259 | |
---|
| 1260 | |
---|
[9cbb7a3] | 1261 | static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) |
---|
[4f858ce] | 1262 | { |
---|
| 1263 | m=nInit(1); |
---|
| 1264 | if (h==NULL) return NULL; |
---|
| 1265 | |
---|
| 1266 | assume(len==pLength(h)); |
---|
| 1267 | kStrategy strat=c->strat; |
---|
| 1268 | if (0 > strat->sl) |
---|
| 1269 | { |
---|
| 1270 | return h; |
---|
| 1271 | } |
---|
| 1272 | int j; |
---|
| 1273 | |
---|
| 1274 | LObject P(h); |
---|
| 1275 | P.SetShortExpVector(); |
---|
| 1276 | P.bucket = kBucketCreate(currRing); |
---|
| 1277 | // BOOLEAN corr=lenS_correct(strat); |
---|
| 1278 | kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/); |
---|
[25061a] | 1279 | wlen_set lenSw=strat->lenS; |
---|
[d491e3] | 1280 | if (strat->lenSw!=NULL) |
---|
| 1281 | lenSw=strat->lenSw; |
---|
[4f858ce] | 1282 | //int max_pos=simple_posInS(strat,P.p); |
---|
| 1283 | loop |
---|
| 1284 | { |
---|
| 1285 | |
---|
| 1286 | j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P); |
---|
[d491e3] | 1287 | if ((j>=0) && ((!n)||(lenSw[j]<=n))) |
---|
[4f858ce] | 1288 | { |
---|
| 1289 | |
---|
| 1290 | |
---|
| 1291 | nNormalize(pGetCoeff(P.p)); |
---|
| 1292 | #ifdef KDEBUG |
---|
| 1293 | if (TEST_OPT_DEBUG) |
---|
| 1294 | { |
---|
| 1295 | PrintS("red:"); |
---|
| 1296 | wrp(h); |
---|
| 1297 | PrintS(" with "); |
---|
| 1298 | wrp(strat->S[j]); |
---|
| 1299 | } |
---|
| 1300 | #endif |
---|
| 1301 | |
---|
| 1302 | number coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1303 | strat->lenS[j]/*pLength(strat->S[j])*/, |
---|
| 1304 | strat->kNoether); |
---|
| 1305 | number m2=nMult(m,coef); |
---|
| 1306 | nDelete(&m); |
---|
| 1307 | m=m2; |
---|
| 1308 | nDelete(&coef); |
---|
| 1309 | h = kBucketGetLm(P.bucket); |
---|
| 1310 | |
---|
| 1311 | if (h==NULL) { |
---|
| 1312 | len=0; |
---|
| 1313 | kBucketDestroy(&P.bucket); |
---|
| 1314 | return |
---|
| 1315 | NULL;} |
---|
| 1316 | P.p=h; |
---|
| 1317 | P.t_p=NULL; |
---|
| 1318 | P.SetShortExpVector(); |
---|
| 1319 | #ifdef KDEBUG |
---|
| 1320 | if (TEST_OPT_DEBUG) |
---|
| 1321 | { |
---|
| 1322 | PrintS("\nto:"); |
---|
| 1323 | wrp(h); |
---|
| 1324 | PrintLn(); |
---|
| 1325 | } |
---|
| 1326 | #endif |
---|
| 1327 | } |
---|
| 1328 | else |
---|
| 1329 | { |
---|
| 1330 | kBucketClear(P.bucket,&(P.p),&len); |
---|
| 1331 | kBucketDestroy(&P.bucket); |
---|
| 1332 | pNormalize(P.p); |
---|
| 1333 | assume(len==(pLength(P.p))); |
---|
| 1334 | return P.p; |
---|
| 1335 | } |
---|
| 1336 | } |
---|
| 1337 | } |
---|
| 1338 | |
---|
| 1339 | |
---|
[d491e3] | 1340 | |
---|
[4f858ce] | 1341 | static poly redTailShort(poly h, kStrategy strat){ |
---|
| 1342 | |
---|
| 1343 | int sl=strat->sl; |
---|
| 1344 | int i; |
---|
| 1345 | int len=pLength(h); |
---|
| 1346 | for(i=0;i<=strat->sl;i++){ |
---|
[48457f] | 1347 | if((strat->lenS[i]>2) || ((strat->lenSw!=NULL) && (strat->lenSw[i]>2))) |
---|
[4f858ce] | 1348 | break; |
---|
| 1349 | } |
---|
| 1350 | return(redNFTail(h,i-1,strat, len)); |
---|
| 1351 | } |
---|
| 1352 | |
---|
[9cbb7a3] | 1353 | static void line_of_extended_prod(int fixpos,slimgb_alg* c){ |
---|
[4f858ce] | 1354 | if (c->gcd_of_terms[fixpos]==NULL) |
---|
| 1355 | { |
---|
| 1356 | c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r); |
---|
| 1357 | if (c->gcd_of_terms[fixpos]) |
---|
| 1358 | { |
---|
| 1359 | int i; |
---|
| 1360 | for(i=0;i<fixpos;i++) |
---|
| 1361 | if((c->states[fixpos][i]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c))) |
---|
| 1362 | { |
---|
| 1363 | c->states[fixpos][i]=HASTREP; |
---|
| 1364 | c->extended_product_crit++; |
---|
| 1365 | } |
---|
| 1366 | for(i=fixpos+1;i<c->n;i++) |
---|
| 1367 | if((c->states[i][fixpos]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c))) |
---|
| 1368 | { c->states[i][fixpos]=HASTREP; |
---|
| 1369 | c->extended_product_crit++; |
---|
| 1370 | } |
---|
| 1371 | } |
---|
| 1372 | } |
---|
| 1373 | } |
---|
[9cbb7a3] | 1374 | static void c_S_element_changed_hook(int pos, slimgb_alg* c){ |
---|
[4f858ce] | 1375 | length_one_crit(c,pos, c->lengths[pos]); |
---|
[d491e3] | 1376 | if (!c->nc) |
---|
| 1377 | line_of_extended_prod(pos,c); |
---|
[4f858ce] | 1378 | } |
---|
| 1379 | class poly_tree_node { |
---|
| 1380 | public: |
---|
| 1381 | poly p; |
---|
| 1382 | poly_tree_node* l; |
---|
| 1383 | poly_tree_node* r; |
---|
| 1384 | int n; |
---|
| 1385 | poly_tree_node(int sn):l(NULL),r(NULL),n(sn){} |
---|
| 1386 | }; |
---|
| 1387 | class exp_number_builder{ |
---|
| 1388 | public: |
---|
| 1389 | poly_tree_node* top_level; |
---|
| 1390 | int n; |
---|
| 1391 | int get_n(poly p); |
---|
| 1392 | exp_number_builder():top_level(0),n(0){} |
---|
| 1393 | }; |
---|
| 1394 | int exp_number_builder::get_n(poly p){ |
---|
| 1395 | poly_tree_node** node=&top_level; |
---|
| 1396 | while(*node!=NULL){ |
---|
| 1397 | int c=pLmCmp(p,(*node)->p); |
---|
| 1398 | if (c==0) return (*node)->n; |
---|
| 1399 | if (c==-1) node=&((*node)->r); |
---|
| 1400 | else |
---|
| 1401 | node=&((*node)->l); |
---|
| 1402 | } |
---|
| 1403 | (*node)= new poly_tree_node(n); |
---|
| 1404 | n++; |
---|
| 1405 | (*node)->p=pLmInit(p); |
---|
| 1406 | return (*node)->n; |
---|
| 1407 | } |
---|
| 1408 | |
---|
| 1409 | //mac_polys exp are smaller iff they are greater by monomial ordering |
---|
| 1410 | //corresponding to solving linear equations notation |
---|
[196cdf] | 1411 | |
---|
[b553e5] | 1412 | //! obsolete |
---|
[4f858ce] | 1413 | struct int_poly_pair{ |
---|
| 1414 | poly p; |
---|
| 1415 | int n; |
---|
| 1416 | }; |
---|
| 1417 | |
---|
[196cdf] | 1418 | |
---|
[b553e5] | 1419 | //! obsolete |
---|
[4f858ce] | 1420 | void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset){ |
---|
| 1421 | if(!k) return; |
---|
| 1422 | t2ippa_rec(ip,ia,k->l,offset); |
---|
| 1423 | ip[offset]=k->p; |
---|
| 1424 | ia[k->n]=offset; |
---|
| 1425 | ++offset; |
---|
| 1426 | |
---|
| 1427 | t2ippa_rec(ip,ia,k->r,offset); |
---|
| 1428 | delete k; |
---|
| 1429 | } |
---|
[196cdf] | 1430 | |
---|
[b553e5] | 1431 | //! obsolete |
---|
[4f858ce] | 1432 | void t2ippa(poly* ip,int* ia,exp_number_builder & e){ |
---|
| 1433 | |
---|
| 1434 | int o=0; |
---|
| 1435 | t2ippa_rec(ip,ia,e.top_level,o); |
---|
| 1436 | } |
---|
| 1437 | int anti_poly_order(const void* a, const void* b){ |
---|
| 1438 | return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p ); |
---|
| 1439 | } |
---|
[81306a] | 1440 | |
---|
[4f858ce] | 1441 | BOOLEAN is_valid_ro(red_object & ro){ |
---|
| 1442 | red_object r2=ro; |
---|
| 1443 | ro.validate(); |
---|
[bddc9d] | 1444 | if ((r2.p!=ro.p)||(r2.sev!=ro.sev)) return FALSE; |
---|
[4f858ce] | 1445 | return TRUE; |
---|
| 1446 | } |
---|
[196cdf] | 1447 | |
---|
| 1448 | //*obsolete |
---|
[9cbb7a3] | 1449 | void pre_comp(poly* p,int & pn,slimgb_alg* c){ |
---|
[4f858ce] | 1450 | if(!(pn)) |
---|
| 1451 | return; |
---|
[ec8a6b6] | 1452 | mac_poly* q=(mac_poly*) omalloc(pn*sizeof(mac_poly)); |
---|
[4f858ce] | 1453 | int i; |
---|
| 1454 | exp_number_builder e; |
---|
| 1455 | for(i=0;i<pn;i++){ |
---|
| 1456 | assume(p[i]!=NULL); |
---|
| 1457 | q[i]=new mac_poly_r(); |
---|
| 1458 | q[i]->exp=e.get_n(p[i]); |
---|
| 1459 | q[i]->coef=nCopy(p[i]->coef); |
---|
| 1460 | |
---|
| 1461 | mac_poly qa=q[i]; |
---|
| 1462 | poly pa=p[i]; |
---|
| 1463 | while(pa->next!=NULL){ |
---|
| 1464 | qa->next = new mac_poly_r(); |
---|
| 1465 | qa=qa->next; |
---|
| 1466 | pa=pa->next, |
---|
| 1467 | qa->exp=e.get_n(pa); |
---|
| 1468 | qa->coef=nCopy(pa->coef); |
---|
| 1469 | |
---|
| 1470 | |
---|
| 1471 | } |
---|
| 1472 | qa->next=NULL; |
---|
| 1473 | pDelete(&p[i]); |
---|
| 1474 | } |
---|
[ec8a6b6] | 1475 | poly* ip= (poly*)omalloc (e.n*sizeof(poly)); |
---|
| 1476 | int* ia=(int*) omalloc (e.n*sizeof(int)); |
---|
[4f858ce] | 1477 | t2ippa(ip,ia,e); |
---|
| 1478 | for(i=0;i<pn;i++){ |
---|
| 1479 | mac_poly mp=q[i]; |
---|
| 1480 | while(mp!=NULL){ |
---|
| 1481 | mp->exp=ia[mp->exp]; |
---|
| 1482 | mp=mp->next; |
---|
| 1483 | } |
---|
| 1484 | |
---|
| 1485 | } |
---|
| 1486 | //gaus reduction start |
---|
| 1487 | int col, row; |
---|
| 1488 | col=0; |
---|
| 1489 | row=0; |
---|
| 1490 | assume(pn>0); |
---|
| 1491 | while(row<pn-1){ |
---|
| 1492 | //row is the row where pivot should be |
---|
| 1493 | // row== pn-1 means we have only to act on one row so no red nec. |
---|
| 1494 | //we assume further all rows till the pn-1 row are non-zero |
---|
| 1495 | |
---|
| 1496 | //select column |
---|
| 1497 | int i; |
---|
| 1498 | col=q[row]->exp; |
---|
| 1499 | int found_in_row=row; |
---|
| 1500 | for(i=row;i<pn;i++){ |
---|
| 1501 | if(q[i]->exp<col){ |
---|
| 1502 | col=q[i]->exp; |
---|
| 1503 | found_in_row=i; |
---|
| 1504 | } |
---|
| 1505 | |
---|
| 1506 | } |
---|
| 1507 | //select pivot |
---|
| 1508 | int act_l=mac_length(q[found_in_row]); |
---|
| 1509 | for(i=row+1;i<pn;i++){ |
---|
| 1510 | if((q[i]->exp==col)&&(mac_length(q[i])<act_l)){ |
---|
| 1511 | found_in_row=i; |
---|
| 1512 | act_l=mac_length(q[i]);//should be optimized here |
---|
| 1513 | } |
---|
| 1514 | } |
---|
| 1515 | mac_poly h=q[row]; |
---|
| 1516 | q[row]=q[found_in_row]; |
---|
| 1517 | q[found_in_row]=h; |
---|
| 1518 | |
---|
| 1519 | //reduction |
---|
| 1520 | for(i=row+1;i<pn;i++){ |
---|
| 1521 | if(q[i]->exp==q[row]->exp){ |
---|
| 1522 | |
---|
| 1523 | number c1=nNeg(nCopy(q[i]->coef)); |
---|
| 1524 | number c2=q[row]->coef; |
---|
| 1525 | //use checkcoeff later |
---|
| 1526 | mac_mult_cons(q[i],c2); |
---|
| 1527 | q[i]=mac_p_add_ff_qq(q[i],c1,q[row]); |
---|
| 1528 | } |
---|
| 1529 | |
---|
| 1530 | |
---|
| 1531 | |
---|
| 1532 | } |
---|
| 1533 | for(i=row+1;i<pn;i++){ |
---|
| 1534 | if(q[i]==NULL){ |
---|
| 1535 | q[i]=q[pn-1]; |
---|
| 1536 | pn--; |
---|
| 1537 | if(i!=pn){i--;} |
---|
| 1538 | } |
---|
| 1539 | } |
---|
| 1540 | |
---|
| 1541 | row++; |
---|
| 1542 | } |
---|
| 1543 | |
---|
| 1544 | |
---|
| 1545 | //gaus reduction end |
---|
| 1546 | |
---|
| 1547 | for(i=0;i<pn;i++){ |
---|
| 1548 | poly pa; |
---|
| 1549 | mac_poly qa; |
---|
| 1550 | p[i]=pLmInit(ip[q[i]->exp]); |
---|
| 1551 | pSetCoeff(p[i],q[i]->coef); |
---|
| 1552 | pa=p[i]; |
---|
| 1553 | qa=q[i]; |
---|
| 1554 | while(qa->next!=NULL){ |
---|
| 1555 | qa=qa->next; |
---|
| 1556 | pa->next=pLmInit(ip[qa->exp]); |
---|
| 1557 | pa=pa->next; |
---|
| 1558 | pa->coef=qa->coef; |
---|
| 1559 | } |
---|
| 1560 | pa->next=NULL; |
---|
| 1561 | } |
---|
| 1562 | for(i=0;i<e.n;i++){ |
---|
| 1563 | pDelete(&ip[i]); |
---|
| 1564 | } |
---|
| 1565 | omfree(ip); |
---|
| 1566 | omfree(ia); |
---|
| 1567 | } |
---|
| 1568 | |
---|
[9cbb7a3] | 1569 | static void go_on (slimgb_alg* c){ |
---|
[4f858ce] | 1570 | //set limit of 1000 for multireductions, at the moment for |
---|
| 1571 | //programming reasons |
---|
| 1572 | int i=0; |
---|
| 1573 | c->average_length=0; |
---|
| 1574 | for(i=0;i<c->n;i++){ |
---|
| 1575 | c->average_length+=c->lengths[i]; |
---|
| 1576 | } |
---|
| 1577 | c->average_length=c->average_length/c->n; |
---|
| 1578 | i=0; |
---|
[ec8a6b6] | 1579 | poly* p=(poly*) omalloc((PAR_N+1)*sizeof(poly));//nullterminated |
---|
[4f858ce] | 1580 | |
---|
| 1581 | int curr_deg=-1; |
---|
| 1582 | while(i<PAR_N){ |
---|
| 1583 | sorted_pair_node* s=top_pair(c);//here is actually chain criterium done |
---|
| 1584 | if (!s) break; |
---|
| 1585 | if(curr_deg>=0){ |
---|
| 1586 | if (s->deg >curr_deg) break; |
---|
| 1587 | } |
---|
| 1588 | |
---|
| 1589 | else curr_deg=s->deg; |
---|
| 1590 | quick_pop_pair(c); |
---|
| 1591 | if(s->i>=0){ |
---|
[d491e3] | 1592 | //be careful replace_pair use createShortSpoly which is not noncommutative |
---|
[4f858ce] | 1593 | //replace_pair(s->i,s->j,c); |
---|
| 1594 | if(s->i==s->j) { |
---|
| 1595 | free_sorted_pair_node(s,c->r); |
---|
| 1596 | continue; |
---|
| 1597 | } |
---|
| 1598 | } |
---|
| 1599 | poly h; |
---|
[d491e3] | 1600 | if(s->i>=0){ |
---|
| 1601 | if (!c->nc) |
---|
| 1602 | h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r); |
---|
| 1603 | else |
---|
| 1604 | h= nc_CreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r); |
---|
| 1605 | } |
---|
[4f858ce] | 1606 | else |
---|
| 1607 | h=s->lcm_of_lm; |
---|
| 1608 | if(s->i>=0) |
---|
| 1609 | now_t_rep(s->j,s->i,c); |
---|
| 1610 | number coef; |
---|
| 1611 | int mlen=pLength(h); |
---|
[d491e3] | 1612 | if (!c->nc){ |
---|
| 1613 | h=redNF2(h,c,mlen,coef,2); |
---|
| 1614 | redTailShort(h,c->strat); |
---|
| 1615 | nDelete(&coef); |
---|
| 1616 | } |
---|
[4f858ce] | 1617 | free_sorted_pair_node(s,c->r); |
---|
| 1618 | if(!h) continue; |
---|
| 1619 | int len=pLength(h); |
---|
| 1620 | p[i]=h; |
---|
| 1621 | |
---|
| 1622 | i++; |
---|
| 1623 | } |
---|
| 1624 | p[i]=NULL; |
---|
| 1625 | // pre_comp(p,i,c); |
---|
| 1626 | if(i==0){ |
---|
| 1627 | omfree(p); |
---|
| 1628 | return; |
---|
| 1629 | } |
---|
[ec8a6b6] | 1630 | red_object* buf=(red_object*) omalloc(i*sizeof(red_object)); |
---|
[4f858ce] | 1631 | c->normal_forms+=i; |
---|
| 1632 | int j; |
---|
| 1633 | for(j=0;j<i;j++){ |
---|
| 1634 | buf[j].p=p[j]; |
---|
| 1635 | buf[j].sev=pGetShortExpVector(p[j]); |
---|
| 1636 | buf[j].bucket = kBucketCreate(currRing); |
---|
| 1637 | int len=pLength(p[j]); |
---|
| 1638 | kBucketInit(buf[j].bucket,buf[j].p,len); |
---|
| 1639 | } |
---|
| 1640 | omfree(p); |
---|
| 1641 | qsort(buf,i,sizeof(red_object),red_object_better_gen); |
---|
| 1642 | // Print("\ncurr_deg:%i\n",curr_deg); |
---|
| 1643 | if (TEST_OPT_PROT) |
---|
| 1644 | Print("M[%i, ",i); |
---|
| 1645 | #ifdef FIND_DETERMINISTIC |
---|
[ec8a6b6] | 1646 | c->modifiedS=(BOOLEAN*) omalloc((c->strat->sl+1)*sizeof(BOOLEAN)); |
---|
| 1647 | c->expandS=(poly*) omalloc((1)*sizeof(poly)); |
---|
[4f858ce] | 1648 | c->expandS[0]=NULL; |
---|
| 1649 | int z2; |
---|
| 1650 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1651 | c->modifiedS[z2]=FALSE; |
---|
| 1652 | #endif |
---|
| 1653 | multi_reduction(buf, i, c); |
---|
| 1654 | #ifdef TGB_DEBUG |
---|
| 1655 | { |
---|
| 1656 | int k; |
---|
| 1657 | for(k=0;k<i;k++) |
---|
| 1658 | { |
---|
| 1659 | assume(kFindDivisibleByInS_easy(c->strat,buf[k])<0); |
---|
| 1660 | int k2; |
---|
| 1661 | for(k2=0;k2<i;k2++) |
---|
| 1662 | { |
---|
| 1663 | if(k==k2) continue; |
---|
| 1664 | assume((!(p_LmDivisibleBy(buf[k].p,buf[k2].p,c->r)))||(wrp(buf[k].p),Print(" k %d k2 %d ",k,k2),wrp(buf[k2].p),FALSE)); |
---|
| 1665 | } |
---|
| 1666 | } |
---|
| 1667 | } |
---|
| 1668 | #endif |
---|
| 1669 | //resort S |
---|
| 1670 | #ifdef FIND_DETERMINISTIC |
---|
| 1671 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1672 | { |
---|
| 1673 | if (c->modifiedS[z2]) |
---|
| 1674 | { |
---|
[25061a] | 1675 | wlen_type qual; |
---|
| 1676 | int new_pos; |
---|
[6bcdc53] | 1677 | if (c->strat->lenSw!=NULL) |
---|
[25061a] | 1678 | new_pos=simple_posInS(c->strat,c->strat->S[z2],strat->lenS[z2],strat->Sw[z2]); |
---|
[4f858ce] | 1679 | else |
---|
[25061a] | 1680 | new_pos=simple_posInS(c->strat,c->strat->S[z2],strat->lenS[z2],lenS[z2]); |
---|
| 1681 | |
---|
[4f858ce] | 1682 | if (new_pos<z2) |
---|
| 1683 | { |
---|
[25061a] | 1684 | move_forward_in_S(z2,new_pos,c->strat); |
---|
[4f858ce] | 1685 | } |
---|
[25061a] | 1686 | |
---|
| 1687 | assume(new_pos<=z2); |
---|
[4f858ce] | 1688 | } |
---|
| 1689 | } |
---|
| 1690 | for(z2=0;c->expandS[z2]!=NULL;z2++) |
---|
| 1691 | { |
---|
| 1692 | add_to_reductors(c,c->expandS[z2],pLength(c->expandS[z2])); |
---|
| 1693 | // PrintS("E"); |
---|
| 1694 | } |
---|
| 1695 | omfree(c->modifiedS); |
---|
| 1696 | c->modifiedS=NULL; |
---|
| 1697 | omfree(c->expandS); |
---|
| 1698 | c->expandS=NULL; |
---|
| 1699 | #endif |
---|
| 1700 | if (TEST_OPT_PROT) |
---|
| 1701 | Print("%i]",i); |
---|
| 1702 | // for(j=0;j<i;j++){ |
---|
| 1703 | // if(buf[j].p==NULL) PrintS("\n ZERO ALERT \n"); |
---|
| 1704 | // int z; |
---|
| 1705 | // for(z=0;z<j;z++){ |
---|
| 1706 | // if (pLmEqual(buf[z].p, buf[j].p)) |
---|
| 1707 | // PrintS("\n Critical Warning!!!! \n"); |
---|
| 1708 | |
---|
| 1709 | // } |
---|
| 1710 | // } |
---|
[ec8a6b6] | 1711 | int* ibuf=(int*) omalloc(i*sizeof(int)); |
---|
| 1712 | sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**)); |
---|
[4f858ce] | 1713 | for(j=0;j<i;j++) |
---|
| 1714 | { |
---|
| 1715 | int len; |
---|
| 1716 | poly p; |
---|
| 1717 | buf[j].flatten(); |
---|
| 1718 | kBucketClear(buf[j].bucket,&p, &len); |
---|
| 1719 | kBucketDestroy(&buf[j].bucket); |
---|
| 1720 | // delete buf[j]; |
---|
| 1721 | //remember to free res here |
---|
[d491e3] | 1722 | if (!c->nc) |
---|
| 1723 | p=redTailShort(p, c->strat); |
---|
[4f858ce] | 1724 | sbuf[j]=add_to_basis_ideal_quotient(p,-1,-1,c,ibuf+j); |
---|
| 1725 | //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j); |
---|
| 1726 | } |
---|
| 1727 | int sum=0; |
---|
| 1728 | for(j=0;j<i;j++){ |
---|
| 1729 | sum+=ibuf[j]; |
---|
| 1730 | } |
---|
[ec8a6b6] | 1731 | sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 1732 | int partsum=0; |
---|
| 1733 | for(j=0;j<i;j++) |
---|
| 1734 | { |
---|
| 1735 | memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*)); |
---|
| 1736 | omfree(sbuf[j]); |
---|
| 1737 | partsum+=ibuf[j]; |
---|
| 1738 | } |
---|
| 1739 | |
---|
[b75d13] | 1740 | qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2); |
---|
| 1741 | c->apairs=spn_merge(c->apairs,c->pair_top+1,big_sbuf,sum,c); |
---|
[4f858ce] | 1742 | c->pair_top+=sum; |
---|
| 1743 | clean_top_of_pair_list(c); |
---|
| 1744 | omfree(big_sbuf); |
---|
| 1745 | omfree(sbuf); |
---|
| 1746 | omfree(ibuf); |
---|
| 1747 | omfree(buf); |
---|
| 1748 | #ifdef TGB_DEBUG |
---|
| 1749 | int z; |
---|
| 1750 | for(z=1;z<=c->pair_top;z++) |
---|
| 1751 | { |
---|
| 1752 | assume(pair_better(c->apairs[z],c->apairs[z-1],c)); |
---|
| 1753 | } |
---|
| 1754 | #endif |
---|
| 1755 | return; |
---|
| 1756 | } |
---|
| 1757 | |
---|
| 1758 | |
---|
[518fb78] | 1759 | |
---|
[4f858ce] | 1760 | #ifdef REDTAIL_S |
---|
| 1761 | |
---|
| 1762 | static poly redNFTail (poly h,const int sl,kStrategy strat, int len) |
---|
| 1763 | { |
---|
| 1764 | if (h==NULL) return NULL; |
---|
| 1765 | pTest(h); |
---|
| 1766 | if (0 > sl) |
---|
| 1767 | return h; |
---|
| 1768 | if (pNext(h)==NULL) return h; |
---|
| 1769 | |
---|
| 1770 | int j; |
---|
| 1771 | poly res=h; |
---|
| 1772 | poly act=res; |
---|
| 1773 | LObject P(pNext(h)); |
---|
| 1774 | pNext(res)=NULL; |
---|
| 1775 | P.bucket = kBucketCreate(currRing); |
---|
| 1776 | len--; |
---|
| 1777 | h=P.p; |
---|
| 1778 | if (len <=0) len=pLength(h); |
---|
| 1779 | kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/); |
---|
| 1780 | pTest(h); |
---|
| 1781 | loop |
---|
| 1782 | { |
---|
| 1783 | P.p=h; |
---|
| 1784 | P.t_p=NULL; |
---|
| 1785 | P.SetShortExpVector(); |
---|
| 1786 | loop |
---|
| 1787 | { |
---|
| 1788 | j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P); |
---|
| 1789 | if (j>=0) |
---|
| 1790 | { |
---|
| 1791 | #ifdef REDTAIL_PROT |
---|
| 1792 | PrintS("r"); |
---|
| 1793 | #endif |
---|
| 1794 | nNormalize(pGetCoeff(P.p)); |
---|
| 1795 | #ifdef KDEBUG |
---|
| 1796 | if (TEST_OPT_DEBUG) |
---|
| 1797 | { |
---|
| 1798 | PrintS("red tail:"); |
---|
| 1799 | wrp(h); |
---|
| 1800 | PrintS(" with "); |
---|
| 1801 | wrp(strat->S[j]); |
---|
| 1802 | } |
---|
| 1803 | #endif |
---|
| 1804 | number coef; |
---|
| 1805 | pTest(strat->S[j]); |
---|
| 1806 | coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1807 | strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether); |
---|
| 1808 | pMult_nn(res,coef); |
---|
| 1809 | nDelete(&coef); |
---|
| 1810 | h = kBucketGetLm(P.bucket); |
---|
| 1811 | pTest(h); |
---|
| 1812 | if (h==NULL) |
---|
| 1813 | { |
---|
| 1814 | #ifdef REDTAIL_PROT |
---|
| 1815 | PrintS(" "); |
---|
| 1816 | #endif |
---|
| 1817 | kBucketDestroy(&P.bucket); |
---|
| 1818 | return res; |
---|
| 1819 | } |
---|
| 1820 | pTest(h); |
---|
| 1821 | P.p=h; |
---|
| 1822 | P.t_p=NULL; |
---|
| 1823 | P.SetShortExpVector(); |
---|
| 1824 | #ifdef KDEBUG |
---|
| 1825 | if (TEST_OPT_DEBUG) |
---|
| 1826 | { |
---|
| 1827 | PrintS("\nto tail:"); |
---|
| 1828 | wrp(h); |
---|
| 1829 | PrintLn(); |
---|
| 1830 | } |
---|
| 1831 | #endif |
---|
| 1832 | } |
---|
| 1833 | else |
---|
| 1834 | { |
---|
| 1835 | #ifdef REDTAIL_PROT |
---|
| 1836 | PrintS("n"); |
---|
| 1837 | #endif |
---|
| 1838 | break; |
---|
| 1839 | } |
---|
| 1840 | } /* end loop current mon */ |
---|
| 1841 | // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); |
---|
| 1842 | //act->next=tmp;pIter(act); |
---|
| 1843 | act->next=kBucketExtractLm(P.bucket);pIter(act); |
---|
| 1844 | h = kBucketGetLm(P.bucket); |
---|
| 1845 | if (h==NULL) |
---|
| 1846 | { |
---|
| 1847 | #ifdef REDTAIL_PROT |
---|
| 1848 | PrintS(" "); |
---|
| 1849 | #endif |
---|
| 1850 | kBucketDestroy(&P.bucket); |
---|
| 1851 | return res; |
---|
| 1852 | } |
---|
| 1853 | pTest(h); |
---|
| 1854 | } |
---|
| 1855 | } |
---|
| 1856 | #endif |
---|
| 1857 | |
---|
| 1858 | |
---|
| 1859 | //try to fill, return FALSE iff queue is empty |
---|
| 1860 | |
---|
| 1861 | //transfers ownership of m to mat |
---|
| 1862 | void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m){ |
---|
| 1863 | assume(mat->mp[row]==NULL); |
---|
| 1864 | mat->mp[row]=m; |
---|
| 1865 | #ifdef TGB_DEBUG |
---|
| 1866 | mac_poly r=m; |
---|
| 1867 | while(r){ |
---|
| 1868 | assume(r->exp<mat->columns); |
---|
| 1869 | r=r->next; |
---|
| 1870 | } |
---|
| 1871 | #endif |
---|
| 1872 | } |
---|
| 1873 | poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){ |
---|
| 1874 | poly p=NULL; |
---|
| 1875 | poly* set_this=&p; |
---|
| 1876 | mac_poly r=mat->mp[row]; |
---|
| 1877 | mat->mp[row]=NULL; |
---|
| 1878 | while(r) |
---|
| 1879 | { |
---|
| 1880 | (*set_this)=pLmInit(monoms[monom_index-1-r->exp]); |
---|
| 1881 | pSetCoeff((*set_this),r->coef); |
---|
| 1882 | set_this=&((*set_this)->next); |
---|
| 1883 | mac_poly old=r; |
---|
| 1884 | r=r->next; |
---|
| 1885 | delete old; |
---|
| 1886 | |
---|
| 1887 | } |
---|
| 1888 | return p; |
---|
| 1889 | |
---|
| 1890 | } |
---|
| 1891 | |
---|
| 1892 | |
---|
| 1893 | |
---|
| 1894 | |
---|
| 1895 | |
---|
| 1896 | |
---|
| 1897 | |
---|
| 1898 | |
---|
| 1899 | |
---|
| 1900 | |
---|
| 1901 | |
---|
| 1902 | static int poly_crit(const void* ap1, const void* ap2){ |
---|
| 1903 | poly p1,p2; |
---|
| 1904 | p1=*((poly*) ap1); |
---|
| 1905 | p2=*((poly*)ap2); |
---|
| 1906 | |
---|
| 1907 | int c=pLmCmp(p1,p2); |
---|
| 1908 | if (c !=0) return c; |
---|
| 1909 | int l1=pLength(p1); |
---|
| 1910 | int l2=pLength(p2); |
---|
| 1911 | if (l1<l2) return -1; |
---|
| 1912 | if (l1>l2) return 1; |
---|
| 1913 | return 0; |
---|
| 1914 | } |
---|
[e1b6944] | 1915 | slimgb_alg::slimgb_alg(ideal I, BOOLEAN F4){ |
---|
[4f858ce] | 1916 | |
---|
[68ae61] | 1917 | |
---|
| 1918 | r=currRing; |
---|
[d491e3] | 1919 | nc=rIsPluralRing(r); |
---|
[54e883b] | 1920 | |
---|
[68ae61] | 1921 | is_homog=TRUE; |
---|
[4f858ce] | 1922 | { |
---|
| 1923 | int hz; |
---|
| 1924 | for(hz=0;hz<IDELEMS(I);hz++){ |
---|
| 1925 | assume(I->m[hz]!=NULL); |
---|
| 1926 | int d=pTotaldegree(I->m[hz]); |
---|
| 1927 | poly t=I->m[hz]->next; |
---|
| 1928 | while(t) |
---|
| 1929 | { |
---|
[68ae61] | 1930 | if (d!=pTotaldegree(t,r)) |
---|
| 1931 | { |
---|
| 1932 | is_homog=FALSE; |
---|
| 1933 | break; |
---|
| 1934 | } |
---|
| 1935 | t=t->next; |
---|
[4f858ce] | 1936 | } |
---|
[68ae61] | 1937 | if(!(is_homog)) break; |
---|
[4f858ce] | 1938 | } |
---|
| 1939 | } |
---|
| 1940 | // Print("is homog:%d",c->is_homog); |
---|
| 1941 | void* h; |
---|
| 1942 | poly hp; |
---|
| 1943 | int i,j; |
---|
[68ae61] | 1944 | to_destroy=NULL; |
---|
| 1945 | easy_product_crit=0; |
---|
| 1946 | extended_product_crit=0; |
---|
| 1947 | if (rField_is_Zp(r)) |
---|
| 1948 | is_char0=FALSE; |
---|
[4f858ce] | 1949 | else |
---|
[68ae61] | 1950 | is_char0=TRUE; |
---|
[4f858ce] | 1951 | //not fully correct |
---|
[68ae61] | 1952 | //(rChar()==0); |
---|
[0516ab] | 1953 | F4_mode=F4; |
---|
[d491e3] | 1954 | |
---|
[0516ab] | 1955 | if ((!F4_mode)&&(!is_homog) &&(pLexOrder)){ |
---|
| 1956 | this->doubleSugar=TRUE; |
---|
| 1957 | } |
---|
| 1958 | else this->doubleSugar=FALSE; |
---|
[68ae61] | 1959 | reduction_steps=0; |
---|
| 1960 | last_index=-1; |
---|
[4f858ce] | 1961 | |
---|
[68ae61] | 1962 | F=NULL; |
---|
| 1963 | F_minus=NULL; |
---|
[4f858ce] | 1964 | |
---|
[68ae61] | 1965 | Rcounter=0; |
---|
[4f858ce] | 1966 | |
---|
[68ae61] | 1967 | soon_free=NULL; |
---|
[4f858ce] | 1968 | |
---|
[68ae61] | 1969 | tmp_lm=pOne(); |
---|
[4f858ce] | 1970 | |
---|
[68ae61] | 1971 | normal_forms=0; |
---|
| 1972 | current_degree=1; |
---|
[4f858ce] | 1973 | |
---|
[68ae61] | 1974 | max_pairs=5*I->idelems(); |
---|
[4f858ce] | 1975 | |
---|
[68ae61] | 1976 | apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*max_pairs); |
---|
| 1977 | pair_top=-1; |
---|
[4f858ce] | 1978 | |
---|
| 1979 | int n=I->idelems(); |
---|
[68ae61] | 1980 | array_lengths=n; |
---|
[6d7605] | 1981 | |
---|
[09ab660] | 1982 | |
---|
[4f858ce] | 1983 | i=0; |
---|
[68ae61] | 1984 | this->n=0; |
---|
| 1985 | T_deg=(int*) omalloc(n*sizeof(int)); |
---|
| 1986 | if((!(is_homog)) &&(pLexOrder)) |
---|
| 1987 | T_deg_full=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 1988 | else |
---|
[68ae61] | 1989 | T_deg_full=NULL; |
---|
| 1990 | tmp_pair_lm=(poly*) omalloc(n*sizeof(poly)); |
---|
| 1991 | tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 1992 | lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long)); |
---|
| 1993 | #ifdef HEAD_BIN |
---|
[68ae61] | 1994 | HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long)); |
---|
[4f858ce] | 1995 | #endif |
---|
| 1996 | /* omUnGetSpecBin(&(c->HeadBin)); */ |
---|
[ec8a6b6] | 1997 | h=omalloc(n*sizeof(char*)); |
---|
[68ae61] | 1998 | states=(char**) h; |
---|
[ec8a6b6] | 1999 | h=omalloc(n*sizeof(int)); |
---|
[68ae61] | 2000 | lengths=(int*) h; |
---|
[e046042] | 2001 | |
---|
[68ae61] | 2002 | gcd_of_terms=(poly*) omalloc(n*sizeof(poly)); |
---|
[e046042] | 2003 | |
---|
[68ae61] | 2004 | short_Exps=(long*) omalloc(n*sizeof(long)); |
---|
[f3c849] | 2005 | if (F4_mode) |
---|
[2bc80b] | 2006 | S=idInit(n,I->rank); |
---|
[f3c849] | 2007 | else |
---|
[2bc80b] | 2008 | S=idInit(1,I->rank); |
---|
[68ae61] | 2009 | strat=new skStrategy; |
---|
| 2010 | strat->syzComp = 0; |
---|
| 2011 | initBuchMoraCrit(strat); |
---|
| 2012 | initBuchMoraPos(strat); |
---|
| 2013 | strat->initEcart = initEcartBBA; |
---|
| 2014 | strat->enterS = enterSBba; |
---|
| 2015 | strat->sl = -1; |
---|
[4f858ce] | 2016 | i=n; |
---|
[6d7605] | 2017 | i=1;//some strange bug else |
---|
[4f858ce] | 2018 | /* initS(c->S,NULL,c->strat); */ |
---|
[68ae61] | 2019 | /* intS start: */ |
---|
[4f858ce] | 2020 | // i=((i+IDELEMS(c->S)+15)/16)*16; |
---|
[68ae61] | 2021 | strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/ |
---|
| 2022 | strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long)); |
---|
[4f858ce] | 2023 | /*initsevS(i);*/ |
---|
[68ae61] | 2024 | strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/ |
---|
| 2025 | strat->fromQ=NULL; |
---|
| 2026 | strat->Shdl=idInit(1,1); |
---|
| 2027 | strat->S=strat->Shdl->m; |
---|
| 2028 | strat->lenS=(int*)omAlloc0(i*sizeof(int)); |
---|
| 2029 | if((is_char0)||((pLexOrder) &&(!is_homog))) |
---|
[6bcdc53] | 2030 | strat->lenSw=(int*)omAlloc0(i*sizeof(wlen_type)); |
---|
[4f858ce] | 2031 | else |
---|
[68ae61] | 2032 | strat->lenSw=NULL; |
---|
[4f858ce] | 2033 | sorted_pair_node* si; |
---|
| 2034 | assume(n>0); |
---|
[68ae61] | 2035 | add_to_basis_ideal_quotient(I->m[0],-1,-1,this,NULL); |
---|
[4f858ce] | 2036 | |
---|
[68ae61] | 2037 | assume(strat->sl==strat->Shdl->idelems()-1); |
---|
[4f858ce] | 2038 | if(!(F4_mode)) |
---|
| 2039 | { |
---|
| 2040 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
| 2041 | { |
---|
| 2042 | // add_to_basis(I->m[i],-1,-1,c); |
---|
[ec8a6b6] | 2043 | si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 2044 | si->i=-1; |
---|
| 2045 | si->j=-1; |
---|
| 2046 | si->expected_length=pLength(I->m[i]); |
---|
| 2047 | si->deg=pTotaldegree(I->m[i]); |
---|
[68ae61] | 2048 | if (!rField_is_Zp(r)){ |
---|
| 2049 | pCleardenom(I->m[i]); |
---|
[4f858ce] | 2050 | } |
---|
| 2051 | si->lcm_of_lm=I->m[i]; |
---|
| 2052 | |
---|
| 2053 | // c->apairs[n-1-i]=si; |
---|
[68ae61] | 2054 | apairs[n-i-1]=si; |
---|
| 2055 | ++(pair_top); |
---|
[4f858ce] | 2056 | } |
---|
| 2057 | } |
---|
| 2058 | else |
---|
| 2059 | { |
---|
[68ae61] | 2060 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
| 2061 | add_to_basis_ideal_quotient(I->m[i],-1,-1,this,NULL); |
---|
[4f858ce] | 2062 | } |
---|
[68ae61] | 2063 | for(i=0;i<I->idelems();i++) |
---|
[4f858ce] | 2064 | { |
---|
[68ae61] | 2065 | I->m[i]=NULL; |
---|
[4f858ce] | 2066 | } |
---|
[68ae61] | 2067 | idDelete(&I); |
---|
| 2068 | } |
---|
| 2069 | slimgb_alg::~slimgb_alg(){ |
---|
| 2070 | int i,j; |
---|
| 2071 | slimgb_alg* c=this; |
---|
[4f858ce] | 2072 | while(c->to_destroy) |
---|
| 2073 | { |
---|
| 2074 | pDelete(&(c->to_destroy->p)); |
---|
| 2075 | poly_list_node* old=c->to_destroy; |
---|
| 2076 | c->to_destroy=c->to_destroy->next; |
---|
| 2077 | omfree(old); |
---|
| 2078 | } |
---|
| 2079 | while(c->F) |
---|
| 2080 | { |
---|
| 2081 | for(i=0;i<c->F->size;i++){ |
---|
| 2082 | pDelete(&(c->F->mp[i].m)); |
---|
| 2083 | } |
---|
| 2084 | omfree(c->F->mp); |
---|
| 2085 | c->F->mp=NULL; |
---|
| 2086 | mp_array_list* old=c->F; |
---|
| 2087 | c->F=c->F->next; |
---|
| 2088 | omfree(old); |
---|
| 2089 | } |
---|
| 2090 | while(c->F_minus) |
---|
| 2091 | { |
---|
| 2092 | for(i=0;i<c->F_minus->size;i++){ |
---|
| 2093 | pDelete(&(c->F_minus->p[i])); |
---|
| 2094 | } |
---|
| 2095 | omfree(c->F_minus->p); |
---|
| 2096 | c->F_minus->p=NULL; |
---|
| 2097 | poly_array_list* old=c->F_minus; |
---|
| 2098 | c->F_minus=c->F_minus->next; |
---|
| 2099 | omfree(old); |
---|
| 2100 | } |
---|
[76b225] | 2101 | for(int z=1 /* zero length at 0 */;z<c->n;z++){ |
---|
[4f858ce] | 2102 | omfree(c->states[z]); |
---|
| 2103 | } |
---|
| 2104 | omfree(c->states); |
---|
| 2105 | omfree(c->lengths); |
---|
| 2106 | for(int z=0;z<c->n;z++) |
---|
| 2107 | { |
---|
| 2108 | pDelete(&c->tmp_pair_lm[z]); |
---|
| 2109 | omfree(c->tmp_spn[z]); |
---|
| 2110 | } |
---|
| 2111 | omfree(c->tmp_pair_lm); |
---|
| 2112 | omfree(c->tmp_spn); |
---|
| 2113 | |
---|
| 2114 | omfree(c->T_deg); |
---|
| 2115 | if(c->T_deg_full) |
---|
| 2116 | omfree(c->T_deg_full); |
---|
| 2117 | |
---|
| 2118 | omFree(c->strat->ecartS); |
---|
| 2119 | omFree(c->strat->sevS); |
---|
| 2120 | // initsevS(i); |
---|
| 2121 | omFree(c->strat->S_2_R); |
---|
| 2122 | |
---|
| 2123 | |
---|
| 2124 | omFree(c->strat->lenS); |
---|
| 2125 | |
---|
| 2126 | if(c->strat->lenSw) omFree(c->strat->lenSw); |
---|
| 2127 | |
---|
| 2128 | |
---|
| 2129 | |
---|
| 2130 | |
---|
| 2131 | for(i=0;i<c->n;i++){ |
---|
| 2132 | if(c->gcd_of_terms[i]) |
---|
| 2133 | pDelete(&(c->gcd_of_terms[i])); |
---|
| 2134 | } |
---|
| 2135 | omfree(c->gcd_of_terms); |
---|
| 2136 | |
---|
| 2137 | omfree(c->apairs); |
---|
| 2138 | if (TEST_OPT_PROT) |
---|
| 2139 | { |
---|
| 2140 | Print("calculated %d NFs\n",c->normal_forms); |
---|
| 2141 | Print("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit); |
---|
| 2142 | } |
---|
| 2143 | int deleted_form_c_s=0; |
---|
| 2144 | |
---|
| 2145 | for(i=0;i<=c->strat->sl;i++){ |
---|
| 2146 | if (!c->strat->S[i]) continue; |
---|
| 2147 | BOOLEAN found=FALSE; |
---|
| 2148 | for(j=0;j<c->n;j++){ |
---|
| 2149 | if (c->S->m[j]==c->strat->S[i]){ |
---|
[68ae61] | 2150 | found=TRUE; |
---|
| 2151 | break; |
---|
[4f858ce] | 2152 | } |
---|
| 2153 | } |
---|
| 2154 | if(!found) pDelete(&c->strat->S[i]); |
---|
| 2155 | } |
---|
| 2156 | // for(i=0;i<c->n;i++){ |
---|
| 2157 | // if (c->rep[i]!=i){ |
---|
| 2158 | // // for(j=0;j<=c->strat->sl;j++){ |
---|
| 2159 | // // if(c->strat->S[j]==c->S->m[i]){ |
---|
| 2160 | // // c->strat->S[j]=NULL; |
---|
| 2161 | // // break; |
---|
| 2162 | // // } |
---|
| 2163 | // // } |
---|
| 2164 | // // PrintS("R_delete"); |
---|
| 2165 | // pDelete(&c->S->m[i]); |
---|
| 2166 | // } |
---|
| 2167 | // } |
---|
| 2168 | |
---|
[dd414d] | 2169 | |
---|
[4f858ce] | 2170 | for(i=0;i<c->n;i++) |
---|
| 2171 | { |
---|
| 2172 | assume(c->S->m[i]!=NULL); |
---|
| 2173 | for(j=0;j<c->n;j++) |
---|
| 2174 | { |
---|
| 2175 | if((c->S->m[j]==NULL)||(i==j)) |
---|
[68ae61] | 2176 | continue; |
---|
[4f858ce] | 2177 | assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
[68ae61] | 2178 | c->S->m[i],~c->short_Exps[i], |
---|
| 2179 | c->r)==p_LmDivisibleBy(c->S->m[j], |
---|
| 2180 | c->S->m[i], |
---|
| 2181 | c->r)); |
---|
[4f858ce] | 2182 | if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
[68ae61] | 2183 | c->S->m[i],~c->short_Exps[i], |
---|
| 2184 | c->r)) |
---|
[4f858ce] | 2185 | { |
---|
[68ae61] | 2186 | pDelete(&c->S->m[i]); |
---|
| 2187 | break; |
---|
[4f858ce] | 2188 | } |
---|
| 2189 | } |
---|
| 2190 | } |
---|
| 2191 | omfree(c->short_Exps); |
---|
[e046042] | 2192 | |
---|
[68ae61] | 2193 | |
---|
| 2194 | ideal I=c->S; |
---|
[4f858ce] | 2195 | |
---|
| 2196 | IDELEMS(I)=c->n; |
---|
| 2197 | |
---|
| 2198 | idSkipZeroes(I); |
---|
| 2199 | for(i=0;i<=c->strat->sl;i++) |
---|
| 2200 | c->strat->S[i]=NULL; |
---|
| 2201 | id_Delete(&c->strat->Shdl,c->r); |
---|
| 2202 | pDelete(&c->tmp_lm); |
---|
| 2203 | omUnGetSpecBin(&lm_bin); |
---|
| 2204 | delete c->strat; |
---|
[68ae61] | 2205 | } |
---|
| 2206 | ideal t_rep_gb(ring r,ideal arg_I, BOOLEAN F4_mode){ |
---|
[1821d6] | 2207 | |
---|
| 2208 | // 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))); |
---|
| 2209 | |
---|
[68ae61] | 2210 | if (TEST_OPT_PROT) |
---|
| 2211 | if (F4_mode) |
---|
| 2212 | PrintS("F4 Modus \n"); |
---|
| 2213 | |
---|
| 2214 | //debug_Ideal=arg_debug_Ideal; |
---|
| 2215 | //if (debug_Ideal) PrintS("DebugIdeal received\n"); |
---|
| 2216 | // Print("Idelems %i \n----------\n",IDELEMS(arg_I)); |
---|
| 2217 | ideal I=idCompactify(arg_I); |
---|
| 2218 | if (idIs0(I)) return I; |
---|
| 2219 | |
---|
| 2220 | qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit); |
---|
| 2221 | //Print("Idelems %i \n----------\n",IDELEMS(I)); |
---|
| 2222 | //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg)); |
---|
[e1b6944] | 2223 | slimgb_alg* c=new slimgb_alg(I, F4_mode); |
---|
[68ae61] | 2224 | |
---|
| 2225 | int i; |
---|
| 2226 | while(c->pair_top>=0) |
---|
| 2227 | { |
---|
| 2228 | if(F4_mode) |
---|
| 2229 | go_on_F4(c); |
---|
| 2230 | else |
---|
| 2231 | go_on(c); |
---|
| 2232 | } |
---|
| 2233 | I=c->S; |
---|
| 2234 | delete c; |
---|
[83f7ec] | 2235 | if (TEST_OPT_REDSB){ |
---|
| 2236 | ideal erg=kInterRed(I,NULL); |
---|
| 2237 | assume(I!=erg); |
---|
| 2238 | id_Delete(&I, currRing); |
---|
| 2239 | return erg; |
---|
| 2240 | } |
---|
[227a50] | 2241 | //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func); |
---|
[2bc80b] | 2242 | assume(I->rank==idRankFreeModule(I)); |
---|
[4f858ce] | 2243 | return(I); |
---|
| 2244 | } |
---|
[9cbb7a3] | 2245 | void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c){ |
---|
[4f858ce] | 2246 | int i,j; |
---|
| 2247 | if (arg_i==arg_j){ |
---|
| 2248 | return; |
---|
| 2249 | } |
---|
| 2250 | if (arg_i>arg_j){ |
---|
| 2251 | i=arg_j; |
---|
| 2252 | j=arg_i; |
---|
| 2253 | } else { |
---|
| 2254 | i=arg_i; |
---|
| 2255 | j=arg_j; |
---|
| 2256 | } |
---|
| 2257 | c->states[j][i]=HASTREP; |
---|
| 2258 | } |
---|
[9cbb7a3] | 2259 | static void soon_t_rep(const int& arg_i, const int& arg_j, slimgb_alg* c) |
---|
[4f858ce] | 2260 | { |
---|
| 2261 | assume(0<=arg_i); |
---|
| 2262 | assume(0<=arg_j); |
---|
| 2263 | assume(arg_i<c->n); |
---|
| 2264 | assume(arg_j<c->n); |
---|
| 2265 | int i,j; |
---|
| 2266 | if (arg_i==arg_j){ |
---|
| 2267 | return; |
---|
| 2268 | } |
---|
| 2269 | if (arg_i>arg_j){ |
---|
| 2270 | i=arg_j; |
---|
| 2271 | j=arg_i; |
---|
| 2272 | } else { |
---|
| 2273 | i=arg_i; |
---|
| 2274 | j=arg_j; |
---|
| 2275 | } |
---|
| 2276 | if (! |
---|
| 2277 | (c->states[j][i]==HASTREP)) |
---|
| 2278 | c->states[j][i]=SOONTREP; |
---|
| 2279 | } |
---|
[9cbb7a3] | 2280 | static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state){ |
---|
[4f858ce] | 2281 | assume(0<=arg_i); |
---|
| 2282 | assume(0<=arg_j); |
---|
| 2283 | assume(arg_i<state->n); |
---|
| 2284 | assume(arg_j<state->n); |
---|
| 2285 | if (arg_i==arg_j) |
---|
| 2286 | { |
---|
| 2287 | return (TRUE); |
---|
| 2288 | } |
---|
| 2289 | if (arg_i>arg_j) |
---|
| 2290 | { |
---|
| 2291 | return (state->states[arg_i][arg_j]==HASTREP); |
---|
| 2292 | } else |
---|
| 2293 | { |
---|
| 2294 | return (state->states[arg_j][arg_i]==HASTREP); |
---|
| 2295 | } |
---|
| 2296 | } |
---|
| 2297 | static int pLcmDeg(poly a, poly b) |
---|
| 2298 | { |
---|
| 2299 | int i; |
---|
| 2300 | int n=0; |
---|
| 2301 | for (i=pVariables; i; i--) |
---|
| 2302 | { |
---|
| 2303 | n+=si_max( pGetExp(a,i), pGetExp(b,i)); |
---|
| 2304 | } |
---|
| 2305 | return n; |
---|
| 2306 | |
---|
| 2307 | } |
---|
| 2308 | |
---|
| 2309 | |
---|
| 2310 | |
---|
[9cbb7a3] | 2311 | static void shorten_tails(slimgb_alg* c, poly monom) |
---|
[4f858ce] | 2312 | { |
---|
| 2313 | return; |
---|
| 2314 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 2315 | for(int i=0;i<c->n;i++) |
---|
| 2316 | { |
---|
| 2317 | //enter tail |
---|
[e046042] | 2318 | |
---|
[4f858ce] | 2319 | if (c->S->m[i]==NULL) continue; |
---|
| 2320 | poly tail=c->S->m[i]->next; |
---|
| 2321 | poly prev=c->S->m[i]; |
---|
| 2322 | BOOLEAN did_something=FALSE; |
---|
| 2323 | while((tail!=NULL)&& (pLmCmp(tail, monom)>=0)) |
---|
| 2324 | { |
---|
| 2325 | if (p_LmDivisibleBy(monom,tail,c->r)) |
---|
| 2326 | { |
---|
| 2327 | did_something=TRUE; |
---|
| 2328 | prev->next=tail->next; |
---|
| 2329 | tail->next=NULL; |
---|
| 2330 | p_Delete(& tail,c->r); |
---|
| 2331 | tail=prev; |
---|
| 2332 | //PrintS("Shortened"); |
---|
| 2333 | c->lengths[i]--; |
---|
| 2334 | } |
---|
| 2335 | prev=tail; |
---|
| 2336 | tail=tail->next; |
---|
| 2337 | } |
---|
| 2338 | if (did_something) |
---|
| 2339 | { |
---|
| 2340 | int new_pos; |
---|
[25061a] | 2341 | wlen_type q; |
---|
[4f858ce] | 2342 | q=pQuality(c->S->m[i],c,c->lengths[i]); |
---|
[25061a] | 2343 | new_pos=simple_posInS(c->strat,c->S->m[i],c->lengths[i],q); |
---|
[4f858ce] | 2344 | |
---|
| 2345 | int old_pos=-1; |
---|
| 2346 | //assume new_pos<old_pos |
---|
| 2347 | for (int z=0;z<=c->strat->sl;z++) |
---|
| 2348 | { |
---|
| 2349 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 2350 | { |
---|
| 2351 | old_pos=z; |
---|
| 2352 | break; |
---|
| 2353 | } |
---|
| 2354 | } |
---|
| 2355 | if (old_pos== -1) |
---|
| 2356 | for (int z=new_pos-1;z>=0;z--) |
---|
| 2357 | { |
---|
| 2358 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 2359 | { |
---|
| 2360 | old_pos=z; |
---|
| 2361 | break; |
---|
| 2362 | } |
---|
| 2363 | } |
---|
| 2364 | assume(old_pos>=0); |
---|
| 2365 | assume(new_pos<=old_pos); |
---|
| 2366 | assume(pLength(c->strat->S[old_pos])==c->lengths[i]); |
---|
| 2367 | c->strat->lenS[old_pos]=c->lengths[i]; |
---|
| 2368 | if (c->strat->lenSw) |
---|
| 2369 | c->strat->lenSw[old_pos]=q; |
---|
| 2370 | |
---|
| 2371 | if (new_pos<old_pos) |
---|
| 2372 | move_forward_in_S(old_pos,new_pos,c->strat); |
---|
| 2373 | |
---|
| 2374 | length_one_crit(c,i,c->lengths[i]); |
---|
| 2375 | } |
---|
| 2376 | } |
---|
| 2377 | } |
---|
[9cbb7a3] | 2378 | static sorted_pair_node* pop_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2379 | clean_top_of_pair_list(c); |
---|
| 2380 | |
---|
| 2381 | if(c->pair_top<0) return NULL; |
---|
| 2382 | else return (c->apairs[c->pair_top--]); |
---|
| 2383 | } |
---|
[9cbb7a3] | 2384 | sorted_pair_node* top_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2385 | super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here |
---|
| 2386 | |
---|
| 2387 | if(c->pair_top<0) return NULL; |
---|
| 2388 | else return (c->apairs[c->pair_top]); |
---|
| 2389 | } |
---|
[9cbb7a3] | 2390 | sorted_pair_node* quick_pop_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2391 | if(c->pair_top<0) return NULL; |
---|
| 2392 | else return (c->apairs[c->pair_top--]); |
---|
| 2393 | } |
---|
[9cbb7a3] | 2394 | static BOOLEAN no_pairs(slimgb_alg* c){ |
---|
[4f858ce] | 2395 | clean_top_of_pair_list(c); |
---|
| 2396 | return (c->pair_top==-1); |
---|
| 2397 | } |
---|
| 2398 | |
---|
| 2399 | |
---|
[9cbb7a3] | 2400 | static void super_clean_top_of_pair_list(slimgb_alg* c){ |
---|
[4f858ce] | 2401 | while((c->pair_top>=0) |
---|
| 2402 | && (c->apairs[c->pair_top]->i>=0) |
---|
| 2403 | && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))) |
---|
| 2404 | { |
---|
| 2405 | |
---|
| 2406 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 2407 | c->pair_top--; |
---|
| 2408 | |
---|
| 2409 | } |
---|
| 2410 | } |
---|
[9cbb7a3] | 2411 | void clean_top_of_pair_list(slimgb_alg* c){ |
---|
[4f858ce] | 2412 | while((c->pair_top>=0) && (c->apairs[c->pair_top]->i>=0) && (!state_is(UNCALCULATED,c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))){ |
---|
| 2413 | |
---|
| 2414 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 2415 | c->pair_top--; |
---|
| 2416 | |
---|
| 2417 | } |
---|
| 2418 | } |
---|
[9cbb7a3] | 2419 | static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, slimgb_alg* c){ |
---|
[4f858ce] | 2420 | assume(0<=arg_i); |
---|
| 2421 | assume(0<=arg_j); |
---|
| 2422 | assume(arg_i<c->n); |
---|
| 2423 | assume(arg_j<c->n); |
---|
| 2424 | if (arg_i==arg_j) |
---|
| 2425 | { |
---|
| 2426 | return (TRUE); |
---|
| 2427 | } |
---|
| 2428 | if (arg_i>arg_j) |
---|
| 2429 | { |
---|
| 2430 | return (c->states[arg_i][arg_j]==state); |
---|
| 2431 | } |
---|
| 2432 | else return(c->states[arg_j][arg_i]==state); |
---|
| 2433 | } |
---|
[b75d13] | 2434 | void free_sorted_pair_node(sorted_pair_node* s, ring r){ |
---|
[4f858ce] | 2435 | if (s->i>=0) |
---|
| 2436 | p_Delete(&s->lcm_of_lm,r); |
---|
| 2437 | omfree(s); |
---|
| 2438 | } |
---|
[9cbb7a3] | 2439 | static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c){ |
---|
[4f858ce] | 2440 | if (a->deg<b->deg) return TRUE; |
---|
| 2441 | if (a->deg>b->deg) return FALSE; |
---|
| 2442 | |
---|
| 2443 | // if (a->expected_length<b->expected_length) return TRUE; |
---|
| 2444 | // if (a->expected_length>b->expected_length) return FALSE; |
---|
| 2445 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 2446 | if (comp==1) return FALSE; |
---|
| 2447 | if (-1==comp) return TRUE; |
---|
| 2448 | if (a->i+a->j<b->i+b->j) return TRUE; |
---|
| 2449 | if (a->i+a->j>b->i+b->j) return FALSE; |
---|
| 2450 | if (a->i<b->i) return TRUE; |
---|
| 2451 | if (a->i>b->i) return FALSE; |
---|
| 2452 | return TRUE; |
---|
| 2453 | } |
---|
| 2454 | |
---|
[b75d13] | 2455 | static int tgb_pair_better_gen(const void* ap,const void* bp){ |
---|
[4f858ce] | 2456 | |
---|
| 2457 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 2458 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 2459 | assume(a->i>a->j); |
---|
| 2460 | assume(b->i>b->j); |
---|
| 2461 | if (a->deg<b->deg) return -1; |
---|
| 2462 | if (a->deg>b->deg) return 1; |
---|
| 2463 | |
---|
| 2464 | |
---|
| 2465 | // if (a->expected_length<b->expected_length) return -1; |
---|
| 2466 | // if (a->expected_length>b->expected_length) return 1; |
---|
| 2467 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 2468 | |
---|
| 2469 | if (comp==1) return 1; |
---|
| 2470 | if (-1==comp) return -1; |
---|
| 2471 | if (a->i+a->j<b->i+b->j) return -1; |
---|
| 2472 | if (a->i+a->j>b->i+b->j) return 1; |
---|
| 2473 | if (a->i<b->i) return -1; |
---|
| 2474 | if (a->i>b->i) return 1; |
---|
| 2475 | return 0; |
---|
| 2476 | } |
---|
| 2477 | |
---|
| 2478 | |
---|
| 2479 | static poly gcd_of_terms(poly p, ring r){ |
---|
| 2480 | int max_g_0=0; |
---|
| 2481 | assume(p!=NULL); |
---|
| 2482 | int i; |
---|
| 2483 | poly m=pOne(); |
---|
| 2484 | poly t; |
---|
| 2485 | for (i=pVariables; i; i--) |
---|
| 2486 | { |
---|
| 2487 | pSetExp(m,i, pGetExp(p,i)); |
---|
| 2488 | if (max_g_0==0) |
---|
| 2489 | if (pGetExp(m,i)>0) |
---|
| 2490 | max_g_0=i; |
---|
| 2491 | } |
---|
| 2492 | |
---|
| 2493 | t=p->next; |
---|
| 2494 | while (t!=NULL){ |
---|
| 2495 | |
---|
| 2496 | if (max_g_0==0) break; |
---|
| 2497 | for (i=max_g_0; i; i--) |
---|
| 2498 | { |
---|
| 2499 | pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i))); |
---|
| 2500 | if (max_g_0==i) |
---|
| 2501 | if (pGetExp(m,i)==0) |
---|
| 2502 | max_g_0=0; |
---|
| 2503 | if ((max_g_0==0) && (pGetExp(m,i)>0)){ |
---|
| 2504 | max_g_0=i; |
---|
| 2505 | } |
---|
| 2506 | } |
---|
| 2507 | t=t->next; |
---|
| 2508 | } |
---|
| 2509 | // for (i=pVariables;i;i--) |
---|
| 2510 | // { |
---|
| 2511 | // if(pGetExp(m,i)>0) |
---|
| 2512 | // return m; |
---|
| 2513 | // } |
---|
| 2514 | if (max_g_0>0) |
---|
| 2515 | return m; |
---|
| 2516 | pDelete(&m); |
---|
| 2517 | return NULL; |
---|
| 2518 | } |
---|
| 2519 | static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m) |
---|
| 2520 | { |
---|
| 2521 | |
---|
| 2522 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 2523 | return FALSE; |
---|
| 2524 | int i = 1; |
---|
| 2525 | loop |
---|
| 2526 | { |
---|
| 2527 | if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0)) return FALSE; |
---|
| 2528 | if (i == pVariables) return TRUE; |
---|
| 2529 | i++; |
---|
| 2530 | } |
---|
| 2531 | } |
---|
| 2532 | |
---|
| 2533 | |
---|
| 2534 | //for impl reasons may return false if the the normal product criterion matches |
---|
[9cbb7a3] | 2535 | static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c){ |
---|
[d491e3] | 2536 | if (c->nc) |
---|
| 2537 | return FALSE; |
---|
[4f858ce] | 2538 | if(gcd1==NULL) return FALSE; |
---|
| 2539 | if(gcd2==NULL) return FALSE; |
---|
| 2540 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 2541 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 2542 | gcd1->next=NULL; |
---|
| 2543 | if (m==NULL) return FALSE; |
---|
| 2544 | |
---|
| 2545 | BOOLEAN erg=pHasNotCFExtended(p1,p2,m); |
---|
| 2546 | pDelete(&m); |
---|
| 2547 | return erg; |
---|
| 2548 | } |
---|
| 2549 | static poly kBucketGcd(kBucket* b, ring r) |
---|
| 2550 | { |
---|
| 2551 | int s=0; |
---|
| 2552 | int i; |
---|
| 2553 | poly m, n; |
---|
| 2554 | BOOLEAN initialized=FALSE; |
---|
| 2555 | for (i=MAX_BUCKET-1;i>=0;i--) |
---|
| 2556 | { |
---|
| 2557 | if (b->buckets[i]!=NULL){ |
---|
| 2558 | if (!initialized){ |
---|
| 2559 | m=gcd_of_terms(b->buckets[i],r); |
---|
| 2560 | initialized=TRUE; |
---|
| 2561 | if (m==NULL) return NULL; |
---|
| 2562 | } |
---|
| 2563 | else |
---|
| 2564 | { |
---|
| 2565 | n=gcd_of_terms(b->buckets[i],r); |
---|
| 2566 | if (n==NULL) { |
---|
| 2567 | pDelete(&m); |
---|
| 2568 | return NULL; |
---|
| 2569 | } |
---|
| 2570 | n->next=m; |
---|
| 2571 | poly t=gcd_of_terms(n,r); |
---|
| 2572 | n->next=NULL; |
---|
| 2573 | pDelete(&m); |
---|
| 2574 | pDelete(&n); |
---|
| 2575 | m=t; |
---|
| 2576 | if (m==NULL) return NULL; |
---|
| 2577 | |
---|
| 2578 | } |
---|
| 2579 | } |
---|
| 2580 | } |
---|
| 2581 | return m; |
---|
| 2582 | } |
---|
| 2583 | |
---|
| 2584 | |
---|
| 2585 | |
---|
| 2586 | |
---|
[9cbb7a3] | 2587 | static inline int quality_of_pos_in_strat_S(int pos, slimgb_alg* c){ |
---|
[4f858ce] | 2588 | if (c->strat->lenSw!=NULL) return c->strat->lenSw[pos]; |
---|
| 2589 | return c->strat->lenS[pos]; |
---|
| 2590 | } |
---|
[54e883b] | 2591 | static inline int quality_of_pos_in_strat_S_mult_high(int pos, poly high, slimgb_alg* c) |
---|
| 2592 | //meant only for nc |
---|
| 2593 | { |
---|
| 2594 | poly m=pOne(); |
---|
| 2595 | pExpVectorDiff(m,high ,c->strat->S[pos]); |
---|
| 2596 | poly product=nc_mm_Mult_p(m, pCopy(c->strat->S[pos]), c->r); |
---|
| 2597 | int erg=pQuality(product,c); |
---|
| 2598 | pDelete(&m); |
---|
| 2599 | pDelete(&product); |
---|
| 2600 | return erg; |
---|
| 2601 | } |
---|
[4f858ce] | 2602 | |
---|
[9cbb7a3] | 2603 | static void multi_reduction_lls_trick(red_object* los, int losl,slimgb_alg* c,find_erg & erg){ |
---|
[4f858ce] | 2604 | erg.expand=NULL; |
---|
| 2605 | BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS |
---|
| 2606 | if(erg.fromS){ |
---|
| 2607 | if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p)) |
---|
| 2608 | { |
---|
| 2609 | int i; |
---|
| 2610 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 2611 | int best=erg.to_reduce_u+1; |
---|
| 2612 | /* |
---|
| 2613 | for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){ |
---|
| 2614 | int qc=los[i].guess_quality(c); |
---|
| 2615 | if (qc<quality_a){ |
---|
| 2616 | best=i; |
---|
| 2617 | quality_a=qc; |
---|
| 2618 | } |
---|
| 2619 | } |
---|
| 2620 | if(best!=erg.to_reduce_u+1){*/ |
---|
| 2621 | int qc; |
---|
| 2622 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2623 | if(qc<quality_a){ |
---|
| 2624 | los[best].flatten(); |
---|
| 2625 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2626 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2627 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2628 | if(qc<quality_a){ |
---|
| 2629 | red_object h=los[erg.to_reduce_u]; |
---|
| 2630 | los[erg.to_reduce_u]=los[best]; |
---|
| 2631 | los[best]=h; |
---|
| 2632 | swap_roles=TRUE; |
---|
| 2633 | } |
---|
| 2634 | else |
---|
| 2635 | swap_roles=FALSE; |
---|
| 2636 | } |
---|
| 2637 | else{ |
---|
| 2638 | |
---|
| 2639 | swap_roles=FALSE; |
---|
| 2640 | } |
---|
| 2641 | |
---|
| 2642 | } |
---|
| 2643 | else |
---|
| 2644 | { |
---|
| 2645 | if (erg.to_reduce_u>erg.to_reduce_l){ |
---|
| 2646 | |
---|
| 2647 | int i; |
---|
| 2648 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
[56a6cc] | 2649 | if (c->nc) |
---|
| 2650 | quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c); |
---|
[4f858ce] | 2651 | int best=erg.to_reduce_u+1; |
---|
| 2652 | int qc; |
---|
| 2653 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2654 | assume(qc==los[best].guess_quality(c)); |
---|
| 2655 | if(qc<quality_a){ |
---|
| 2656 | los[best].flatten(); |
---|
| 2657 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2658 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2659 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2660 | //(best!=erg.to_reduce_u+1) |
---|
| 2661 | if(qc<quality_a){ |
---|
| 2662 | red_object h=los[erg.to_reduce_l]; |
---|
| 2663 | los[erg.to_reduce_l]=los[best]; |
---|
| 2664 | los[best]=h; |
---|
| 2665 | erg.reduce_by=erg.to_reduce_l; |
---|
| 2666 | erg.fromS=FALSE; |
---|
| 2667 | erg.to_reduce_l++; |
---|
| 2668 | } |
---|
| 2669 | } |
---|
| 2670 | } |
---|
| 2671 | else |
---|
| 2672 | { |
---|
| 2673 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 2674 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
[25061a] | 2675 | wlen_type qc=los[erg.to_reduce_u].guess_quality(c); |
---|
[4f858ce] | 2676 | if(qc<quality_a){ |
---|
| 2677 | int best=erg.to_reduce_u; |
---|
| 2678 | los[best].flatten(); |
---|
| 2679 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2680 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2681 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2682 | if(qc<quality_a){ |
---|
| 2683 | BOOLEAN exp=FALSE; |
---|
| 2684 | if(qc<=2) |
---|
| 2685 | exp=TRUE; |
---|
| 2686 | else { |
---|
| 2687 | if (qc<quality_a/2) |
---|
| 2688 | exp=TRUE; |
---|
| 2689 | else |
---|
| 2690 | if(erg.reduce_by<c->n/4) |
---|
| 2691 | exp=TRUE; |
---|
| 2692 | } |
---|
| 2693 | if (exp){ |
---|
| 2694 | poly clear_into; |
---|
| 2695 | los[erg.to_reduce_u].flatten(); |
---|
| 2696 | kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); |
---|
| 2697 | erg.expand=pCopy(clear_into); |
---|
| 2698 | kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); |
---|
| 2699 | if (TEST_OPT_PROT) |
---|
| 2700 | PrintS("e"); |
---|
| 2701 | |
---|
| 2702 | } |
---|
| 2703 | } |
---|
| 2704 | } |
---|
| 2705 | |
---|
| 2706 | |
---|
| 2707 | } |
---|
| 2708 | |
---|
| 2709 | swap_roles=FALSE; |
---|
| 2710 | return; |
---|
| 2711 | } |
---|
| 2712 | |
---|
| 2713 | } |
---|
| 2714 | else{ |
---|
| 2715 | if(erg.reduce_by>erg.to_reduce_u){ |
---|
| 2716 | //then lm(rb)>= lm(tru) so = |
---|
| 2717 | assume(erg.reduce_by==erg.to_reduce_u+1); |
---|
| 2718 | int best=erg.reduce_by; |
---|
[25061a] | 2719 | wlen_type quality_a=los[erg.reduce_by].guess_quality(c); |
---|
[4f858ce] | 2720 | int qc; |
---|
| 2721 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2722 | |
---|
| 2723 | int i; |
---|
| 2724 | if(qc<quality_a){ |
---|
| 2725 | red_object h=los[erg.reduce_by]; |
---|
| 2726 | los[erg.reduce_by]=los[best]; |
---|
| 2727 | los[best]=h; |
---|
| 2728 | } |
---|
| 2729 | swap_roles=FALSE; |
---|
| 2730 | return; |
---|
| 2731 | |
---|
| 2732 | |
---|
| 2733 | } |
---|
| 2734 | else |
---|
| 2735 | { |
---|
| 2736 | assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); |
---|
| 2737 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 2738 | //further assume, that reduce_by is the above all other polys |
---|
| 2739 | //with same leading term |
---|
| 2740 | int il=erg.reduce_by; |
---|
| 2741 | int quality_a =los[erg.reduce_by].guess_quality(c); |
---|
| 2742 | int qc; |
---|
| 2743 | while((il>0) && pLmEqual(los[il-1].p,los[il].p)){ |
---|
| 2744 | il--; |
---|
| 2745 | qc=los[il].guess_quality(c); |
---|
| 2746 | if (qc<quality_a){ |
---|
| 2747 | quality_a=qc; |
---|
| 2748 | erg.reduce_by=il; |
---|
| 2749 | } |
---|
| 2750 | } |
---|
| 2751 | swap_roles=FALSE; |
---|
| 2752 | } |
---|
| 2753 | |
---|
| 2754 | } |
---|
| 2755 | if(swap_roles) |
---|
| 2756 | { |
---|
| 2757 | if (TEST_OPT_PROT) |
---|
| 2758 | PrintS("b"); |
---|
| 2759 | poly clear_into; |
---|
| 2760 | int dummy_len; |
---|
| 2761 | int new_length; |
---|
| 2762 | int bp=erg.to_reduce_u;//bucket_positon |
---|
| 2763 | //kBucketClear(los[bp].bucket,&clear_into,&new_length); |
---|
| 2764 | new_length=los[bp].clear_to_poly(); |
---|
| 2765 | clear_into=los[bp].p; |
---|
| 2766 | poly p=c->strat->S[erg.reduce_by]; |
---|
| 2767 | int j=erg.reduce_by; |
---|
| 2768 | int old_length=c->strat->lenS[j];// in view of S |
---|
| 2769 | los[bp].p=p; |
---|
| 2770 | kBucketInit(los[bp].bucket,p,old_length); |
---|
[25061a] | 2771 | wlen_type qal=pQuality(clear_into,c,new_length); |
---|
[4f858ce] | 2772 | int pos_in_c=-1; |
---|
| 2773 | int z; |
---|
| 2774 | int new_pos; |
---|
[25061a] | 2775 | new_pos=simple_posInS(c->strat,clear_into,new_length, qal); |
---|
[4f858ce] | 2776 | assume(new_pos<=j); |
---|
| 2777 | for (z=c->n;z;z--) |
---|
| 2778 | { |
---|
| 2779 | if(p==c->S->m[z-1]) |
---|
| 2780 | { |
---|
| 2781 | pos_in_c=z-1; |
---|
| 2782 | break; |
---|
| 2783 | } |
---|
| 2784 | } |
---|
| 2785 | if(pos_in_c>=0) |
---|
| 2786 | { |
---|
| 2787 | c->S->m[pos_in_c]=clear_into; |
---|
| 2788 | c->lengths[pos_in_c]=new_length; |
---|
| 2789 | if (c->T_deg_full) |
---|
| 2790 | c->T_deg_full[pos_in_c]=pTotaldegree_full(clear_into); |
---|
| 2791 | c_S_element_changed_hook(pos_in_c,c); |
---|
| 2792 | } |
---|
| 2793 | c->strat->S[j]=clear_into; |
---|
| 2794 | c->strat->lenS[j]=new_length; |
---|
| 2795 | assume(pLength(clear_into)==new_length); |
---|
[6bcdc53] | 2796 | if(c->strat->lenSw!=NULL) |
---|
[4f858ce] | 2797 | c->strat->lenSw[j]=qal; |
---|
| 2798 | if (!rField_is_Zp(c->r)) |
---|
| 2799 | { |
---|
| 2800 | pContent(clear_into); |
---|
| 2801 | pCleardenom(clear_into);//should be unnecessary |
---|
| 2802 | } |
---|
| 2803 | else |
---|
| 2804 | pNorm(clear_into); |
---|
| 2805 | #ifdef FIND_DETERMINISTIC |
---|
| 2806 | erg.reduce_by=j; |
---|
| 2807 | //resort later see diploma thesis, find_in_S must be deterministic |
---|
| 2808 | //during multireduction if spolys are only in the span of the |
---|
| 2809 | //input polys |
---|
| 2810 | #else |
---|
| 2811 | |
---|
| 2812 | if (new_pos<j) |
---|
| 2813 | { |
---|
| 2814 | move_forward_in_S(j,new_pos,c->strat); |
---|
| 2815 | erg.reduce_by=new_pos; |
---|
| 2816 | } |
---|
| 2817 | #endif |
---|
| 2818 | } |
---|
| 2819 | } |
---|
| 2820 | static int fwbw(red_object* los, int i){ |
---|
| 2821 | int i2=i; |
---|
| 2822 | int step=1; |
---|
| 2823 | |
---|
| 2824 | BOOLEAN bw=FALSE; |
---|
| 2825 | BOOLEAN incr=TRUE; |
---|
| 2826 | |
---|
| 2827 | while(1) |
---|
| 2828 | { |
---|
| 2829 | if(!bw) |
---|
| 2830 | { |
---|
| 2831 | step=si_min(i2,step); |
---|
| 2832 | if (step==0) break; |
---|
| 2833 | i2-=step; |
---|
| 2834 | |
---|
| 2835 | if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 2836 | { |
---|
| 2837 | bw=TRUE; |
---|
| 2838 | incr=FALSE; |
---|
| 2839 | } |
---|
| 2840 | else |
---|
| 2841 | { |
---|
| 2842 | if ((!incr) &&(step==1)) break; |
---|
| 2843 | } |
---|
| 2844 | |
---|
| 2845 | |
---|
| 2846 | } |
---|
| 2847 | else |
---|
| 2848 | { |
---|
| 2849 | |
---|
| 2850 | step=si_min(i-i2,step); |
---|
| 2851 | if (step==0) break; |
---|
| 2852 | i2+=step; |
---|
| 2853 | if(pLmEqual(los[i].p,los[i2].p)){ |
---|
| 2854 | if(step==1) break; |
---|
| 2855 | else |
---|
| 2856 | { |
---|
| 2857 | bw=FALSE; |
---|
| 2858 | } |
---|
| 2859 | } |
---|
| 2860 | |
---|
| 2861 | } |
---|
| 2862 | if (incr) |
---|
| 2863 | step*=2; |
---|
| 2864 | else |
---|
| 2865 | { |
---|
| 2866 | if (step%2==1) |
---|
| 2867 | step=(step+1)/2; |
---|
| 2868 | else |
---|
| 2869 | step/=2; |
---|
| 2870 | |
---|
| 2871 | } |
---|
| 2872 | } |
---|
| 2873 | return i2; |
---|
| 2874 | } |
---|
[9cbb7a3] | 2875 | static void multi_reduction_find(red_object* los, int losl,slimgb_alg* c,int startf,find_erg & erg){ |
---|
[4f858ce] | 2876 | kStrategy strat=c->strat; |
---|
| 2877 | |
---|
| 2878 | assume(startf<=losl); |
---|
| 2879 | assume((startf==losl-1)||(pLmCmp(los[startf].p,los[startf+1].p)==-1)); |
---|
| 2880 | int i=startf; |
---|
| 2881 | |
---|
| 2882 | int j; |
---|
| 2883 | while(i>=0){ |
---|
| 2884 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0)); |
---|
| 2885 | assume(is_valid_ro(los[i])); |
---|
| 2886 | j=kFindDivisibleByInS_easy(strat,los[i]); |
---|
| 2887 | if(j>=0){ |
---|
| 2888 | |
---|
| 2889 | erg.to_reduce_u=i; |
---|
| 2890 | erg.reduce_by=j; |
---|
| 2891 | erg.fromS=TRUE; |
---|
| 2892 | int i2=fwbw(los,i); |
---|
| 2893 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 2894 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 2895 | assume(i>=i2); |
---|
| 2896 | |
---|
| 2897 | // int i2; |
---|
| 2898 | // for(i2=i-1;i2>=0;i2--){ |
---|
| 2899 | // if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 2900 | // break; |
---|
| 2901 | // } |
---|
| 2902 | |
---|
| 2903 | // erg.to_reduce_l=i2+1; |
---|
| 2904 | erg.to_reduce_l=i2; |
---|
| 2905 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2906 | return; |
---|
| 2907 | } |
---|
| 2908 | if (j<0){ |
---|
| 2909 | |
---|
| 2910 | //not reduceable, try to use this for reducing higher terms |
---|
| 2911 | int i2=fwbw(los,i); |
---|
| 2912 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 2913 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 2914 | assume(i>=i2); |
---|
| 2915 | if(i2!=i){ |
---|
| 2916 | |
---|
| 2917 | erg.to_reduce_u=i-1; |
---|
| 2918 | erg.to_reduce_l=i2; |
---|
| 2919 | erg.reduce_by=i; |
---|
| 2920 | erg.fromS=FALSE; |
---|
| 2921 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2922 | return; |
---|
| 2923 | } |
---|
[0516ab] | 2924 | if((!(c->is_homog)) &&(!(c->doubleSugar))) |
---|
[4f858ce] | 2925 | { |
---|
| 2926 | |
---|
| 2927 | for (i2=i+1;i2<losl;i2++){ |
---|
| 2928 | if (p_LmShortDivisibleBy(los[i].p,los[i].sev,los[i2].p,~los[i2].sev, |
---|
| 2929 | c->r)){ |
---|
| 2930 | int i3=i2; |
---|
| 2931 | while((i3+1<losl) && (pLmEqual(los[i2].p, los[i3+1].p))) |
---|
| 2932 | i3++; |
---|
| 2933 | erg.to_reduce_u=i3; |
---|
| 2934 | erg.to_reduce_l=i2; |
---|
| 2935 | erg.reduce_by=i; |
---|
| 2936 | erg.fromS=FALSE; |
---|
| 2937 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2938 | return; |
---|
| 2939 | } |
---|
| 2940 | // else {assume(!p_LmDivisibleBy(los[i].p, los[i2].p,c->r));} |
---|
| 2941 | } |
---|
| 2942 | } |
---|
| 2943 | i--; |
---|
| 2944 | } |
---|
| 2945 | } |
---|
| 2946 | erg.reduce_by=-1;//error code |
---|
| 2947 | return; |
---|
| 2948 | } |
---|
| 2949 | |
---|
| 2950 | // nicht reduzierbare eintraege in ergebnisliste schreiben |
---|
| 2951 | // nullen loeschen |
---|
| 2952 | // while(finde_groessten leitterm reduzierbar(c,erg)){ |
---|
| 2953 | |
---|
| 2954 | static int multi_reduction_clear_zeroes(red_object* los, int losl, int l, int u) |
---|
| 2955 | { |
---|
| 2956 | |
---|
| 2957 | |
---|
| 2958 | int deleted=0; |
---|
| 2959 | int i=l; |
---|
| 2960 | int last=-1; |
---|
| 2961 | while(i<=u) |
---|
| 2962 | { |
---|
| 2963 | |
---|
| 2964 | if(los[i].p==NULL){ |
---|
| 2965 | kBucketDestroy(&los[i].bucket); |
---|
| 2966 | // delete los[i];//here we assume los are constructed with new |
---|
| 2967 | //destroy resources, must be added here |
---|
| 2968 | if (last>=0) |
---|
| 2969 | { |
---|
| 2970 | memmove(los+(int)(last+1-deleted),los+(last+1),sizeof(red_object)*(i-1-last)); |
---|
| 2971 | } |
---|
| 2972 | last=i; |
---|
| 2973 | deleted++; |
---|
| 2974 | } |
---|
| 2975 | i++; |
---|
| 2976 | } |
---|
| 2977 | if((last>=0)&&(last!=losl-1)) |
---|
| 2978 | memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last)); |
---|
| 2979 | return deleted; |
---|
| 2980 | |
---|
| 2981 | } |
---|
| 2982 | |
---|
[9cbb7a3] | 2983 | static void sort_region_down(red_object* los, int l, int u, slimgb_alg* c) |
---|
[4f858ce] | 2984 | { |
---|
| 2985 | qsort(los+l,u-l+1,sizeof(red_object),red_object_better_gen); |
---|
| 2986 | int i; |
---|
| 2987 | |
---|
| 2988 | for(i=l;i<=u;i++) |
---|
| 2989 | { |
---|
| 2990 | BOOLEAN moved=FALSE; |
---|
| 2991 | int j; |
---|
| 2992 | for(j=i;j;j--) |
---|
| 2993 | { |
---|
| 2994 | if(pLmCmp(los[j].p,los[j-1].p)==-1){ |
---|
| 2995 | red_object h=los[j]; |
---|
| 2996 | los[j]=los[j-1]; |
---|
| 2997 | los[j-1]=h; |
---|
| 2998 | moved=TRUE; |
---|
| 2999 | } |
---|
| 3000 | else break; |
---|
| 3001 | } |
---|
| 3002 | if(!moved) return; |
---|
| 3003 | } |
---|
| 3004 | } |
---|
| 3005 | |
---|
| 3006 | //assume that los is ordered ascending by leading term, all non zero |
---|
[9cbb7a3] | 3007 | static void multi_reduction(red_object* los, int & losl, slimgb_alg* c) |
---|
[4f858ce] | 3008 | { |
---|
| 3009 | |
---|
| 3010 | //initialize; |
---|
| 3011 | assume(c->strat->sl>=0); |
---|
| 3012 | assume(losl>0); |
---|
| 3013 | int i; |
---|
| 3014 | for(i=0;i<losl;i++){ |
---|
| 3015 | los[i].sev=pGetShortExpVector(los[i].p); |
---|
| 3016 | //SetShortExpVector(); |
---|
| 3017 | los[i].p=kBucketGetLm(los[i].bucket); |
---|
| 3018 | } |
---|
| 3019 | |
---|
| 3020 | kStrategy strat=c->strat; |
---|
| 3021 | int curr_pos=losl-1; |
---|
| 3022 | |
---|
| 3023 | |
---|
| 3024 | // nicht reduzierbare einträge in ergebnisliste schreiben |
---|
| 3025 | // nullen loeschen |
---|
| 3026 | while(curr_pos>=0){ |
---|
| 3027 | |
---|
| 3028 | find_erg erg; |
---|
| 3029 | multi_reduction_find(los, losl,c,curr_pos,erg);//last argument should be curr_pos |
---|
| 3030 | // PrintS("\n erg:\n"); |
---|
| 3031 | // Print("upper:%i\n",erg.to_reduce_u); |
---|
| 3032 | // Print("lower:%i\n",erg.to_reduce_l); |
---|
| 3033 | // Print("reduce_by:%i\n",erg.reduce_by); |
---|
| 3034 | // Print("fromS:%i\n",erg.fromS); |
---|
| 3035 | if(erg.reduce_by<0) break; |
---|
| 3036 | |
---|
| 3037 | |
---|
| 3038 | |
---|
| 3039 | erg.expand=NULL; |
---|
| 3040 | int d=erg.to_reduce_u-erg.to_reduce_l+1; |
---|
| 3041 | //if ((!erg.fromS)&&(d>100)){ |
---|
[196cdf] | 3042 | |
---|
[4f858ce] | 3043 | multi_reduction_lls_trick(los,losl,c,erg); |
---|
| 3044 | int sum=0; |
---|
| 3045 | |
---|
| 3046 | |
---|
| 3047 | int i; |
---|
| 3048 | int len; |
---|
| 3049 | // wrp(los[erg.to_reduce_u].p); |
---|
| 3050 | //Print("\n"); |
---|
| 3051 | multi_reduce_step(erg,los,c); |
---|
[196cdf] | 3052 | |
---|
[4f858ce] | 3053 | // reduction_step *rs=create_reduction_step(erg, los, c); |
---|
| 3054 | // rs->reduce(los,erg.to_reduce_l,erg.to_reduce_u); |
---|
| 3055 | // finalize_reduction_step(rs); |
---|
| 3056 | |
---|
| 3057 | int deleted=multi_reduction_clear_zeroes(los, losl, erg.to_reduce_l, erg.to_reduce_u); |
---|
| 3058 | if(erg.fromS==FALSE) |
---|
| 3059 | curr_pos=si_max(erg.to_reduce_u,erg.reduce_by); |
---|
| 3060 | else |
---|
| 3061 | curr_pos=erg.to_reduce_u; |
---|
| 3062 | losl -= deleted; |
---|
| 3063 | curr_pos -= deleted; |
---|
| 3064 | |
---|
| 3065 | //Print("deleted %i \n",deleted); |
---|
| 3066 | sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c); |
---|
| 3067 | // sort_region_down(los, 0, losl-1, c); |
---|
| 3068 | // qsort(los,losl,sizeof(red_object),red_object_better_gen); |
---|
| 3069 | if(erg.expand) |
---|
| 3070 | { |
---|
| 3071 | #ifdef FIND_DETERMINISTIC |
---|
| 3072 | int i; |
---|
| 3073 | for(i=0;c->expandS[i];i++); |
---|
[ec8a6b6] | 3074 | c->expandS=(poly*) omrealloc(c->expandS,(i+2)*sizeof(poly)); |
---|
[4f858ce] | 3075 | c->expandS[i]=erg.expand; |
---|
| 3076 | c->expandS[i+1]=NULL; |
---|
| 3077 | #else |
---|
| 3078 | add_to_reductors(c,erg.expand,erg.expand_length); |
---|
| 3079 | #endif |
---|
| 3080 | } |
---|
| 3081 | |
---|
| 3082 | } |
---|
| 3083 | return; |
---|
| 3084 | } |
---|
| 3085 | void red_object::flatten(){ |
---|
| 3086 | assume(p==kBucketGetLm(bucket)); |
---|
| 3087 | } |
---|
| 3088 | void red_object::validate(){ |
---|
[bddc9d] | 3089 | p=kBucketGetLm(bucket); |
---|
| 3090 | if(p) |
---|
[4f858ce] | 3091 | sev=pGetShortExpVector(p); |
---|
| 3092 | } |
---|
| 3093 | int red_object::clear_to_poly(){ |
---|
| 3094 | flatten(); |
---|
| 3095 | int l; |
---|
| 3096 | kBucketClear(bucket,&p,&l); |
---|
| 3097 | return l; |
---|
| 3098 | } |
---|
| 3099 | |
---|
| 3100 | |
---|
| 3101 | |
---|
| 3102 | |
---|
| 3103 | |
---|
| 3104 | void reduction_step::reduce(red_object* r, int l, int u){} |
---|
| 3105 | void simple_reducer::target_is_no_sum_reduce(red_object & ro){ |
---|
[d491e3] | 3106 | number coef; |
---|
| 3107 | if (!c->nc) |
---|
| 3108 | coef=kBucketPolyRed(ro.bucket,p, |
---|
| 3109 | p_len, |
---|
| 3110 | c->strat->kNoether); |
---|
| 3111 | else |
---|
| 3112 | nc_kBucketPolyRed_Z(ro.bucket, p, &coef); |
---|
| 3113 | nDelete(&coef); |
---|
[4f858ce] | 3114 | } |
---|
| 3115 | |
---|
[bddc9d] | 3116 | |
---|
[4f858ce] | 3117 | void simple_reducer::reduce(red_object* r, int l, int u){ |
---|
| 3118 | this->pre_reduce(r,l,u); |
---|
| 3119 | int i; |
---|
| 3120 | //debug start |
---|
| 3121 | int im; |
---|
| 3122 | // for(im=l;im<=u;im++) |
---|
| 3123 | // assume(is_valid_ro(r[im])); |
---|
| 3124 | |
---|
| 3125 | |
---|
| 3126 | //debug end |
---|
| 3127 | |
---|
| 3128 | for(i=l;i<=u;i++){ |
---|
| 3129 | |
---|
| 3130 | |
---|
| 3131 | |
---|
[bddc9d] | 3132 | this->target_is_no_sum_reduce(r[i]); |
---|
[4f858ce] | 3133 | |
---|
| 3134 | } |
---|
| 3135 | for(i=l;i<=u;i++){ |
---|
| 3136 | r[i].validate(); |
---|
| 3137 | #ifdef TGB_DEBUG |
---|
| 3138 | #endif |
---|
[bddc9d] | 3139 | } |
---|
[4f858ce] | 3140 | } |
---|
| 3141 | reduction_step::~reduction_step(){} |
---|
| 3142 | simple_reducer::~simple_reducer(){ |
---|
| 3143 | if(fill_back!=NULL) |
---|
| 3144 | { |
---|
| 3145 | kBucketInit(fill_back,p,p_len); |
---|
| 3146 | } |
---|
| 3147 | fill_back=NULL; |
---|
| 3148 | |
---|
| 3149 | } |
---|
[36b1aa] | 3150 | |
---|
[9cbb7a3] | 3151 | void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c){ |
---|
[4f858ce] | 3152 | static int id=0; |
---|
| 3153 | id++; |
---|
| 3154 | |
---|
| 3155 | int rn=erg.reduce_by; |
---|
| 3156 | poly red; |
---|
| 3157 | int red_len; |
---|
| 3158 | simple_reducer* pointer; |
---|
[27e091b] | 3159 | BOOLEAN work_on_copy=FALSE; |
---|
[4f858ce] | 3160 | if(erg.fromS){ |
---|
| 3161 | red=c->strat->S[rn]; |
---|
| 3162 | red_len=c->strat->lenS[rn]; |
---|
| 3163 | assume(red_len==pLength(red)); |
---|
| 3164 | } |
---|
| 3165 | else |
---|
| 3166 | { |
---|
| 3167 | r[rn].flatten(); |
---|
| 3168 | kBucketClear(r[rn].bucket,&red,&red_len); |
---|
| 3169 | if (!rField_is_Zp(c->r)) |
---|
| 3170 | { |
---|
| 3171 | pContent(red); |
---|
| 3172 | pCleardenom(red);//should be unnecessary |
---|
| 3173 | |
---|
| 3174 | } |
---|
| 3175 | pNormalize(red); |
---|
| 3176 | red_len=pLength(red); |
---|
| 3177 | } |
---|
[56a6cc] | 3178 | if ((c->nc)||(erg.to_reduce_u-erg.to_reduce_l>5)){ |
---|
[27e091b] | 3179 | work_on_copy=TRUE; |
---|
[4f858ce] | 3180 | // poly m=pOne(); |
---|
| 3181 | poly m=c->tmp_lm; |
---|
| 3182 | pSetCoeff(m,nInit(1)); |
---|
| 3183 | for(int i=1;i<=pVariables;i++) |
---|
| 3184 | pSetExp(m,i,(pGetExp(r[erg.to_reduce_l].p, i)-pGetExp(red,i))); |
---|
| 3185 | pSetm(m); |
---|
[d491e3] | 3186 | poly red_cp; |
---|
| 3187 | if (!c->nc) |
---|
| 3188 | red_cp=ppMult_mm(red,m); |
---|
| 3189 | else |
---|
| 3190 | red_cp=nc_mm_Mult_p(m, pCopy(red), c->r); |
---|
[4f858ce] | 3191 | if(!erg.fromS){ |
---|
| 3192 | kBucketInit(r[rn].bucket,red,red_len); |
---|
| 3193 | } |
---|
| 3194 | //now reduce the copy |
---|
[9cbb7a3] | 3195 | //static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) |
---|
[d491e3] | 3196 | if (!c->nc) |
---|
| 3197 | redTailShort(red_cp,c->strat); |
---|
[4f858ce] | 3198 | //number mul; |
---|
| 3199 | // red_len--; |
---|
| 3200 | // red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length); |
---|
| 3201 | // pSetCoeff(red_cp,nMult(red_cp->coef,mul)); |
---|
| 3202 | // nDelete(&mul); |
---|
| 3203 | // red_len++; |
---|
| 3204 | red=red_cp; |
---|
| 3205 | red_len=pLength(red); |
---|
| 3206 | // pDelete(&m); |
---|
| 3207 | |
---|
| 3208 | } |
---|
| 3209 | int i; |
---|
| 3210 | |
---|
| 3211 | |
---|
[27e091b] | 3212 | |
---|
[4f858ce] | 3213 | assume(red_len==pLength(red)); |
---|
[36b1aa] | 3214 | |
---|
| 3215 | pointer=new simple_reducer(red,red_len,c); |
---|
[4f858ce] | 3216 | |
---|
[27e091b] | 3217 | if ((!work_on_copy) && (!erg.fromS)) |
---|
[4f858ce] | 3218 | pointer->fill_back=r[rn].bucket; |
---|
| 3219 | else |
---|
| 3220 | pointer->fill_back=NULL; |
---|
| 3221 | pointer->reduction_id=id; |
---|
| 3222 | pointer->c=c; |
---|
| 3223 | |
---|
| 3224 | pointer->reduce(r,erg.to_reduce_l, erg.to_reduce_u); |
---|
[27e091b] | 3225 | if(work_on_copy) pDelete(&pointer->p); |
---|
[4f858ce] | 3226 | delete pointer; |
---|
| 3227 | |
---|
| 3228 | }; |
---|
| 3229 | |
---|
| 3230 | |
---|
| 3231 | |
---|
[bddc9d] | 3232 | |
---|
[4f858ce] | 3233 | void simple_reducer:: pre_reduce(red_object* r, int l, int u){} |
---|
[36b1aa] | 3234 | |
---|