Changeset 0b0bc3 in git for libpolys

Timestamp:

Feb 8, 2013, 6:03:33 PM (11 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

c462b60ab56fe1781c7f591d40ccd2799acd6c92

Parents:

67242b64d178faf65f7a6059740248dcfbf15c53

Message:

chg: n_Farey, p_Farey, p_ChineseRemainder

from master

Location:

libpolys/polys/monomials

Files:

• p_polys.cc (modified) (1 diff)
• p_polys.h (modified) (1 diff)

libpolys/polys/monomials/p_polys.cc

@@ -59 +59 @@
 #endif
 
+/*
+ * lift ideal with coeffs over Z (mod N) to Q via Farey
+ */
+poly p_Farey(poly p, number N, const ring r)
+{
+  poly h=p_Copy(p,r);
+  poly hh=h;
+  while(h!=NULL)
+  {
+    number c=pGetCoeff(h);
+    pSetCoeff0(h,n_Farey(c,N,r->cf));
+    n_Delete(&c,r->cf);
+    pIter(h);
+  }
+  while((hh!=NULL)&&(n_IsZero(pGetCoeff(hh),r->cf)))
+  {
+    p_LmDelete(&hh,r);
+  }
+  h=hh;
+  while((h!=NULL) && (pNext(h)!=NULL))
+  {
+    if(n_IsZero(pGetCoeff(pNext(h)),r->cf))
+    {
+      p_LmDelete(&pNext(h),r);
+    }
+    else pIter(h);
+  }
+  return hh;
+}
+/*2
+* xx,q: arrays of length 0..rl-1
+* xx[i]: SB mod q[i]
+* assume: char=0
+* assume: q[i]!=0
+* destroys xx
+*/
+poly p_ChineseRemainder(poly *xx, number *x,number *q, int rl, const ring R)
+{
+  poly r,h,hh;
+  int j;
+  poly  res_p=NULL;
+  loop
+  {
+    /* search the lead term */
+    r=NULL;
+    for(j=rl-1;j>=0;j--)
+    {
+      h=xx[j];
+      if ((h!=NULL)
+      &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
+        r=h;
+    }
+    /* nothing found -> return */
+    if (r==NULL) break;
+    /* create the monomial in h */
+    h=p_Head(r,R);
+    /* collect the coeffs in x[..]*/
+    for(j=rl-1;j>=0;j--)
+    {
+      hh=xx[j];
+      if ((hh!=NULL) && (p_LmCmp(r,hh,R)==0))
+      {
+        x[j]=pGetCoeff(hh);
+        hh=p_LmFreeAndNext(hh,R);
+        xx[j]=hh;
+      }
+      else
+        x[j]=n_Init(0, R);
+    }
+    number n=n_ChineseRemainder(x,q,rl,R->cf);
+    for(j=rl-1;j>=0;j--)
+    {
+      x[j]=NULL; // nlInit(0...) takes no memory
+    }
+    if (n_IsZero(n,R)) p_Delete(&h,R);
+    else
+    {
+      p_SetCoeff(h,n,R);
+      //Print("new mon:");pWrite(h);
+      pNext(h)=res_p;
+      res_p=h; // building res_p in reverse order!
+    }
+  }
+  return pReverse(res_p);
+}
 /***************************************************************
  *

libpolys/polys/monomials/p_polys.h

@@ -36 +36 @@
 #endif
 
+poly p_Farey(poly p, number N, const ring r);
+/*
+* xx,q: arrays of length 0..rl-1
+* xx[i]: SB mod q[i]
+* assume: char=0
+* assume: q[i]!=0
+* destroys xx
+*/
+poly p_ChineseRemainder(poly *xx, number *x,number *q, int rl, const ring R);
 /***************************************************************
  *