1 // binomial.cc
2
3 // implementation of class binomial
4
5 #ifndef BINOMIAL_CC
6 #define BINOMIAL_CC
7
8 #include <climits>
9 #include "binomial__term_ordering.h"
10
11 ///////////////////////// constructors and destructor //////////////////////
12
13 // For a better overview, the constructor code is separated for
14 // NO_SUPPORT_DRIVEN_METHODS and SUPPORT_DRIVEN_METHODS.
15
16 #ifdef NO_SUPPORT_DRIVEN_METHODS
17
binomial(const short & number_of_variables)18 binomial::binomial(const short& number_of_variables)
19 :_number_of_variables(number_of_variables)
20 {
21 exponent_vector=new Integer[_number_of_variables];
22 }
23
24
25
26
binomial(const short & number_of_variables,const Integer * exponents)27 binomial::binomial(const short& number_of_variables,const Integer* exponents)
28 :_number_of_variables(number_of_variables)
29 {
30
31 // range check for rarely used constructors
32 if(_number_of_variables<=0)
33 {
34 cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
35 "argument out of range"<<endl;
36 exponent_vector=NULL;
37 // to avoid problems when deleting
38 return;
39 }
40
41 // initialization
42 exponent_vector=new Integer[_number_of_variables];
43 for(short i=0;i<_number_of_variables;i++)
44 exponent_vector[i]=exponents[i];
45 }
46
47
48
49
binomial(const short & number_of_variables,const Integer * exponents,const term_ordering & w)50 binomial::binomial(const short& number_of_variables,const Integer* exponents,
51 const term_ordering& w)
52 :_number_of_variables(number_of_variables)
53 {
54
55 // range check for rarely used constructors
56 if(_number_of_variables<=0)
57 {
58 cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
59 "argument out of range"<<endl;
60 exponent_vector=NULL;
61 // to avoid problems when deleting
62 return;
63 }
64
65 exponent_vector=new Integer[_number_of_variables];
66
67 // determine head and tail
68 if(w.compare_to_zero(exponents)>=0)
69 for(short i=0;i<_number_of_variables;i++)
70 exponent_vector[i]=exponents[i];
71 else
72 for(short i=0;i<_number_of_variables;i++)
73 exponent_vector[i]=-exponents[i];
74
75 }
76
77
78
79
binomial(const binomial & b)80 binomial::binomial(const binomial& b)
81 :_number_of_variables(b._number_of_variables)
82 {
83 exponent_vector=new Integer[_number_of_variables];
84 for(short i=0;i<_number_of_variables;i++)
85 exponent_vector[i]=b.exponent_vector[i];
86 }
87
88
89
90
91 #endif // NO_SUPPORT_DRIVEN_METHODS
92
93
94
95
96 #ifdef SUPPORT_DRIVEN_METHODS
97
98
99
100
binomial(const short & number_of_variables)101 binomial::binomial(const short& number_of_variables)
102 :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
103 {
104 exponent_vector=new Integer[_number_of_variables];
105 }
106
107
108
109
binomial(const short & number_of_variables,const Integer * exponents)110 binomial::binomial(const short& number_of_variables, const Integer* exponents)
111 :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
112 {
113
114 // range check for rarely used constructors
115 if(_number_of_variables<=0)
116 {
117 exponent_vector=NULL;
118 // to avoid problems when deleting
119 cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
120 "argument out of range"<<endl;
121 return;
122 }
123
124 exponent_vector=new Integer[_number_of_variables];
125
126 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
127 // number of bits of a long int
128
129
130 for(short i=0;i<_number_of_variables;i++)
131 {
132
133 #ifdef SUPPORT_VARIABLES_FIRST
134
135 Integer actual_entry=exponents[i];
136 exponent_vector[i]=actual_entry;
137
138 #endif // SUPPORT_VARIABLES_FIRST
139
140 #ifdef SUPPORT_VARIABLES_LAST
141
142 short j=_number_of_variables-1-i;
143 Integer actual_entry=exponents[j];
144 exponent_vector[j]=actual_entry;
145
146 #endif // SUPPORT_VARIABLES_LAST
147
148 if(i<size_of_support_vectors)
149 {
150 // variable i is considered in the support vectors
151 if(actual_entry>0)
152 head_support|=(1<<i);
153 // bit i of head_support is set to 1 (counting from 0)
154 else if(actual_entry<0)
155 tail_support|=(1<<i);
156 // bit i of tail_support is set to 1
157 }
158 }
159
160 }
161
162
163
164
binomial(const short & number_of_variables,const Integer * exponents,const term_ordering & w)165 binomial::binomial(const short& number_of_variables, const Integer* exponents,
166 const term_ordering& w)
167 :_number_of_variables(number_of_variables),head_support(0),tail_support(0)
168 {
169 // range check for rarely used constructors
170 if(_number_of_variables<=0)
171 {
172 cerr<<"\nWARNING: binomial::binomial(const short&, const Integer*):\n"
173 "argument out of range"<<endl;
174 exponent_vector=NULL;
175 // to avoid problems when deleting
176 return;
177 }
178
179
180 exponent_vector=new Integer[_number_of_variables];
181
182 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
183 // number of bits of a long int
184
185 // determine head and tail
186 short sign;
187 if(w.compare_to_zero(exponents)>=0)
188 sign=1;
189 else
190 sign=-1;
191
192
193 for(short i=0;i<_number_of_variables;i++)
194 {
195
196 #ifdef SUPPORT_VARIABLES_FIRST
197
198 Integer actual_entry=sign*exponents[i];
199 exponent_vector[i]=actual_entry;
200
201 #endif // SUPPORT_VARIABLES_FIRST
202
203 #ifdef SUPPORT_VARIABLES_LAST
204
205 short j=_number_of_variables-1-i;
206 Integer actual_entry=sign*exponents[j];
207 exponent_vector[j]=actual_entry;
208
209 #endif // SUPPORT_VARIABLES_LAST
210
211 if(i<size_of_support_vectors)
212 {
213 // variable i is considered in the support vectors
214 if(actual_entry>0)
215 head_support|=(1<<i);
216 // bit i of head_support is set to 1 (counting from 0)
217 else if(actual_entry<0)
218 tail_support|=(1<<i);
219 // bit i of tail_support is set to 1
220 }
221 }
222
223 }
224
225
226
227
binomial(const binomial & b)228 binomial::binomial(const binomial& b)
229 :_number_of_variables(b._number_of_variables),
230 head_support(b.head_support),tail_support(b.tail_support)
231 {
232 exponent_vector=new Integer[_number_of_variables];
233 for(short i=0;i<_number_of_variables;i++)
234 exponent_vector[i]=b.exponent_vector[i];
235 }
236
237
238
239
240 #endif // SUPPORT_DRIVEN_METHODS
241
242
243
244
~binomial()245 binomial::~binomial()
246 {
247 delete[] exponent_vector;
248 }
249
250
251
252
253 /////////////////// object information /////////////////////////////////////
254
255
256
257
number_of_variables() const258 short binomial::number_of_variables() const
259 {
260 return _number_of_variables;
261 }
262
263
264
265
error_status() const266 short binomial::error_status() const
267 {
268 if(_number_of_variables<0)
269 return _number_of_variables;
270 return 0;
271 }
272
273
274
275
276 //////////////////// assignment and access operators ////////////////////////
277
278
279
280
operator =(const binomial & b)281 binomial& binomial::operator=(const binomial& b)
282 {
283
284 if(&b==this)
285 return *this;
286
287
288 #ifdef SUPPORT_DRIVEN_METHODS
289
290 head_support=b.head_support;
291 tail_support=b.tail_support;
292
293 #endif // SUPPORT_DRIVEN_METHODS
294
295 if(_number_of_variables!=b._number_of_variables)
296 {
297 delete[] exponent_vector;
298 _number_of_variables=b._number_of_variables;
299
300 if(_number_of_variables<=0)
301 {
302 cerr<<"\nWARNING: binomial& binomial::operator=(const binomial&):\n"
303 "assignment from corrupt binomial"<<endl;
304 exponent_vector=NULL;
305 return (*this);
306 }
307
308 exponent_vector=new Integer[_number_of_variables];
309 }
310
311 for(short i=0;i<_number_of_variables;i++)
312 exponent_vector[i]=b.exponent_vector[i];
313
314 return(*this);
315 }
316
317
318
319
operator [](const short & i) const320 Integer binomial::operator[](const short& i) const
321 {
322 return exponent_vector[i];
323 }
324
325
326
327
328 //////////////////// comparison operators ///////////////////////////////////
329
330
331
332
operator ==(const binomial & b) const333 BOOLEAN binomial::operator==(const binomial& b) const
334 {
335 if(this == &b)
336 return(TRUE);
337
338 #ifdef SUPPORT_DRIVEN_METHODS
339
340 if(head_support!=b.head_support)
341 return(FALSE);
342 if(tail_support!=b.tail_support)
343 return(FALSE);
344
345 #endif // SUPPORT_DRIVEN_METHODS
346
347 for(short i=0;i<_number_of_variables;i++)
348 if(exponent_vector[i]!=b.exponent_vector[i])
349 return(FALSE);
350 return(TRUE);
351 }
352
353
354
355
operator !=(const binomial & b) const356 BOOLEAN binomial::operator!=(const binomial& b) const
357 {
358 if(this == &b)
359 return(FALSE);
360
361 #ifdef SUPPORT_DRIVEN_METHODS
362
363 if(head_support!=b.head_support)
364 return(TRUE);
365 if(tail_support!=b.tail_support)
366 return(TRUE);
367
368 #endif // SUPPORT_DRIVEN_METHODS
369
370 for(short i=0;i<_number_of_variables;i++)
371 if(exponent_vector[i]!=b.exponent_vector[i])
372 return(TRUE);
373 return(FALSE);
374 }
375
376
377
378
379 // operators for efficient comparisons with the zero binomial (comp_value=0)
380
operator ==(const Integer comp_value) const381 BOOLEAN binomial::operator==(const Integer comp_value) const
382 {
383
384 #ifdef SUPPORT_DRIVEN_METHODS
385
386 if(comp_value==0)
387 {
388 if(head_support!=0)
389 return(FALSE);
390 if(tail_support!=0)
391 return(FALSE);
392 }
393
394 #endif // SUPPORT_DRIVEN_METHODS
395
396 for(short i=0;i<_number_of_variables;i++)
397 if(exponent_vector[i]!=comp_value)
398 return(FALSE);
399 return(TRUE);
400 }
401
402
403
404
operator !=(const Integer comp_value) const405 BOOLEAN binomial::operator!=(const Integer comp_value) const
406 {
407
408 #ifdef SUPPORT_DRIVEN_METHODS
409
410 if(comp_value==0)
411 {
412 if(head_support!=0)
413 return(TRUE);
414 if(tail_support!=0)
415 return(TRUE);
416 }
417
418 #endif // SUPPORT_DRIVEN_METHODS
419
420 for(short i=0;i<_number_of_variables;i++)
421 if(exponent_vector[i]!=comp_value)
422 return(TRUE);
423 return(FALSE);
424 }
425
426
427
428
operator <=(const Integer comp_value) const429 BOOLEAN binomial::operator<=(const Integer comp_value) const
430 {
431
432 #ifdef SUPPORT_DRIVEN_METHODS
433
434 if(comp_value==0)
435 if(head_support!=0)
436 return(FALSE);
437
438 #endif // SUPPORT_DRIVEN_METHODS
439
440 for(short i=0;i<_number_of_variables;i++)
441 if(exponent_vector[i]>comp_value)
442 return(FALSE);
443 return(TRUE);
444 }
445
446
447
448
operator >=(const Integer comp_value) const449 BOOLEAN binomial::operator>=(const Integer comp_value) const
450 {
451
452 #ifdef SUPPORT_DRIVEN_METHODS
453
454 if(comp_value==0)
455 if(tail_support!=0)
456 return(FALSE);
457
458 #endif
459
460 for(short i=0;i<_number_of_variables;i++)
461 if(exponent_vector[i]<comp_value)
462 return(FALSE);
463 return(TRUE);
464 }
465
466
467
468
469 ////////////// basic routines for Buchbergers's algorithm //////////////////
470
471
472
473
head_reductions_by(const binomial & b) const474 Integer binomial::head_reductions_by(const binomial& b) const
475 // Returns the number of possible reductions of the actual binomial�s head
476 // by the binomial b. This is the minimum of the quotients
477 // exponent_vector[i]/b.exponent_vector[i]
478 // where exponent_vector[i]>0 and b.exponent_vector[i]>0
479 // (0 if there are no such quotients).
480 // A negative return value means b=0 or head(b)=1.
481 {
482
483
484 #ifdef NO_SUPPORT_DRIVEN_METHODS
485
486 Integer result=-1;
487 Integer new_result=-1;
488 // -1 stands for infinitely many reductions
489
490 for(short i=0;i<_number_of_variables;i++)
491 // explicit sign tests for all components
492 {
493 Integer actual_b_component=b.exponent_vector[i];
494
495 if(actual_b_component>0)
496 // else variable i is not involved in the head of b
497 {
498 Integer actual_component=exponent_vector[i];
499
500 if(actual_component<actual_b_component)
501 return 0;
502
503 new_result=(Integer) (actual_component/actual_b_component);
504
505 // new_result>=1
506 if((new_result<result) || (result==-1))
507 // new (or first) minimum
508 result=new_result;
509 }
510 }
511
512 #endif // NO_SUPPORT_DRIVEN_METHODS
513
514
515 #ifdef SUPPORT_DRIVEN_METHODS
516
517 if((head_support&b.head_support)!=b.head_support)
518 // head support of b not contained in head support, no reduction possible
519 return 0;
520
521
522 Integer result=-1;
523 Integer new_result=-1;
524 // -1 stands for infinitely many reductions
525
526
527 short size_of_support_vectors=CHAR_BIT*sizeof(long);
528 // number of bits of a long int
529 if(size_of_support_vectors>_number_of_variables)
530 size_of_support_vectors=_number_of_variables;
531 // number of components of the support vectors
532
533
534 #ifdef SUPPORT_VARIABLES_FIRST
535
536 for(short i=0;i<size_of_support_vectors;i++)
537 // test support variables
538
539 if(b.head_support&(1<<i))
540 // bit i of b.head_support is 1
541 {
542 new_result=(Integer) (exponent_vector[i]/b.exponent_vector[i]);
543 // remember that exponent_vector[i]>0 !
544 // (head support contains that of b)
545
546 if(new_result==0)
547 // exponent_vector[i]<b.exponent_vector[i]
548 return 0;
549
550 // new_result>=1
551 if((new_result<result) || (result==-1))
552 // new (or first) minimum
553 result=new_result;
554 }
555
556
557 for(short i=size_of_support_vectors;i<_number_of_variables;i++)
558 // test non-support variables
559 // from now on we need explicit sign tests
560 {
561 Integer actual_b_component=b.exponent_vector[i];
562
563 if(actual_b_component>0)
564 // else variable i is not involved in the head of b
565 {
566 Integer actual_component=exponent_vector[i];
567
568 if(actual_component<actual_b_component)
569 return 0;
570
571 new_result=(Integer) (actual_component/actual_b_component);
572
573 // new_result>=1
574 if((new_result<result) || (result==-1))
575 // new (or first) minimum
576 result=new_result;
577 }
578 }
579
580 #endif // SUPPORT_VARIABLES_FIRST
581
582
583 #ifdef SUPPORT_VARIABLES_LAST
584
585 for(short i=0;i<size_of_support_vectors;i++)
586 // test support variables
587
588 if(b.head_support&(1<<i))
589 // bit i of b.head_support is 1
590 {
591 short j=_number_of_variables-1-i;
592 new_result=(Integer) (exponent_vector[j]/ b.exponent_vector[j]);
593 // remember that exponent_vector[_number_of_variables-1-i]>0 !
594 // (head support contains that of b)
595
596 if(new_result==0)
597 // exponent_vector[_number_of_variables-1-i]
598 // <b.exponent_vector[_number_of_variables-1-i]
599 return 0;
600
601 // new_result>=1
602 if((new_result<result) || (result==-1))
603 // new (or first) minimum
604 result=new_result;
605 }
606
607
608 for(short i=size_of_support_vectors;i<_number_of_variables;i++)
609 // test non-support variables
610 // from now on we need explicit sign tests
611 {
612 short j=_number_of_variables-1-i;
613 Integer actual_b_component=b.exponent_vector[j];
614
615 if(actual_b_component>0)
616 // else variable number_of_variables-1-i is not involved in the head of b
617 {
618 Integer actual_component=exponent_vector[j];
619
620 if(actual_component<actual_b_component)
621 return 0;
622
623 new_result=(Integer) (actual_component/actual_b_component);
624
625 // new_result>=1
626 if((new_result<result) || (result==-1))
627 // new (or first) minimum
628 result=new_result;
629 }
630 }
631
632 #endif // SUPPORT_VARIABLES_LAST
633
634
635 #endif // SUPPORT_DRIVEN_METHODS
636
637
638 return(result);
639 }
640
641
642
643
tail_reductions_by(const binomial & b) const644 Integer binomial::tail_reductions_by(const binomial& b) const
645 // Returns the number of possible reductions of the actual binomial�s tail
646 // by the binomial b. This is the minimum of the quotients
647 // - exponent_vector[i]/b.exponent_vector[i]
648 // where exponent_vector[i]<0 and b.exponent_vector[i]>0
649 // (0 if there are no such quotients).
650 // A negative return value means b=0 or head(b)=1.
651 {
652
653
654 #ifdef NO_SUPPORT_DRIVEN_METHODS
655
656 Integer result=-1;
657 Integer new_result=-1;
658 // -1 stands for infinitely many reductions
659
660 for(short i=0;i<_number_of_variables;i++)
661 // explicit sign tests for all components
662 {
663 Integer actual_b_component=b.exponent_vector[i];
664
665 if(actual_b_component>0)
666 // else variable i is not involved in the head of b
667 {
668 Integer actual_component=-exponent_vector[i];
669
670 if(actual_component<actual_b_component)
671 return 0;
672
673 new_result=(Integer) (actual_component/actual_b_component);
674
675 // new_result>=1
676 if((new_result<result) || (result==-1))
677 // new (or first) minimum
678 result=new_result;
679 }
680 }
681
682 #endif // NO_SUPPORT_DRIVEN_METHODS
683
684
685 #ifdef SUPPORT_DRIVEN_METHODS
686
687 if((tail_support&b.head_support)!=b.head_support)
688 // head support of b not contained in tail support, no reduction possible
689 return 0;
690
691
692 Integer result=-1;
693 Integer new_result=-1;
694 // -1 stands for infinitely many reductions
695
696
697 short size_of_support_vectors=CHAR_BIT*sizeof(long);
698 // number of bits of a long int
699 if(size_of_support_vectors>_number_of_variables)
700 size_of_support_vectors=_number_of_variables;
701 // number of components of the support vectors
702
703
704 #ifdef SUPPORT_VARIABLES_FIRST
705
706 for(short i=0;i<size_of_support_vectors;i++)
707 // test support variables
708
709 if(b.head_support&(1<<i))
710 // bit i of b.head_support is 1
711 {
712 new_result=(Integer) (-exponent_vector[i]/b.exponent_vector[i]);
713 // remember that exponent_vector[i]<0 !
714 // (tail support contains the head support of b)
715
716 if(new_result==0)
717 // -exponent_vector[i]<b.exponent_vector[i]
718 return 0;
719
720 // new_result>=1
721 if((new_result<result) || (result==-1))
722 // new (or first) minimum
723 result=new_result;
724 }
725
726
727 for(short i=size_of_support_vectors;i<_number_of_variables;i++)
728 // test non-support variables
729 // from now on we need explicit sign tests
730 {
731 Integer actual_b_component=b.exponent_vector[i];
732
733 if(actual_b_component>0)
734 // else variable i is not involved in the head of b
735 {
736 Integer actual_component=-exponent_vector[i];
737
738 if(actual_component<actual_b_component)
739 return 0;
740
741 new_result=(Integer) (actual_component/actual_b_component);
742
743 // new_result>=1
744 if((new_result<result) || (result==-1))
745 // new (or first) minimum
746 result=new_result;
747 }
748 }
749
750 #endif // SUPPORT_VARIABLES_FIRST
751
752
753 #ifdef SUPPORT_VARIABLES_LAST
754
755 for(short i=0;i<size_of_support_vectors;i++)
756 // test support variables
757
758 if(b.head_support&(1<<i))
759 // bit i of b.head_support is 1
760 {
761 short j=_number_of_variables-1-i;
762 new_result=(Integer) (-exponent_vector[j] / b.exponent_vector[j]);
763 // remember that exponent_vector[_number_of_variables-1-i]<0 !
764 // (tail support contains the head support of b)
765
766 if(new_result==0)
767 // -exponent_vector[_number_of_variables-1-i]
768 // <b.exponent_vector[_number_of_variables-1-i]
769 return 0;
770
771 // new_result>=1
772 if((new_result<result) || (result==-1))
773 // new (or first) minimum
774 result=new_result;
775 }
776
777
778 for(short i=size_of_support_vectors;i<_number_of_variables;i++)
779 // test non-support variables
780 // from now on we need explicit sign tests
781 {
782 short j=_number_of_variables-1-i;
783 Integer actual_b_component=b.exponent_vector[j];
784
785 if(actual_b_component>0)
786 // else variable number_of_variables-1-i is not involved in the head of b
787 {
788 Integer actual_component=-exponent_vector[j];
789
790 if(actual_component<actual_b_component)
791 return 0;
792
793 new_result=(Integer) (actual_component/actual_b_component);
794
795 // new_result>=1
796 if((new_result<result) || (result==-1))
797 // new (or first) minimum
798 result=new_result;
799 }
800 }
801
802 #endif // SUPPORT_VARIABLES_LAST
803
804
805 #endif // SUPPORT_DRIVEN_METHODS
806
807
808 return(result);
809 }
810
811
812
813
reduce_head_by(const binomial & b,const term_ordering & w)814 int binomial::reduce_head_by(const binomial& b, const term_ordering& w)
815 {
816 Integer reduction_number=head_reductions_by(b);
817 if(reduction_number<=0)
818 return 0;
819
820 for(short i=0;i<_number_of_variables;i++)
821 exponent_vector[i]-=(reduction_number * b.exponent_vector[i]);
822 // multiple reduction
823 // reduction corresponds to subtraction of vectors
824
825 short sign=w.compare_to_zero(exponent_vector);
826
827
828 #ifdef NO_SUPPORT_DRIVEN_METHODS
829
830 if(sign==0)
831 // binomial reduced to zero
832 return 2;
833
834 for(short i=0;i<_number_of_variables;i++)
835 exponent_vector[i]*=sign;
836
837 #endif // NO_SUPPORT_DRIVEN_METHODS
838
839
840 #ifdef SUPPORT_DRIVEN_METHODS
841
842 head_support=0;
843 tail_support=0;
844
845 if(sign==0)
846 // binomial reduced to zero
847 return 2;
848
849 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
850
851
852 // recompute the support vectors
853
854 #ifdef SUPPORT_VARIABLES_FIRST
855
856 for(short i=0;i<_number_of_variables;i++)
857 {
858
859 Integer& actual_entry=exponent_vector[i];
860 // to avoid unnecessary pointer arithmetic
861
862 actual_entry*=sign;
863
864 if(i<size_of_support_vectors)
865 if(actual_entry>0)
866 head_support|=(1<<i);
867 else
868 if(actual_entry<0)
869 tail_support|=(1<<i);
870 }
871
872 #endif // SUPPORT_VARIABLES_FIRST
873
874
875 #ifdef SUPPORT_VARIABLES_LAST
876
877 for(short i=0;i<_number_of_variables;i++)
878 {
879 Integer& actual_entry=exponent_vector[_number_of_variables-1-i];
880 // to avoid unneccessary pointer arithmetic
881
882 actual_entry*=sign;
883
884 if(i<size_of_support_vectors)
885 {
886 if(actual_entry>0)
887 head_support|=(1<<i);
888 else if(actual_entry<0)
889 tail_support|=(1<<i);
890 }
891 }
892
893 #endif // SUPPORT_VARIABLES_LAST
894
895
896 #endif // SUPPORT_DRIVEN_METHODS
897
898 return 1;
899 }
900
901
902
903
reduce_tail_by(const binomial & b,const term_ordering & w)904 int binomial::reduce_tail_by(const binomial& b, const term_ordering& w)
905 {
906 Integer reduction_number=tail_reductions_by(b);
907 if(reduction_number<=0)
908 return 0;
909
910 for(short i=0;i<_number_of_variables;i++)
911 exponent_vector[i]+=(reduction_number * b.exponent_vector[i]);
912 // multiple reduction
913 // reduction corresponds to addition of vectors
914
915 // a tail reduction does not require a sign check
916
917
918 #ifdef SUPPORT_DRIVEN_METHODS
919
920 head_support=0;
921 tail_support=0;
922
923 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
924
925
926 // recompute the support vectors
927
928 #ifdef SUPPORT_VARIABLES_FIRST
929
930 for(short i=0;i<_number_of_variables;i++)
931 {
932
933 Integer& actual_entry=exponent_vector[i];
934 // to avoid unnecessary pointer arithmetic
935
936 if(i<size_of_support_vectors)
937 {
938 if(actual_entry>0)
939 head_support|=(1<<i);
940 else if(actual_entry<0)
941 tail_support|=(1<<i);
942 }
943 }
944
945 #endif // SUPPORT_VARIABLES_FIRST
946
947
948 #ifdef SUPPORT_VARIABLES_LAST
949
950 for(short i=0;i<_number_of_variables;i++)
951 {
952 Integer& actual_entry=exponent_vector[_number_of_variables-1-i];
953 // to avoid unneccessary pointer arithmetic
954
955 if(i<size_of_support_vectors)
956 {
957 if(actual_entry>0)
958 head_support|=(1<<i);
959 else if(actual_entry<0)
960 tail_support|=(1<<i);
961 }
962 }
963
964 #endif // SUPPORT_VARIABLES_LAST
965
966
967 #endif // SUPPORT_DRIVEN_METHODS
968
969 return 1;
970 }
971
972
973
974
S_binomial(const binomial & a,const binomial & b,const term_ordering & w)975 binomial& S_binomial(const binomial& a, const binomial& b,
976 const term_ordering& w)
977 {
978 binomial* S_bin=new binomial(a._number_of_variables);
979 binomial& result=*S_bin;
980 // Note that we allocate memory for the result binomial. We often use
981 // pointers or references as argument and return types because the
982 // generating binomials of an ideal are kept in lists. For the performance
983 // of Buchberger's algorithm it it very important to avoid local copies
984 // of binomials, so a lot of attention is paid on the choice of argument
985 // and return types. As this choice is done in order to improve performance,
986 // it might be a bad choice with respect to code reuse (there are some
987 // dangerous constructions).
988
989 for(short i=0;i<result._number_of_variables;i++)
990 result.exponent_vector[i]=a.exponent_vector[i]-b.exponent_vector[i];
991 // The S-binomial corresponds to the vector difference.
992
993 // compute head and tail
994 short sign=w.compare_to_zero(result.exponent_vector);
995
996
997 #ifdef NO_SUPPORT_DRIVEN_METHODS
998
999 if(sign==0)
1000 // binomial reduced to zero
1001 return result;
1002
1003 for(short i=0;i<result._number_of_variables;i++)
1004 result.exponent_vector[i]*=sign;
1005
1006 #endif // NO_SUPPORT_DRIVEN_METHODS
1007
1008
1009 #ifdef SUPPORT_DRIVEN_METHODS
1010
1011 result.head_support=0;
1012 result.tail_support=0;
1013
1014 if(sign==0)
1015 // binomial reduced to zero
1016 return result;
1017
1018 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1019
1020
1021 // recompute the support vectors
1022
1023 #ifdef SUPPORT_VARIABLES_FIRST
1024
1025 for(short i=0;i<result._number_of_variables;i++)
1026 {
1027
1028 Integer& actual_entry=result.exponent_vector[i];
1029 // to avoid unnecessary pointer arithmetic
1030
1031 actual_entry*=sign;
1032
1033 if(i<size_of_support_vectors)
1034 {
1035 if(actual_entry>0)
1036 result.head_support|=(1<<i);
1037 else if(actual_entry<0)
1038 result.tail_support|=(1<<i);
1039 }
1040 }
1041
1042 #endif // SUPPORT_VARIABLES_FIRST
1043
1044
1045 #ifdef SUPPORT_VARIABLES_LAST
1046
1047 for(short i=0;i<result._number_of_variables;i++)
1048 {
1049 Integer& actual_entry=result.exponent_vector
1050 [result._number_of_variables-1-i];
1051 // to avoid unneccessary pointer arithmetic
1052
1053 actual_entry*=sign;
1054
1055 if(i<size_of_support_vectors)
1056 {
1057 if(actual_entry>0)
1058 result.head_support|=(1<<i);
1059 else if(actual_entry<0)
1060 result.tail_support|=(1<<i);
1061 }
1062 }
1063
1064 #endif // SUPPORT_VARIABLES_LAST
1065
1066
1067 #endif // SUPPORT_DRIVEN_METHODS
1068
1069
1070 return result;
1071 }
1072
1073
1074
1075
1076 ///////////// criteria for unnecessary S-pairs ///////////////////////////////
1077
1078 // The criteria are programmed in a way that tries to minimize pointer
1079 // arithmetic. Therefore the code may appear a little bit inflated.
1080
1081
1082
1083
relatively_prime(const binomial & a,const binomial & b)1084 BOOLEAN relatively_prime(const binomial& a, const binomial& b)
1085 {
1086
1087 #ifdef NO_SUPPORT_DRIVEN_METHODS
1088
1089 // look at all variables
1090 for(short i=0;i<a._number_of_variables;i++)
1091 if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1092 return FALSE;
1093
1094 return TRUE;
1095
1096 #endif // NO_SUPPORT_DRIVEN_METHODS
1097
1098
1099 #ifdef SUPPORT_DRIVEN_METHODS
1100
1101 if((a.head_support & b.head_support)!=0)
1102 // common support variable in the heads
1103 return FALSE;
1104
1105 // no common support variable in the heads, look at remaining variables
1106 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1107
1108
1109 #ifdef SUPPORT_VARIABLES_FIRST
1110
1111 for(short i=size_of_support_vectors;i<a._number_of_variables;i++)
1112 if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1113 return FALSE;
1114
1115 return TRUE;
1116
1117 #endif // SUPPORT_VARIABLES_FIRST
1118
1119
1120 #ifdef SUPPORT_VARIABLES_LAST
1121
1122 for(short i=a._number_of_variables-1-size_of_support_vectors;i>=0;i--)
1123 if((a.exponent_vector[i]>0) && (b.exponent_vector[i]>0))
1124 return FALSE;
1125
1126 return TRUE;
1127
1128 #endif // SUPPORT_VARIABLES_LAST
1129
1130
1131 #endif // SUPPORT_DRIVEN_METHODS
1132
1133 }
1134
1135
1136
1137
M(const binomial & a,const binomial & b,const binomial & c)1138 BOOLEAN M(const binomial& a, const binomial& b, const binomial& c)
1139 // Returns TRUE iff lcm(head(a),head(c)) divides properly lcm(head(b),head(c)).
1140 // This is checked by comparing the positive components of the exponent
1141 // vectors.
1142 {
1143
1144
1145 #ifdef SUPPORT_DRIVEN_METHODS
1146
1147 long b_or_c=b.head_support|c.head_support;
1148
1149 if((a.head_support|b_or_c) != b_or_c)
1150 return FALSE;
1151 // The support of lcm(head(a),head(c)) equals the union of the head supports
1152 // of a and c. The above condition verifies if the support of
1153 // lcm(head(a),head(c)) is contained in the support of lcm(head(b),head(c))
1154 // by checking if head a involves a variable that is not involved in
1155 // head(b) or head(c).
1156
1157 #endif // SUPPORT_DRIVEN_METHODS
1158
1159
1160 BOOLEAN properly=FALSE;
1161
1162 for(short i=0;i<a._number_of_variables;i++)
1163 {
1164 Integer a_exponent=a.exponent_vector[i];
1165 Integer b_exponent=b.exponent_vector[i];
1166 Integer c_exponent=c.exponent_vector[i];
1167 Integer m1=MAXIMUM(a_exponent,c_exponent);
1168 Integer m2=MAXIMUM(b_exponent,c_exponent);
1169
1170 if(m1>0)
1171 {
1172 if(m1>m2)
1173 return FALSE;
1174 if(m1<m2)
1175 properly=TRUE;
1176 }
1177 }
1178
1179 return properly;
1180 }
1181
1182
1183
1184
F(const binomial & a,const binomial & b,const binomial & c)1185 BOOLEAN F(const binomial& a, const binomial& b, const binomial& c)
1186 // verifies if lcm(head(a),head(c))=lcm(head(b),head(c))
1187 {
1188
1189 #ifdef SUPPORT_DRIVEN_METHODS
1190
1191 if((a.head_support|c.head_support)!=(b.head_support|c.head_support))
1192 return FALSE;
1193 // The above condition verifies if the support of lcm(head(a),head(c))
1194 // equals the support of lcm(head(b),head(c)).
1195
1196 #endif // SUPPORT_DRIVEN_METHODS
1197
1198 for(short i=0;i<a._number_of_variables;i++)
1199 {
1200 Integer a_exponent=a.exponent_vector[i];
1201 Integer b_exponent=b.exponent_vector[i];
1202 Integer c_exponent=c.exponent_vector[i];
1203 Integer m1=MAXIMUM(a_exponent,c_exponent);
1204 Integer m2=MAXIMUM(b_exponent,c_exponent);
1205
1206 if((m1!=m2) && (m1>0 || m2>0))
1207 return FALSE;
1208 }
1209
1210 return TRUE;
1211 }
1212
1213
1214
1215
B(const binomial & a,const binomial & b,const binomial & c)1216 BOOLEAN B(const binomial& a, const binomial& b, const binomial& c)
1217 // verifies if head(a) divides lcm(head(b),head(c)) and
1218 // lcm(head(a),head(b))!=lcm(head(b),head(c))!=lcm(head(a),head(c))
1219 {
1220
1221 #ifdef SUPPORT_DRIVEN_METHODS
1222
1223 long a_or_b=a.head_support|b.head_support;
1224 long a_or_c=a.head_support|c.head_support;
1225 long b_or_c=b.head_support|c.head_support;
1226
1227 if((a.head_support & b_or_c)!=a.head_support)
1228 return FALSE;
1229 // The above condition verifies if the support of head(a) is contained in
1230 // the support of lcm(head(b),head(c)).
1231
1232 if( (a_or_c != b_or_c) && (a_or_b != b_or_c))
1233 // Then the inequality conditions are guaranteed...
1234 {
1235 for(short i=0;i<a._number_of_variables;i++)
1236 {
1237 Integer b_exponent=b.exponent_vector[i];
1238 Integer c_exponent=c.exponent_vector[i];
1239
1240 if(a.exponent_vector[i]>MAXIMUM(b_exponent,c_exponent))
1241 return FALSE;
1242 }
1243
1244 return (TRUE);
1245 }
1246
1247
1248 if(a_or_b != b_or_c)
1249 // Then the first inequality conditions is guaranteed...
1250 // Verifie only the second.
1251 {
1252 BOOLEAN not_equal=FALSE;
1253
1254 for(short i=0;i<a._number_of_variables;i++)
1255 {
1256 Integer a_exponent=a.exponent_vector[i];
1257 Integer b_exponent=b.exponent_vector[i];
1258 Integer c_exponent=c.exponent_vector[i];
1259 Integer m=MAXIMUM(b_exponent, c_exponent);
1260
1261 if(a_exponent>m)
1262 return FALSE;
1263
1264 if(MAXIMUM(a_exponent,c_exponent) != m)
1265 not_equal=TRUE;
1266 }
1267 return(not_equal);
1268 }
1269
1270
1271 if( a_or_c != b_or_c )
1272 // Then the second inequality conditions is guaranteed...
1273 // Verifie only the first.
1274 {
1275 BOOLEAN not_equal=FALSE;
1276
1277 for(short i=0;i<a._number_of_variables;i++)
1278 {
1279 Integer a_exponent=a.exponent_vector[i];
1280 Integer b_exponent=b.exponent_vector[i];
1281 Integer c_exponent=c.exponent_vector[i];
1282 Integer m=MAXIMUM(b_exponent, c_exponent);
1283
1284 if(a_exponent > m)
1285 return FALSE;
1286
1287 if(MAXIMUM(a_exponent,b_exponent) != m)
1288 not_equal=TRUE;
1289 }
1290 return(not_equal);
1291 }
1292
1293 #endif // SUPPORT_DRIVEN_METHODS
1294
1295
1296 BOOLEAN not_equal_1=FALSE;
1297 BOOLEAN not_equal_2=FALSE;
1298
1299 for(short i=0;i<a._number_of_variables;i++)
1300 {
1301 Integer a_exponent=a.exponent_vector[i];
1302 Integer b_exponent=b.exponent_vector[i];
1303 Integer c_exponent=c.exponent_vector[i];
1304 Integer m=MAXIMUM(b_exponent, c_exponent);
1305
1306 if(a_exponent > m)
1307 return FALSE;
1308
1309 if(MAXIMUM(a_exponent,b_exponent) != m)
1310 not_equal_1=TRUE;
1311 if(MAXIMUM(a_exponent,c_exponent) != m)
1312 not_equal_2=TRUE;
1313 }
1314
1315 return (not_equal_1 && not_equal_2);
1316
1317 }
1318
1319
1320
1321
second_crit(const binomial & a,const binomial & b,const binomial & c)1322 BOOLEAN second_crit(const binomial& a, const binomial& b,
1323 const binomial& c)
1324 // verifies if head(a) divides lcm(head(b),head(c))
1325 {
1326
1327 #ifdef SUPPORT_DRIVEN_METHODS
1328
1329 if((a.head_support & (b.head_support|c.head_support))!=a.head_support)
1330 return FALSE;
1331 // The above condition verifies if the support of head(a) is contained in
1332 // the support of lcm(head(b),head(c))
1333
1334 #endif // SUPPORT_DRIVEN_METHODS.
1335
1336 for(short i=0;i<a._number_of_variables;i++)
1337 {
1338 Integer b_exponent=b.exponent_vector[i];
1339 Integer c_exponent=c.exponent_vector[i];
1340
1341 if(a.exponent_vector[i]>MAXIMUM(b_exponent,c_exponent))
1342 return FALSE;
1343 }
1344
1345 return (TRUE);
1346 }
1347
1348
1349
1350
1351 //////// special routines needed by the IP-algorithms ///////////////////////
1352
1353
1354
1355
involves_elimination_variables(const term_ordering & w)1356 BOOLEAN binomial::involves_elimination_variables(const term_ordering& w)
1357 {
1358 // The use of support information would require the distinction of various
1359 // cases here (relation between the number of variables to eliminate
1360 // and the number of support variables) and be quite difficult.
1361 // It is doubtful if this would improve performance.
1362 // As this function is not used in Buchberger�s algorithm (and therefore
1363 // rather rarely), I renounce to implement this.
1364
1365 for(short i=0;i<w.number_of_elimination_variables();i++)
1366 // elimination variables are always the last ones
1367 if(exponent_vector[_number_of_variables-1-i]!=0)
1368 return TRUE;
1369
1370 return FALSE;
1371 }
1372
1373
1374
1375
drop_elimination_variables(const term_ordering & w)1376 BOOLEAN binomial::drop_elimination_variables(const term_ordering& w)
1377 {
1378 _number_of_variables-=w.number_of_elimination_variables();
1379 // dangerous (no compatibility check)!!
1380
1381 // copy components of interest to save memory
1382 // the leading term has to be recomputed!!
1383
1384 Integer *aux=exponent_vector;
1385 exponent_vector=new Integer[_number_of_variables];
1386
1387 if(w.weight(aux)>=0)
1388 for(short i=0;i<_number_of_variables;i++)
1389 exponent_vector[i]=aux[i];
1390 else
1391 for(short i=0;i<_number_of_variables;i++)
1392 exponent_vector[i]=-aux[i];
1393
1394 delete[] aux;
1395
1396
1397 #ifdef SUPPORT_DRIVEN_METHODS
1398
1399 // Recompute head and tail.
1400 // Normally, this routine is only called for binomials that do not involve
1401 // the variables to eliminate. But if SUPPORT_VARIABLES_LAST is enabled,
1402 // the support changes in spite of this. Therefore, the support is
1403 // recomputed... For the same reasons as mentionned in the preceeding
1404 // routine, the existing support information is not used.
1405
1406 head_support=0;
1407 tail_support=0;
1408 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1409 if(size_of_support_vectors>_number_of_variables)
1410 size_of_support_vectors=_number_of_variables;
1411
1412
1413 #ifdef SUPPORT_VARIABLES_FIRST
1414
1415 for(short i=0;i<size_of_support_vectors;i++)
1416 {
1417 Integer actual_entry=exponent_vector[i];
1418 if(actual_entry>0)
1419 head_support|=(1<<i);
1420 else if(actual_entry[i]<0)
1421 tail_support|=(1<<i);
1422 }
1423
1424 #endif // SUPPORT_VARIABLES_FIRST
1425
1426
1427 #ifdef SUPPORT_VARIABLES_LAST
1428
1429 for(short i=0;i<size_of_support_vectors;i++)
1430 {
1431 Integer actual_entry=exponent_vector[_number_of_variables-1-i];
1432 if(actual_entry>0)
1433 head_support|=(1<<i);
1434 else if(actual_entry<0)
1435 tail_support|=(1<<i);
1436 }
1437
1438 #endif // SUPPORT_VARIABLES_LAST
1439
1440
1441 #endif // SUPPORT_DRIVEN_METHODS
1442 return TRUE;
1443
1444 }
1445
1446
1447
1448
drop_last_weighted_variable(const term_ordering & w)1449 BOOLEAN binomial::drop_last_weighted_variable(const term_ordering& w)
1450 {
1451 _number_of_variables--;
1452 // dangerous!!
1453
1454 // copy components of interest to save memory
1455 // the leading term has to be recomputed!!
1456
1457 Integer *aux=exponent_vector;
1458 exponent_vector=new Integer[_number_of_variables];
1459
1460 short last_weighted_variable=w.number_of_weighted_variables()-1;
1461 aux[last_weighted_variable]=0;
1462 // set last component to zero, so it cannot influence the weight
1463
1464 if(w.weight(aux)>=0)
1465 {
1466 for(short i=0;i<last_weighted_variable;i++)
1467 exponent_vector[i]=aux[i];
1468 for(short i=last_weighted_variable;i<_number_of_variables;i++)
1469 exponent_vector[i]=aux[i+1];
1470 }
1471 else
1472 {
1473 for(short i=0;i<last_weighted_variable;i++)
1474 exponent_vector[i]=-aux[i];
1475 for(short i=last_weighted_variable;i<_number_of_variables;i++)
1476 exponent_vector[i]=-aux[i+1];
1477 }
1478
1479 delete[] aux;
1480
1481
1482 #ifdef SUPPORT_DRIVEN_METHODS
1483
1484 // Recompute head and tail.
1485 // Normally, this routine is only called for binomials that do not involve
1486 // the variable to be dropped. But if SUPPORT_VARIABLES_LAST is enabled,
1487 // the support changes in spite of this. Therefore, the support is
1488 // recomputed... For the same reasons as mentionned in the preceeding
1489 // routines, the existing support information is not used.
1490
1491 head_support=0;
1492 tail_support=0;
1493 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1494 if(size_of_support_vectors>_number_of_variables)
1495 size_of_support_vectors=_number_of_variables;
1496
1497
1498 #ifdef SUPPORT_VARIABLES_FIRST
1499
1500 for(short i=0;i<size_of_support_vectors;i++)
1501 {
1502 Integer actual_entry=exponent_vector[i];
1503 if(actual_entry>0)
1504 head_support|=(1<<i);
1505 else if(actual_entry<0)
1506 tail_support|=(1<<i);
1507 }
1508
1509 #endif // SUPPORT_VARIABLES_FIRST
1510
1511
1512 #ifdef SUPPORT_VARIABLES_LAST
1513
1514 for(short i=0;i<size_of_support_vectors;i++)
1515 {
1516 Integer actual_entry=exponent_vector[_number_of_variables-1-i];
1517 if(actual_entry>0)
1518 head_support|=(1<<i);
1519 else if(actual_entry<0)
1520 tail_support|=(1<<i);
1521 }
1522
1523 #endif // SUPPORT_VARIABLES_LAST
1524
1525 #endif // SUPPORT_DRIVEN_METHODS
1526 return TRUE;
1527 }
1528
1529
1530
1531
adapt_to_term_ordering(const term_ordering & w)1532 int binomial::adapt_to_term_ordering(const term_ordering& w)
1533 {
1534
1535 if(w.compare_to_zero(exponent_vector)<0)
1536 {
1537 // then exchange head and tail
1538 for(short i=0;i<_number_of_variables;i++)
1539 exponent_vector[i]*=(-1);
1540
1541
1542 #ifdef SUPPORT_DRIVEN_METHODS
1543
1544 unsigned long swap=head_support;
1545 head_support=tail_support;
1546 tail_support=swap;
1547
1548 #endif
1549
1550
1551 return -1;
1552 // binomial changed
1553 }
1554
1555 else
1556 return 1;
1557 // binomial unchanged
1558 }
1559
1560
1561
1562
swap_variables(const short & i,const short & j)1563 binomial& binomial::swap_variables(const short& i, const short& j)
1564 {
1565
1566
1567 #ifdef SUPPORT_DRIVEN_METHODS
1568
1569 // First adjust head_support and tail_support.
1570
1571 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1572 if(size_of_support_vectors>_number_of_variables)
1573 size_of_support_vectors=_number_of_variables;
1574
1575
1576 #ifdef SUPPORT_VARIABLES_FIRST
1577
1578 if(i<size_of_support_vectors)
1579 // else i is no support variable
1580 {
1581 if(exponent_vector[j]>0)
1582 // bit i will be 1 in the new head_support, 0 in the new tail_support
1583 {
1584 head_support|=(1<<i);
1585 // bit i is set to 1
1586
1587 tail_support&=~(1<<i);
1588 // bit i is set to 0
1589 // (in the complement ~(1<<i) all bits are 1 except from bit i)
1590 }
1591
1592 if(exponent_vector[j]==0)
1593 // bit i will be 0 in the new head_support, 0 in the new tail_support
1594 {
1595 head_support&=~(1<<i);
1596 // bit i is set to 0
1597
1598 tail_support&=~(1<<i);
1599 // bit i is set to 0
1600 }
1601
1602 if(exponent_vector[j]<0)
1603 // bit i will be 0 in the new head_support, 1 in the new tail_support
1604 {
1605 head_support&=~(1<<i);
1606 // bit i is set to 0
1607
1608 tail_support|=(1<<i);
1609 // bit i is set to 1
1610 }
1611 }
1612
1613
1614 if(j<size_of_support_vectors)
1615 // else j is no support variable
1616 {
1617 if(exponent_vector[i]>0)
1618 // bit j will be 1 in the new head_support, 0 in the new tail_support
1619 {
1620 head_support|=(1<<j);
1621 // bit j is set to 1
1622
1623 tail_support&=~(1<<j);
1624 // bit j is set to 0
1625 // (in the complement ~(1<<j) all bits are 1 except from bit j)
1626 }
1627
1628 if(exponent_vector[i]==0)
1629 // bit j will be 0 in the new head_support, 0 in the new tail_support
1630 {
1631 head_support&=~(1<<j);
1632 // bit j is set to 0
1633
1634 tail_support&=~(1<<j);
1635 // bit j is set to 0
1636 }
1637
1638 if(exponent_vector[i]<0)
1639 // bit j will be 0 in the new head_support, 1 in the new tail_support
1640 {
1641 head_support&=~(1<<j);
1642 // bit j is set to 0
1643
1644 tail_support|=(1<<j);
1645 // bit j is set to 1
1646 }
1647 }
1648
1649 #endif // SUPPORT_VARIABLES_FIRST
1650
1651
1652 #ifdef SUPPORT_VARIABLES_LAST
1653
1654 // Using SUPPORT_VARIABLES_LAST, bit k of the support vectors
1655 // corresponds to exponent_vector[_number_of_variables-1-k],
1656 // hence bit _number_of_variables-1-i to exponent_vector[i].
1657
1658 if(i>=_number_of_variables-size_of_support_vectors)
1659 // else i is no support variable
1660 {
1661 if(exponent_vector[j]>0)
1662 // bit _number_of_variables-1-i will be 1 in the new head_support,
1663 // 0 in the new tail_support
1664 {
1665 short k=_number_of_variables-1-i;
1666
1667 head_support|=(1<<k);
1668 // bit _number_of_variables-1-i is set to 1
1669
1670 tail_support&=~(1<<k);
1671 // bit _number_of_variables-1-i is set to 0
1672 // (in the complement ~(1<<(_number_of_variables-1-i)) all bits are 1
1673 // except from bit _number_of_variables-1-i)
1674 }
1675
1676 if(exponent_vector[j]==0)
1677 // bit _number_of_variables-1-i will be 0 in the new head_support,
1678 // 0 in the new tail_support
1679 {
1680 short k=_number_of_variables-1-i;
1681
1682 head_support&=~(1<<k);
1683 // bit _number_of_variables-1-i is set to 0
1684
1685 tail_support&=~(1<<k);
1686 // bit _number_of_variables-1-i is set to 0
1687 }
1688
1689 if(exponent_vector[j]<0)
1690 // bit _number_of_variables-1-i will be 0 in the new head_support,
1691 // 1 in the new tail_support
1692 {
1693 short k=_number_of_variables-1-i;
1694
1695 head_support&=~(1<<k);
1696 // bit _number_of_variables-1-i is set to 0
1697
1698 tail_support|=(1<<k);
1699 // bit _number_of_variables-1-i is set to 1
1700 }
1701 }
1702
1703
1704 if(j>=_number_of_variables-size_of_support_vectors)
1705 // else j is no support variable
1706 {
1707 if(exponent_vector[i]>0)
1708 // bit _number_of_variables-1-j will be 1 in the new head_support,
1709 // 0 in the new tail_support
1710 {
1711 short k=_number_of_variables-1-j;
1712
1713 head_support|=(1<<k);
1714 // bit _number_of_variables-1-j is set to 1
1715
1716 tail_support&=~(1<<k);
1717 // bit _number_of_variables-1-j is set to 0
1718 // (in the complement ~(1<<(_number_of_variables-1-j)) all bits are 1
1719 // except from bit _number_of_variables-1-j)
1720 }
1721
1722 if(exponent_vector[i]==0)
1723 // bit _number_of_variables-1-j will be 0 in the new head_support,
1724 // 0 in the new tail_support
1725 {
1726 short k=_number_of_variables-1-j;
1727
1728 head_support&=~(1<<k);
1729 // bit _number_of_variables-1-j is set to 0
1730
1731 tail_support&=~(1<<k);
1732 // bit _number_of_variables-1-j is set to 0
1733 }
1734
1735 if(exponent_vector[i]<0)
1736 // bit _number_of_variables-1-j will be 0 in the new head_support,
1737 // 1 in the new tail_support
1738 {
1739 short k=_number_of_variables-1-j;
1740
1741 head_support&=~(1<<k);
1742 // bit _number_of_variables-1-j is set to 0
1743
1744 tail_support|=(1<<k);
1745 // bit _number_of_variables-1-j is set to 1
1746 }
1747 }
1748
1749 #endif // SUPPORT_VARIABLES_LAST
1750
1751 #endif // SUPPORT_DRIVEN_METHODS
1752
1753
1754 // Now swap the components.
1755
1756 Integer swap=exponent_vector[j];
1757 exponent_vector[j]=exponent_vector[i];
1758 exponent_vector[i]=swap;
1759
1760 return *this;
1761
1762 }
1763
flip_variable(const short & i)1764 binomial& binomial::flip_variable(const short& i)
1765 {
1766
1767 if(exponent_vector[i]==0)
1768 // binomial does not involve variable to flip
1769 return *this;
1770
1771
1772 #ifdef SUPPORT_DRIVEN_METHODS
1773
1774 // First adjust head_support and tail_support.
1775
1776 short size_of_support_vectors=CHAR_BIT*sizeof(unsigned long);
1777 if(size_of_support_vectors>_number_of_variables)
1778 size_of_support_vectors=_number_of_variables;
1779
1780
1781 #ifdef SUPPORT_VARIABLES_FIRST
1782
1783 if(i<size_of_support_vectors)
1784 // else i is no support variable
1785 {
1786 if(exponent_vector[i]>0)
1787 // variable i will be moved from head to tail
1788 {
1789 head_support&=~(1<<i);
1790 // bit i is set to 0
1791
1792 tail_support|=(1<<i);
1793 // bit i is set to 1
1794 }
1795
1796 else
1797 // variable i will be moved from tail to head
1798 // remember that exponent_vector[i]!=0
1799 {
1800 tail_support&=~(1<<i);
1801 // bit i is set to 0
1802
1803 head_support|=(1<<i);
1804 // bit i is set to 1
1805 }
1806 }
1807 #endif // SUPPORT_VARIABLES_FIRST
1808
1809 #ifdef SUPPORT_VARIABLES_LAST
1810
1811 // Using SUPPORT_VARIABLES_LAST, bit k of the support vectors
1812 // corresponds to exponent_vector[_number_of_variables-1-k],
1813 // hence bit _number_of_variables-1-i to exponent_vector[i].
1814
1815 if(i>=_number_of_variables-size_of_support_vectors)
1816 // else i is no support variable
1817 {
1818 if(exponent_vector[i]>0)
1819 // variable i will be moved from head to tail
1820 {
1821 short k=_number_of_variables-1-i;
1822
1823 head_support&=~(1<<k);
1824 // bit _number_of_variables-1-i is set to 0
1825
1826 tail_support|=(1<<k);
1827 // bit _number_of_variables-1-i is set to 1
1828
1829 }
1830
1831 else
1832 // variable i will be moved from tail to head
1833 {
1834 short k=_number_of_variables-1-i;
1835
1836 tail_support&=~(1<<k);
1837 // bit _number_of_variables-1-i is set to 0
1838
1839 head_support|=(1<<k);
1840 // bit _number_of_variables-1-i is set to 1
1841
1842 }
1843 }
1844 #endif // SUPPORT_VARIABLES_LAST
1845
1846
1847 #endif // SUPPORT_DRIVEN_METHODS
1848
1849 // Now flip the variable.
1850
1851 exponent_vector[i]*=-1;
1852 return *this;
1853 }
1854
1855 ////////////////////////// output /////////////////////////////////////////
1856
print() const1857 void binomial::print() const
1858 {
1859 printf("(");
1860 for(short i=0;i<_number_of_variables-1;i++)
1861 printf("%6d,",exponent_vector[i]);
1862 printf("%6d)\n",exponent_vector[_number_of_variables-1]);
1863 }
1864
print_all() const1865 void binomial::print_all() const
1866 {
1867 print();
1868
1869 #ifdef SUPPORT_DRIVEN_METHODS
1870
1871 printf("head: %ld, tail %ld\n",head_support,tail_support);
1872
1873 #endif // SUPPORT_DRIVEN_METHODS
1874 }
1875
print(FILE * output) const1876 void binomial::print(FILE* output) const
1877 {
1878 fprintf(output,"(");
1879 for(short i=0;i<_number_of_variables-1;i++)
1880 fprintf(output,"%6d,",exponent_vector[i]);
1881 fprintf(output,"%6d)\n",exponent_vector[_number_of_variables-1]);
1882 }
1883
print_all(FILE * output) const1884 void binomial::print_all(FILE* output) const
1885 {
1886 print(output);
1887
1888 #ifdef SUPPORT_DRIVEN_METHODS
1889
1890 fprintf(output,"head: %ld, tail %ld\n",head_support,tail_support);
1891
1892 #endif // SUPPORT_DRIVEN_METHODS
1893 }
1894
print(ofstream & output) const1895 void binomial::print(ofstream& output) const
1896 {
1897 output<<"(";
1898 for(short i=0;i<_number_of_variables-1;i++)
1899 output<<setw(6)<<exponent_vector[i]<<",";
1900 output<<setw(6)<<exponent_vector[_number_of_variables-1]<<")"<<endl;
1901 }
1902
print_all(ofstream & output) const1903 void binomial::print_all(ofstream& output) const
1904 {
1905 print(output);
1906
1907 #ifdef SUPPORT_DRIVEN_METHODS
1908
1909 output<<"head: "<<setw(16)<<head_support<<", tail: "<<setw(16)
1910 <<tail_support<<endl;
1911
1912 #endif // SUPPORT_DRIVEN_METHODS
1913 }
1914
format_print(ofstream & output) const1915 void binomial::format_print(ofstream& output) const
1916 {
1917 for(short i=0;i<_number_of_variables;i++)
1918 output<<setw(6)<<exponent_vector[i];
1919 output<<endl;
1920 }
1921
1922 #endif // BINOMIAL_CC
1923