Changeset e961571 in git

Timestamp:

Feb 19, 2013, 12:56:40 PM (10 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

73b2e93d708311ad220a6ca578c7bff10757938afd65244df2e764406fbf106074b1b1782db1d97b

Parents:

11e593b7d06bde70555fd944e100187b744cd03b

git-author:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2013-02-19 12:56:40+01:00

git-committer:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2013-02-19 13:01:11+01:00

Message:

fix: naGcd/naLcm

File:

• libpolys/polys/ext_fields/algext.cc (modified) (19 diffs)

libpolys/polys/ext_fields/algext.cc

@@ -52 +52 @@
 #endif
 
-   
+
 #include <polys/ext_fields/algext.h>
 #define TRANSEXT_PRIVATES 1
@@ -670 +670 @@
 }
 #endif
+number napLcm(number b, const coeffs cf)
+{
+  number h=n_Init(1,naRing->cf);
+  poly bb=(poly)b;
+  number d;
+  while(bb!=NULL)
+  {
+    d=n_Lcm(h,pGetCoeff(bb), naRing->cf);
+    n_Delete(&h,naRing->cf);
+    h=d;
+    pIter(bb);
+  }
+}
+number naLcmContent(number a, number b, const coeffs cf)
+{
+  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
+  else return ndGcd(a,b,cf);
+  #if 0
+  {
+    a=(number)p_Copy((poly)a,naRing);
+    number t=napLcm(b,cf);
+    if(!naIsOne(t,cf))
+    {
+      number bt, rr;
+      poly xx=(poly)a;
+      while (xx!=NULL)
+      {
+        bt = n_Gcd(t, pGetCoeff(xx), naRing->cf);
+        rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
+        n_Delete(&pGetCoeff(xx),naRing->cf);
+        pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
+        n_Normalize(pGetCoeff(xx),naRing->cf);
+        n_Delete(&bt,naRing->cf);
+        n_Delete(&rr,naRing->cf);
+        pIter(xx);
+      }
+    }
+    n_Delete(&t,naRing->cf);
+    return (number) a;
+  }
+  #endif
+}
 
 /* expects *param to be castable to AlgExtInfo */
@@ -689 +731 @@
   if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
   {
-    const ideal mi = naRing->qideal; 
+    const ideal mi = naRing->qideal;
     assume( IDELEMS(mi) == 1 );
     const ideal ii = e->r->qideal;
@@ -696 +738 @@
     // TODO: the following should be extended for 2 *equal* rings...
     assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
-    
+
     rDelete(e->r);
-    
+
     return TRUE;
   }
@@ -773 +815 @@
 number naGcd(number a, number b, const coeffs cf)
 {
+  if (a==NULL)  return naCopy(b,cf);
+  if (b==NULL)  return naCopy(a,cf);
+
+  poly ax=(poly)a;
+  poly bx=(poly)b;
+  if (pNext(ax)!=NULL)
+    return (number)p_Copy(ax, naRing);
+  else
+  {
+    if(nCoeff_is_Zp(naRing->cf))
+      return naInit(1,cf);
+    else
+    {
+      number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
+      if (n_IsOne(x,naRing->cf))
+        return (number)p_NSet(x,naRing);
+      while (pNext(ax)!=NULL)
+      {
+        pIter(ax);
+        number y = n_Gcd(x, pGetCoeff(ax), naRing->cf);
+        n_Delete(&x,naRing->cf);
+        x = y;
+        if (n_IsOne(x,naRing->cf))
+          return (number)p_NSet(x,naRing);
+      }
+      do
+      {
+        number y = n_Gcd(x, pGetCoeff(bx), naRing->cf);
+        n_Delete(&x,naRing->cf);
+        x = y;
+        if (n_IsOne(x,naRing->cf))
+          return (number)p_NSet(x,naRing);
+        pIter(bx);
+      }
+      while (bx!=NULL);
+      return (number)p_NSet(x,naRing);
+    }
+  }
+#if 0
   naTest(a); naTest(b);
-  if ((a == NULL) && (b == NULL)) WerrorS(nDivBy0);
   const ring R = naRing;
   return (number) singclap_gcd(p_Copy((poly)a, R), p_Copy((poly)b, R), R);
+#endif
 //  return (number)p_Gcd((poly)a, (poly)b, naRing);
 }
@@ -784 +865 @@
   naTest(a);
   if (a == NULL) WerrorS(nDivBy0);
-  
+
   poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
 // singclap_extgcd!
@@ -792 +873 @@
 
 //  if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
-  
+
   naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
   p_Delete(&mFactor, naRing);
-  
+
   //  /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
-  //  assume(naIsOne((number)theGcd, cf)); 
+  //  assume(naIsOne((number)theGcd, cf));
 
   if( !naIsOne((number)theGcd, cf) )
-  {  
+  {
     WerrorS("zero divisor found - your minpoly is not irreducible");
     p_Delete(&aFactor, naRing); aFactor = NULL;
@@ -984 +1065 @@
   const ring   R = cf->extRing;
   assume(R != NULL);
-  const coeffs Q = R->cf; 
-  assume(Q != NULL); 
-  assume(nCoeff_is_Q(Q));  
+  const coeffs Q = R->cf;
+  assume(Q != NULL);
+  assume(nCoeff_is_Q(Q));
 
   numberCollectionEnumerator.Reset();
@@ -1004 +1085 @@
 
   int normalcount = 0;
-  
+
   poly cand1, cand;
-  
+
   do
   {
@@ -1013 +1094 @@
 
     naTest(n);
-    
+
     cand1 = (poly)n;
 
@@ -1036 +1117 @@
     number& n = numberCollectionEnumerator.Current();
     ++length;
-    
+
     if( (--normalcount) <= 0)
       naNormalize(n, cf);
-    
+
     naTest(n);
 
 //    p_InpGcd(cand, (poly)n, R);
-    
+
     cand = singclap_gcd(cand, p_Copy((poly)n, R), R);
 
 //    cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
-    
+
     assume( naGreaterZero((number)cand, cf) ); // ???
 /*
@@ -1069 +1150 @@
     }
 */
-    
-  } 
+
+  }
 
   // part3: all coeffs = all coeffs / cand
@@ -1076 +1157 @@
     cand = p_Neg(cand, R);
 
-  c = (number)cand; naTest(c);  
+  c = (number)cand; naTest(c);
 
   poly cInverse = (poly)naInvers(c, cf);
   assume(cInverse != NULL); // c is non-zero divisor!?
 
-  
+
   numberCollectionEnumerator.Reset();
 
@@ -1102 +1183 @@
       assume(length == 0);
     }
-    
-    definiteReduce((poly &)n, naMinpoly, cf);    
-  }
-  
+
+    definiteReduce((poly &)n, naMinpoly, cf);
+  }
+
   assume(length == 0);
   assume(cInverse == NULL); //   p_Delete(&cInverse, R);
@@ -1114 +1195 @@
   number cc;
 
-  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!? 
+  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
 
   // over alg. ext. of Q // takes over the input number
-  c = (number) p_Mult_nn( (poly)c, cc, R); 
+  c = (number) p_Mult_nn( (poly)c, cc, R);
 //      p_Mult_q(p_NSet(cc, R), , R);
 
@@ -1169 +1250 @@
       }
     }
-*/  
-
-  
+*/
+
+
 //  c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
 }
@@ -1183 +1264 @@
 
   assume(cf->extRing != NULL);
-  const coeffs Q = cf->extRing->cf; 
-  assume(Q != NULL); 
-  assume(nCoeff_is_Q(Q));  
+  const coeffs Q = cf->extRing->cf;
+  assume(Q != NULL);
+  assume(nCoeff_is_Q(Q));
   number n;
   CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
@@ -1269 +1350 @@
 #endif
   cf->cfGcd          = naGcd;
-  //cf->cfLcm          = naLcm;
+  cf->cfLcm          = naLcmContent;
   cf->cfSize         = naSize;
   cf->nCoeffIsEqual  = naCoeffIsEqual;
@@ -1289 +1370 @@
     cf->cfClearDenominators = naClearDenominators;
   }
-  
+
   return FALSE;
 }