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