Changeset 3216ec in git

Timestamp:

Aug 15, 2012, 1:44:30 PM (12 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

d8b0997ff6f148513d95e2f2a5a075c7386c7168

Parents:

a8ead8e63f3539f8915726efa18791dcc052733a

Message:

add: extgcd for bigint

Files:

• Singular/iparith.cc (modified) (1 diff)
• Singular/table.h (modified) (1 diff)
• libpolys/coeffs/coeffs.h (modified) (2 diffs)
• libpolys/coeffs/longrat.cc (modified) (3 diffs)
• libpolys/coeffs/longrat.h (modified) (1 diff)

Singular/iparith.cc

@@ -1974 +1974 @@
   inerror=3;
   return TRUE;
+}
+static BOOLEAN jjEXTGCD_BI(leftv res, leftv u, leftv v)
+{
+  number uu=(number)u->Data();number vv=(number)v->Data();
+  lists L=(lists)omAllocBin(slists_bin);
+  number a,b;
+  number p0=n_ExtGcd(uu,vv,&a,&b,coeffs_BIGINT);
+  L->Init(3);
+  L->m[0].rtyp=BIGINT_CMD;   L->m[0].data=(void *)p0;
+  L->m[1].rtyp=BIGINT_CMD;   L->m[1].data=(void *)a;
+  L->m[2].rtyp=BIGINT_CMD;   L->m[2].data=(void *)b;
+  res->rtyp=LIST_CMD;
+  res->data=(char *)L;
+  return FALSE;
 }
 static BOOLEAN jjEXTGCD_I(leftv res, leftv u, leftv v)

Singular/table.h

@@ -526 +526 @@
 ,{D(jjEXPORTTO),  EXPORTTO_CMD,   NONE,           PACKAGE_CMD, IDHDL, ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjEXTGCD_I),  EXTGCD_CMD,     LIST_CMD,       INT_CMD,    INT_CMD, ALLOW_PLURAL |ALLOW_RING}
+,{D(jjEXTGCD_BI), EXTGCD_CMD,     LIST_CMD,       BIGINT_CMD, BIGINT_CMD, ALLOW_PLURAL |ALLOW_RING}
 #ifdef HAVE_FACTORY
 ,{D(jjEXTGCD_P),  EXTGCD_CMD,     LIST_CMD,       POLY_CMD,   POLY_CMD, NO_PLURAL |NO_RING}

libpolys/coeffs/coeffs.h

@@ -143 +143 @@
    BOOLEAN (*cfIsUnit)(number a,const coeffs r);
    number  (*cfGetUnit)(number a,const coeffs r);
-   number  (*cfExtGcd)(number a, number b, number *s, number *t,const coeffs r);
 #endif
 
@@ -181 +180 @@
    number  (*cfGetNumerator)(number &n, const coeffs r);
    number  (*cfGcd)(number a, number b, const coeffs r);
+   number  (*cfExtGcd)(number a, number b, number *s, number *t,const coeffs r);
    number  (*cfLcm)(number a, number b, const coeffs r);
    void    (*cfDelete)(number * a, const coeffs r);

libpolys/coeffs/longrat.cc

@@ -2605 +2605 @@
 }
 
+number nlExtGcd(number a, number b, number *s, number *t, const coeffs)
+{
+  mpz_t aa,bb;
+  *s=ALLOC_RNUMBER();
+  mpz_init((*s)->z); (*s)->s=3;
+  (*t)=ALLOC_RNUMBER();
+  mpz_init((*t)->z); (*t)->s=3;
+  number g=ALLOC_RNUMBER();
+  mpz_init(g->z); g->s=3;
+  if (SR_HDL(a) & SR_INT)
+  {
+    mpz_init_set_si(aa,SR_TO_INT(a));
+  }
+  else
+  {
+    mpz_init_set(aa,a->z);
+  }
+  if (SR_HDL(b) & SR_INT)
+  {
+    mpz_init_set_si(bb,SR_TO_INT(b));
+  }
+  else
+  {
+    mpz_init_set(bb,b->z);
+  }
+  mpz_gcdext(g->z,(*s)->z,(*t)->z,aa,bb);
+  mpz_clear(aa);
+  mpz_clear(bb);
+  (*s)=nlShort3((*s));
+  (*t)=nlShort3((*t));
+  g=nlShort3(g);
+  return g;
+}
+
 void    nlCoeffWrite  (const coeffs, BOOLEAN /*details*/)
 {
@@ -2816 +2850 @@
   //r->cfIsUnit = NULL; // only for ring stuff
   //r->cfGetUnit = NULL; // only for ring stuff
-  //r->cfExtGcd = NULL; // only for ring stuff
   //r->cfDivBy = NULL; // only for ring stuff
   #endif
@@ -2837 +2870 @@
   r->cfGetNumerator = nlGetNumerator;
   r->cfGcd  = nlGcd;
+  r->cfExtGcd = nlExtGcd; // only for ring stuff and Z
   r->cfLcm  = nlLcm;
   r->cfDelete= nlDelete;

libpolys/coeffs/longrat.h

@@ -65 +65 @@
 
 number   nlGcd(number a, number b, const coeffs r);
+number nlExtGcd(number a, number b, number *s, number *t, const coeffs);
 number   nlLcm(number a, number b, const coeffs r);   /*special routine !*/
 BOOLEAN  nlGreater(number a, number b, const coeffs r);