Changeset 42281d6 in git

Timestamp:

Jul 6, 2011, 7:04:52 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

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

Children:

13f4949d39b811d9e4ba8e8cbff2c4565ce87187

Parents:

ec970ef2b3d7d5253124f91a7c731ac3c7c540c3

Message:

divisibility test


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

Location:

factory

Files:

• cf_algorithm.cc (modified) (2 diffs)
• cf_algorithm.h (modified) (1 diff)

factory/cf_algorithm.cc

@@ -30 +30 @@
 #include "cf_iter.h"
 #include "templates/ftmpl_functions.h"
+#include "algext.h"
 
 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
@@ -385 +386 @@
 //}}}
 
+/// same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
+bool
+tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail )
+{
+    fail= false;
+    // trivial cases
+    if ( g.isZero() )
+        return true;
+    else if ( f.isZero() )
+        return false;
+
+    if (f.inCoeffDomain() || g.inCoeffDomain())
+    {
+        // if we are in a field all elements not equal to zero are units
+        if ( f.inCoeffDomain() )
+        {
+            CanonicalForm inv;
+            tryInvert (f, M, inv, fail);
+            return !fail;
+        }
+        else
+        {
+            return false;
+        }
+    }
+
+    // we may assume now that both levels either equal LEVELBASE
+    // or are greater zero
+    int fLevel = f.level();
+    int gLevel = g.level();
+    if ( (gLevel > 0) && (fLevel == gLevel) )
+    {
+        if (degree( f ) > degree( g ))
+          return false;
+        bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
+
+        if (fail || !dividestail)
+          return false;
+        bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
+        if (fail || !dividesLC)
+          return false;
+        CanonicalForm q,r;
+        bool divides= tryDivremt (g, f, q, r, M, fail);
+        if (fail || !divides)
+          return false;
+        return r.isZero();
+    }
+    else if ( gLevel < fLevel )
+    {
+        // g is a coefficient w.r.t. f
+        return false;
+    }
+    else
+    {
+        // either f is a coefficient w.r.t. polynomial g or both
+        // f and g are from a base domain (should be Z or Z/p^n,
+        // then)
+        CanonicalForm q, r;
+        bool divides= tryDivremt (g, f, q, r, M, fail);
+        if (fail || !divides)
+          return false;
+        return r.isZero();
+    }
+}
+
 //{{{ CanonicalForm maxNorm ( const CanonicalForm & f )
 //{{{ docu

factory/cf_algorithm.h

@@ -41 +41 @@
 
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
+
+bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
 
 CanonicalForm maxNorm ( const CanonicalForm & f );