Changeset a8e8b9 in git

Timestamp:

May 31, 2011, 5:29:48 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')

Children:

d80a1affe5140fcac28532ccf3a3ad97b41ee6ee

Parents:

7d1c995f987c51bad98f33e83e328a16ded060ec

Message:

added division with remainder


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

Location:

factory

Files:

• algext.cc (modified) (3 diffs)
• algext.h (modified) (1 diff)

factory/algext.cc

@@ -34 +34 @@
     if(f.degree() < M.degree())
       return f;
-    CanonicalForm tmp = f;
-    do
-      tmp -= lc(tmp)*M*power(M.mvar(),tmp.degree()-M.degree());
-    while(tmp.degree() >= M.degree());
+    CanonicalForm tmp = mod (f, M);
     return tmp;
   }
@@ -69 +66 @@
 }
 
+void tryDivrem (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& Q,
+                CanonicalForm& R, CanonicalForm& inv, const CanonicalForm& mipo,
+                bool& fail)
+{
+  if (F.inCoeffDomain())
+  {
+    Q= 0;
+    R= F;
+    return;
+  }
+
+  CanonicalForm A, B;
+  Variable x= F.mvar();
+  A= F;
+  B= G;
+  int degA= degree (A, x);
+  int degB= degree (B, x);
+
+  if (degA < degB)
+  {
+    R= A;
+    Q= 0;
+    return;
+  }
+
+  tryInvert (Lc (B), mipo, inv, fail);
+  if (fail)
+    return;
+
+  R= A;
+  Q= 0;
+  CanonicalForm Qi;
+  for (int i= degA -degB; i >= 0; i--)
+  {
+    if (degree (R, x) == i + degB)
+    {
+      Qi= Lc (R)*inv*power (x, i);
+      Qi= reduce (Qi, mipo);
+      R -= Qi*B;
+      R= reduce (R, mipo);
+      Q += Qi;
+    }
+  }
+}
+
 void tryEuclid( const CanonicalForm & A, const CanonicalForm & B, const CanonicalForm & M, CanonicalForm & result, bool & fail )
 {
@@ -107 +149 @@
   }
   Variable x = P.mvar();
-  CanonicalForm rem;
+  CanonicalForm rem, Q;
   // here: degree(P) >= degree(result)
   while(true)
   {
-    tryInvert( Lc(result), M, inv, fail );
-    if(fail)
-      return;
-    // here: Lc(result) is invertible modulo M
-    rem = reduce( P - Lc(P)*inv*result*power( x, P.degree(x)-result.degree(x) ), M );
+    tryDivrem (P, result, Q, rem, inv, M, fail);
+    if (fail)
+      return;
     if( rem.isZero() )
     {

factory/algext.h

@@ -8 +8 @@
 
 CanonicalForm QGCD( const CanonicalForm &, const CanonicalForm & );
+void tryDivrem (const CanonicalForm&, const CanonicalForm&, CanonicalForm&,
+                CanonicalForm&, CanonicalForm&, const CanonicalForm&,
+                bool&);
 void tryEuclid( const CanonicalForm &, const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool & );
 void tryInvert( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool & );