Changeset bba835 in git

Timestamp:

May 3, 2007, 3:27:45 PM (16 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')

Children:

75ae36afc86628e8325b039c42ab23fe91876b39

Parents:

52e38fce6d01c11b7934d7b1830db574af0f6983

Message:

*hannes: chinese remainder


git-svn-id: file:///usr/local/Singular/svn/trunk@10011 2c84dea3-7e68-4137-9b89-c4e89433aadc

Files:

• Singular/iparith.cc (modified) (5 diffs)
• doc/reference.doc (modified) (previous)
• kernel/clapconv.cc (modified) (2 diffs)
• kernel/ideals.cc (modified) (3 diffs)
• kernel/ideals.h (modified) (2 diffs)

Singular/iparith.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: iparith.cc,v 1.444 2007-03-22 13:34:52 Singular Exp $ */
+/* $Id: iparith.cc,v 1.445 2007-05-03 13:27:42 Singular Exp $ */
 
 /*
@@ -1684 +1684 @@
   return FALSE;
 }
+#if 0
 static BOOLEAN jjCHINREM_P(leftv res, leftv u, leftv v)
 {
-#if 0
-  ideal c=(ideal)u->CopyD();
+  lists c=(lists)u->CopyD(); // list of poly
   intvec* p=(intvec*)v->Data();
   int rl=p->length();
-  poly r=NULL,h;
+  poly r=NULL,h, result=NULL;
   number *x=(number *)omAlloc(rl*sizeof(number));
   number *q=(number *)omAlloc(rl*sizeof(number));
@@ -1698 +1698 @@
     q[i]=nlInit((*p)[i]);
   }
-  // for each monom
-  //number n=nlChineseRemainder(x,q,rl);
+  loop
+  {
+    for(i=rl-1;i>=0;i--)
+    {
+      if (c->m[i].Typ()!=POLY_CMD)
+      {
+        Werror("poly expected at pos %d",i+1);
+        for(i=rl-1;i>=0;i--)
+        {
+          nlDelete(&(q[i]),currRing);
+        }
+        omFree(x); omFree(q); // delete c
+        return TRUE;
+      }
+      h=((poly)c->m[i].Data());
+      if (r==NULL) r=h;
+      else if (pLmCmp(r,h)==-1) r=h;
+    }
+    if (r==NULL) break;
+    for(i=rl-1;i>=0;i--)
+    {
+      h=((poly)c->m[i].Data());
+      if (pLmCmp(r,h)==0)
+      { 
+        x[i]=pGetCoeff(h);
+        h=pLmFreeAndNext(h);
+        c->m[i].data=(char*)h;
+      }
+      else
+        x[i]=nlInit(0);
+    }
+    number n=nlChineseRemainder(x,q,rl);
+    for(i=rl-1;i>=0;i--)
+    {
+      nlDelete(&(x[i]),currRing);
+    }
+    h=pHead(r);
+    pSetCoeff(h,n);
+    result=pAdd(result,h);
+  }
   for(i=rl-1;i>=0;i--)
   {
@@ -1705 +1743 @@
   }
   omFree(x); omFree(q);
-  res->data=(char *)r;
-  return FALSE;
-#else
-  return TRUE; // not yet implemented
+  res->data=(char *)result;
+  return FALSE;
+}
 #endif
+static BOOLEAN jjCHINREM_ID(leftv res, leftv u, leftv v)
+{
+  lists c=(lists)u->CopyD(); // list of ideal
+  intvec* p=(intvec*)v->Data();
+  int rl=p->length();
+  poly r=NULL,h; 
+  ideal result;
+  ideal *x=(ideal *)omAlloc(rl*sizeof(ideal));
+  int i;
+  for(i=rl-1;i>=0;i--)
+  {
+    if (c->m[i].Typ()!=IDEAL_CMD)
+    {
+      Werror("ideal expected at pos %d",i+1);
+      omFree(x); // delete c
+      return TRUE;
+    }
+    x[i]=((ideal)c->m[i].Data());
+  }
+  number *q=(number *)omAlloc(rl*sizeof(number));
+  for(i=rl-1;i>=0;i--)
+  {
+    q[i]=nlInit((*p)[i]);
+  }
+  result=idChineseRemainder(x,q,rl);
+  for(i=rl-1;i>=0;i--)
+  {
+    nlDelete(&(q[i]),currRing);
+  }
+  omFree(q);
+  res->data=(char *)result;
+  return FALSE;
 }
 static BOOLEAN jjCOEF(leftv res, leftv u, leftv v)
@@ -3107 +3176 @@
 #endif
 ,{jjCHINREM_BI,CHINREM_CMD,    BIGINT_CMD,     INTVEC_CMD, INTVEC_CMD ALLOW_PLURAL}
-,{jjCHINREM_P, CHINREM_CMD,    POLY_CMD,       IDEAL_CMD,  IDEAL_CMD ALLOW_PLURAL}
+//,{jjCHINREM_P, CHINREM_CMD,    POLY_CMD,       LIST_CMD,   INTVEC_CMD ALLOW_PLURAL}
+,{jjCHINREM_ID,CHINREM_CMD,    IDEAL_CMD,      LIST_CMD,   INTVEC_CMD ALLOW_PLURAL}
 ,{jjCOEF,      COEF_CMD,       MATRIX_CMD,     POLY_CMD,   POLY_CMD ALLOW_PLURAL}
 ,{jjCOEFFS_Id, COEFFS_CMD,     MATRIX_CMD,     IDEAL_CMD,  POLY_CMD ALLOW_PLURAL}

kernel/clapconv.cc

@@ -3 +3 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-// $Id: clapconv.cc,v 1.8 2007-03-15 14:24:03 Singular Exp $
+// $Id: clapconv.cc,v 1.9 2007-05-03 13:27:45 Singular Exp $
 /*
 * ABSTRACT: convert data between Singular and factory
@@ -730 +730 @@
   chineseRemainder(X,Q,xnew,qnew);
   number n=convClapNSingN(xnew);
+  number p=convClapNSingN(qnew);
+  number p2=nlIntDiv(p,nlInit(2));
+  if (nlGreater(n,p2))
+  {
+     number n2=nlSub(n,p);
+     nlDelete(&n,currRing);
+     n=n2;
+  }
+  nlDelete(&p,currRing);
+  nlDelete(&p2,currRing);
   return n;
 #else

kernel/ideals.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: ideals.cc,v 1.41 2007-04-03 15:16:39 Singular Exp $ */
+/* $Id: ideals.cc,v 1.42 2007-05-03 13:27:44 Singular Exp $ */
 /*
 * ABSTRACT - all basic methods to manipulate ideals
@@ -13 +13 @@
 #include "febase.h"
 #include "numbers.h"
+#include "longrat.h"
 #include "polys.h"
 #include "ring.h"
@@ -3694 +3695 @@
   return gcd_p;
 }
+
+/*2
+* xx,q: arrays of length 0..rl-1
+* xx[i]: SB mod q[i]
+* assume: char=0
+* assume: q[i]!=0
+* destroys xx
+*/
+ideal idChineseRemainder(ideal *xx, number *q, int rl)
+{
+  ideal result=idInit(IDELEMS(xx[0]),1);
+  int i,j;
+  poly r,h,res_p;
+  number *x=(number *)omAlloc(rl*sizeof(number));
+  for(i=IDELEMS(result)-1;i>=0;i--)
+  {
+    res_p=NULL;
+    loop
+    {
+      r=NULL;
+      for(j=rl-1;j>=0;j--)
+      {
+        h=xx[j]->m[i];
+        if ((r==NULL)||(pLmCmp(r,h)==-1)) r=h;
+      }
+      if (r==NULL) break;
+      for(j=rl-1;j>=0;j--)
+      {
+        h=xx[j]->m[i];
+        if (pLmCmp(r,h)==0)
+        { 
+          x[j]=pGetCoeff(h);
+          h=pLmFreeAndNext(h);
+          xx[j]->m[i]=h;
+        }
+        else
+          x[j]=nlInit(0);
+      }
+      number n=nlChineseRemainder(x,q,rl);
+      for(j=rl-1;j>=0;j--)
+      {
+        nlDelete(&(x[j]),currRing);
+      }
+      h=pHead(r);
+      pSetCoeff(h,n);
+      res_p=pAdd(res_p,h);
+    }
+    result->m[i]=res_p;
+  }
+  omFree(x);
+  for(i=rl-1;i>=0;i--) idDelete(&(xx[i]));
+  omFree(xx);
+  return result;
+}

kernel/ideals.h

@@ -4 +4 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: ideals.h,v 1.7 2007-01-10 17:17:27 Singular Exp $ */
+/* $Id: ideals.h,v 1.8 2007-05-03 13:27:44 Singular Exp $ */
 /*
 * ABSTRACT - all basic methods to manipulate ideals
@@ -155 +155 @@
 
 poly id_GCD(poly f, poly g, const ring r);
+
+ideal idChineseRemainder(ideal *x, number *q, int rl);
 #endif